[컴퓨터과학개론] 알고리즘 - 정렬 알고리즘(선택 정렬, 버블 정렬, 삽입 정렬)

기본 개념

정렬 → 주어진 데이터를 값의 크기 순서에 따라 재배열하는 것

 

정렬을 위한 기본 가정

 

A[i] > 0, (0≤i≤n-1)
 
if i < j
then
    A[i]≤A[j], (0≤i,j≤n-1)

선택 정렬

가장 작은 키값을 갖는 원소를 선택하여 차례대로 나열

선택 정렬의 처리 과정

 

선택 정렬의 적용 예

 

버블 정렬

왼쪽에서부터 모든 인접한 두 원소를 차례대로 비교한 후 왼쪽 값이 더 큰 경우에는 오른쪽 값과 자리바꿈을 통해 정렬

 

버블 정렬의 적용 예

 

버블 정렬의 특징

선택 정렬에 비해 원소 교환이 많이 발생

- 선택 정렬보다 비효율적

삽입 정렬

주어진 원소를 하나씩 뽑은 후, 나열된 원소들이 항상 정렬된 형태를 가지도록 원소를 바른 위치에 삽입하여 나열하는 방식

 

삽입 정렬의 처리 과정

미정렬 부분의 왼쪽으로부터 한 원소씩 꺼내어 정렬 부분에서 제자리를 찾아 삽입하는 방법

 

삽입 정렬의 적용 예

 

삽입 정렬의 특징