[자료구조] 정렬

1. 선택 정렬(Selection Sort) : O(n^2)

정렬된 리스트 | 정렬되지 않은 리스트

오름차순일 때

정렬이 안 된 숫자 중, 가장 작은 수를골라 정렬 안 된 리스트 중 가장 왼 쪽의 원소와 교환하고, 정렬 된 리스트에 포함시킨다.

ex.

) 5 3 8 1 2 7

1 ) 3 8 5 2 7

1 2 ) 8 5 3 7

1 2 3 ) 5 8 7

1 2 3 5 ) 8 7

1 2 3 5 7 ) 8

1 2 3 5 7 8 )

2. 삽입 정렬 (Insertion sort) : O(n^2)

 

정렬된 리스트 | 정렬되지 않은 리스트

오름차순일 때

정렬되어있지 않은 리스트의 첫 번째 숫자가 정렬된 리스트의 어느 위치에 삽입되어야하는가를 판단한 후, 해당 위치에 숫자를 삽입.

-> 점점 정렬된 리스트의 크기를 키워 나감.

ex.

) 5 3 8 1 2 7

5 ) 3 8 1 2 7

3 5 ) 8 1 2 7

3 5 8 ) 1 2 7

1 3 5 8 ) 2 7

1 2 3 5 8 ) 7

1 2 3 5 7 8 )

3. 버블 정렬 (Bubble Sort) : O(n^2)

index++ 두 개씩 짝을 지어 비교해 자리를 바로잡아가면서 오른쪽이 최댓값이 되도록 하나씩 바로잡아간다.

ex.

5 3 8 1 2 7

Scan1)

3 5' 8 1 2 7

3 5 8' 1 2 7

3 5 1 8' 2 7

3 5 1 2 8' 7

3 5 1 2 7 8'

Scan2)

3 5' 1 2 7 8

3 1 5' 2 7 8

3 1 2 5' 7 8

3 1 2 5 7' 8

3 1 2 5 7 8'

Scan3)

1 3' 2 5 7 8

1 2 3' 5 7 8

1 2 3 5' 7 8

1 2 3 5 7' 8

1 2 3 5 7 8'

Scan4)

1 2 3 5 7 8 중 swap발생 x -> 정렬이 완료됨.

단점 : swap작업은 3개의 이동을 포함하고 있으므로 복잡도가 너무 커진다., 단순하지만 거의 쓰이지 않는 알고리즘이다.

4. 셸 정렬(Shell sort) : O(n^(1.5))

먼저 정렬해야 할 리스트들을 일정한 기준에 따라 분류하여 연속적이지 않은 여러 개의 부분리스트를 만들고, 각 부분 리스트를 삽입 정렬을 이용하여 정렬한다.

부분리스트를 만들 때, 주어진 리스트의 각 k번째 요소를 추출해서 만든다. k(gap, 간격)을 줄여가므로, 수행 과정이 반복될 때마다 하나의 부분 리스트에 속하는 레코드들의 개수는 증가. -> 마지막 step의 gap==1

ex.

10 8 6 20 4 3 22 1 0 15 16

gap=5)

10 3 16

8 22

6 1

20 0

4 15

각 부분 리스트들을 Insertion sort를 이용해서 정렬

3 10 16

8 22

1 6

0 20

4 15

다시 합침

3' 8 1 0 4 10' 22 6 20 15 16'

3' 8 1 0' 4 10 22' 6 20 15' 16

gap=3)

3 0 22 15

8 4 6 16

1 10 20

부분리스트들을 Insertion sort를 이용해서 정렬.

ex. 3 0 22 15

3) 0 22 15

0 3 ) 22 15

0 3 22 ) 15

0 3 15 22)

0 3 15 22

4 6 8 16

1 10 20

다시 합침

0' 4 1 3' 6 10 15' 8 20 22' 16

0 4 1 3 6 10 15 8 20 22 16

gap=1)

0

4

1

3

6

10

15

8

