선택정렬(Selection-sort), 삽입정렬(Insertion-sort), 버블정렬(Bubble-sort)

선택정렬(Selection-sort)

선택정렬은 오름차순, 내림차순 정렬에 따라 가장 작은 값, 가장 큰 값을 선택한 뒤 맨 앞의 위치부터 차례대로 비교하여 정렬하는 방식이다.

정렬되지 않은 수 전체를 차례대로 비교하여 가장 작은 값을 찾고 이 값과 가장 첫번째 위치를 교환한다. 이러면 가장 첫번째 위치는 정렬이 된 것이다.

그리고 정렬되지 않은 부분에서 다시 가장 작은 값을 찾고 정렬되지 않은 부분의 첫번째 위치와 비교하여 교환한다.

이런 과정을 거쳐 정렬되지 않은 모든 부분을 정렬될 때까지 반복하는 것이다.

7, 3, 9, 4, 5, 1를 선택정렬로 오름차순 정렬해보자

우선 전체 중 가장 작은 값인 1을 찾는다.

1을 가장 첫번째에 있는 7(인덱스 0)과 비교하여 더 작다면 위치를 바꿔준다.

1, 3, 9, 4, 5, 7

맨 앞(인덱스0)은 정렬이 된 것이다.

1, 3, 9, 4, 5, 7 인덱스 1~5에서 가장 작은 값을 찾는다. = 3

3을 인덱스 1의 값 3과(결국 자기자신) 비교한다. 

1, 3, 9, 4, 5, 7

인덱스 0~1은 정렬되었다.

1, 3, 9, 4, 5, 7 인덱스 2~5에서 가장 작은 값을 찾는다. = 4

4를 인덱스 2의 값 9와 비교하고 바꿔준다.

1, 3, 4, 9, 5, 7

인덱스 0~2는 정렬되었다.

1, 3, 4, 9, 5, 7 인덱스 3~5에서 가장 작은 값을 찾는다. = 5

5를 인덱스 3의 값 9와 비교하고 바꿔준다.

1, 3, 4, 5, 9, 7

인덱스 0~3은 정렬되었다.

1, 3, 4, 5, 9, 7 인덱스 4~5에서 가장 작은 값을 찾는다. =7

7을 인덱스 4의 값 9와 비교하고 바꿔준다.

1, 3, 4, 5, 7, 9

모든 수가 정렬되었다.

선택정렬은 가령 모든 데이터가 정렬되어 있을지라도 가장 작은 값을 찾는 과정을 계속 거치기 때문에 불안전 정렬이며

최선이건 최악의 경우건 시간복잡도는 O(n^2)이다.

삽입정렬(Insertion-sort)

삽입정렬은 자신보다 한 칸 앞에 원소와 크기를 비교하면서 자신의 위치를 찾는 정렬이다.

인덱스 0부터 하면 비교할 대상이 없으므로 인덱스 1부터 시작한다.

인덱스 0~5까지 6개의 수를 오름차순으로 삽입정렬 해보자.

3, 5, 8, 1, 9, 7

인덱스 1부터 시작한다 했으므로 5부터 시작한다. 5를 임시변수에 저장해놓고 하나씩 비교한다.

[3, 5], 8, 1, 9, 7

여기서 대괄호는 비교연산을 수행하는 범위이자 비교연산을 통해 정렬이 보장되는 범위이다.

5를 자신보다 한 칸 앞에 있는 데이터 3과 비교한다. 5는 3보다 크므로 인덱스 0~1은 정렬됐다.

이제 인덱스 2의 값인 8을 기준으로 한칸씩 비교한다.

[3, 5, 8], 1, 9, 7

8은 5보다 크므로 교환하지 않는다. 그리고 이미 인덱스0~1은 정렬되어 있으므로 더이상 비교하지 않는다.

이제 인덱스0~2는 정렬됐다.

인덱스 3인 1을 기준으로 한칸씩 비교한다. temp=1