20

22

16

합침

0 1 3 4 6 8 10 15 16 20 22

5. 합병 정렬(merge sort) : O(n*log_2(n))

DIVIDE AND CONQUER

divide -> conquer -> combine

divide

정렬해야 할 배열을 같은 크기의 2개의 부분 배열로 나눈다.

부분 배열의 크기가 크다면, 적당해질 때까지 divide 반복

conquer

부분 배열 정렬

combine

정렬된 부분 배열들을 합병 //합병 과정에서도 간단한 정렬이 필요함.

ex.

27 10 12 20 25 13 15 22

왼 쪽 부분 배열

27 10 12 20

27 10  |  12 20

(27 | 10) | (12 | 20)

10 27 | 12 20

10 12 20 27

오른 쪽 부분 배열

25 13 15 22

25 13 | 15 22

25 | 13 | 15 | 22

13 25 | 15 22

13 15 22 25

10 12 20 27 | 13 15 22 25

10 12 13 15 20 22 25 27

6. 퀵 정렬 (Quick sort) : O(n*log_2(n)) //같은 복잡도를 가지는 다른 정렬 알고리즘보다 제일 빠르다. -> 그래서 퀵정렬

DIVIDE AND CONQUER

**pivot사용

::pivot을 중심으로 부분 리스트들이 절반으로 나뉜다면 가장 효율적이다.

그래서 주로 배열 원소들의 첫 번째, 가운데, 마지막 중 median of three를 중간값으로 가정하고 pivot으로 설정함. (실제 중간값 구하려면 비용이 커짐.)

리스트 안의 원소 중 하나를 pivot으로 잡고, 그보다 작으면 왼쪽, 그보다 크면 pivot 오른쪽에 두기. (비균등하게 분할됨)

-> pivot을 제외한 왼쪽 리스트와 오른쪽 리스트를 정렬함.

-> high, low 포인터를 각각 pivot이 아닌 것 중 가장 오른쪽, 왼쪽으로 잡는다.

-> high, low를 비교해서 high가 low보다 작은 값을 가지면 서로 swap

-> high, low가 만나는 지점에서 비교연산 멈춤.

여기에선 첫 번째 원소를 pivot으로 잡음.

5* 3' 8 4 9 1 6 2 7'

low -> 3

high -> 7

//바꿀 필요 x

...

low -> 8

high -> 2

두 개를 swap

5* 3 2 4' 9 1 6' 8 7

5* 3 2 4 9' 1' 6 8 7

low-> 9

high -> 1

swap

5* 3 2 4 1 9 6 8 7

low, high가 만남.

만나는 위치에 pivot을 둔다.

3 2 4 1 5* 9 6 8 7

pivot을 중심으로 나눠진 부분 리스트들을 각각 정렬함.

1 2 3 4 5* 6 7 8 9

7. 히프 정렬 (heap sort) : O(n*log_2(n))

유리할 때 : 가장 큰 값, 또는 가장 작은 값 중 몇 개만 필요할 때.

방법 : 

오름차순 정렬 -> min heap 사용 -> 삭제연산을 반복하면서 return값들 순서대로

내림차순 정렬 -> max heap 사용 -> 삭제 연산을 반복하면서 return값들 순서대로

8. 기수 정렬 (Radix sort) : O(dn), (usually, d<10), d는 자릿수

첫 자릿수부터 한 digit씩 감소시켜가면서 1의 자리가 될 때까지 bucket에 넣고, bucket 내용물 순서대로 정렬하면 기수정렬이 완성됨.

단점 :

1. 추가적인 메모리를 필요로 한다. -> In-place sorting이 아니다.

2. 한정된 데이터타입 -> 레코드의 키들이 동일한 길이를 가지는 숫자나 문자열로 구성되어 있어야 한다. -> 숫자면 맨 앞에 자릿수에 맞게 0000붙이고, 문자라도 0붙여서 정렬할 때에만 0 bucket쓰면 안 되나?