[3, 5, 8, 1], 9, 7

1은 8보다 작으므로 [3, 5, 8, 8], 9, 7  temp=1

1은 5보다 작으므로 [3, 5, 5, 8], 9, 7  temp=1

1은 3보다 작으므로 [1, 3, 5, 8], 9, 7  temp=1

1, 3, 5, 8, 9, 7   인덱스 0~3은 정렬됐다.

인덱스 4인 9를 기준으로 한칸씩 비교한다. temp=9

[1, 3, 5, 8, 9], 7

9는 8보다 크므로 인덱스0~4는 정렬됨을 보장받는다.

이제 마지막 인덱스인 7을 기준으로 한칸씩 비교한다.

[1, 3, 5, 8, 9, 7]

7은 9보다 작으므로 [1, 3, 5, 8, 9, 9]  temp=7

7은 8보다 작으므로 [1, 3, 5, 8, 8, 9]  temp=7

7은 5보다 크므로    [1, 3, 5, 7, 8, 9]  temp=7

1, 3, 5, 7, 8, 9 

이제 모든 수가 정렬 되었다. 

삽입정렬은 안전정렬이므로 모든 데이터가 이미 정렬되어있을 때 한번만 비교하면 되므로 시간복잡도는 O(n)이지만

최악의 경우에 O(n^2)의 수행시간이 걸린다.

버블정렬(Bubble-sort)

버블정렬은 인접한 두 원소를 비교하여 정렬하는 방식이다.

첫번째 원소부터 시작하여 그 다음 원소와 비교하고 다시 그 다음 원소와 비교하는 방식이다.

7, 3, 9, 4, 5, 1을 오름차순 버블정렬 해보자

우선 인덱스0, 1을 비교한다.

[7, 3], 9, 4, 5, 1

3은 7보다 크므로 바꿔준다.

[3, 7], 9, 4, 5, 1

이제 인덱스1, 2를 비교한다.

3, [7, 9], 4, 5, 1

9는 7보다 크므로 바꾸지 않는다.

이제 인덱스2, 3을 비교한다.

3, 7, [9, 4], 5, 1

4는 9보다 작으므로 바꿔준다.

3, 7, [4, 9], 5, 1

이제 인덱스3, 4를 비교한다.

3, 7, 4, [9, 5], 1

5는 9보다 작으므로 바꿔준다.

3, 7, 4, [5, 9], 1

이제 인덱스4, 5를 비교한다.

3, 7, 4, 5, [9, 1]

1은 9보다 작으므로 바꿔준다.

3, 7, 4, 5, [1, 9]

한번의 순회가 끝났고 6개의 원소 중 가장 큰 수인 9가 맨뒤로 가서 자신의 자리를 찾았으므로 다음 순회에선 굳이 모든 원소를 비교할 필요는 사라졌다. 다음 순회를 통해 뒤에서부터 원소들이 하나씩 더 정렬될 것이다.

따라서 2번째 순회부터는 이미 정렬된 원소는 제외하고 나머지만 비교하여 정렬할 것이다.

맨처음으로 돌아와서 3, 7, 4, 5, 1, 9에서 인덱스5를 제외하고 0, 1   1, 2   2, 3   3, 4 를 비교한다.

2번째 순회를 통해 인덱스 4에 7이 올 것이다.

3번째 순회를 통해 인덱스 3에 5가 올 것이다.

이러한 과정을 통해 버블정렬은 맨 뒤에서부터 큰 수가 차례대로 정렬된다.

버블정렬은 한 번의 순회를 할 때마다 비교해야 하는 개수가 하나씩 줄어들기 때문에 전체 원소의 개수가 n개일 때 n-1번, n-2번 n-3번 ... 2번, 1번 비교하게 된다.

따라서 모든 데이터가 이미 정렬되어 있을지라도 정렬을 보장받기 위해 전체적인 비교를 계속 진행하므로 최선이건 최악이건 시간복잡도는 O(n^2)이다.