[자료구조] 12. 정렬

1. 선택정렬(selection sort)
   : 정렬되지 않은 곳에서 비교하여, 가장 작은 애와 배열의 맨 앞의 애를 교환한다.
   - 시간복잡도: O(n^2)
   - unstable sort
   - in-place sort
   
   • 비교연산: 정렬되지 않은 곳에서 제일 작은 애
   • 이동연산: 교환 --> unstable sort
2. 삽입정렬(insertion sort)
   : 정렬되지 않은 곳의 맨 앞의 애를, 정렬된 곳에서 비교하여 적절한 자리에 삽입한다.
   - 시간복잡도: 최악의 경우는 O(n^2), 최선의 경우는 O(n); 대부분 정렬되어 있으면 매우 효과적이다.
   - stable sort
   - in-place sort
   
   • key값에 정렬되지 않은 부분의 맨 앞의 애를 넣는다. --> 공간복잡도: O(1): in-place sort
   • 비교연산: 정렬된 부분의 애들과 key값을 비교하여,
   • 이동연산: 만약 key가 정렬되지 않은 부분의 애보다 작으면, 그 앞에 밀어넣는다. --> stable sort
3. 버블정렬(bubble sort)
   : 인접한 2개의 레코드를 비교하여, 순서대로 되어있지 않으면, 서로 교환한다.
   - 1 라운드가 끝나면, 비교한 것들 중에서 가장 큰 애는 최종 위치가 결정된다.
   - 시간복잡도: O(n^2)
   - stable sort
   - in-place sort
   
   1. 비교연산: 둘씩 비교한다.
   2. 이동연산: 비교한 결과, 이동 해야되면 이동한다. --> stable sort
4. 셸정렬(shell sort)
   : 삽입정렬의 문제는, 정렬되지 않은 곳에서 뽑은 애를 정렬된 곳의 이웃한 레코드와만 비교할 수 있다는 것이다. 셸정렬에서는 부분리스트로 나눠서, 이웃하지 않은 레코드와도 비교할 수 있게 한다.
   - 시간복잡도: gap의 크기에 따라 달라진다.
   - stable sort
   - in-place sort
   
   1. 전체 리스트를 일정 간격(gap)의 부분리스트로 나눈다.
   2. 나누어진 각각의 부분리스트를 삽입정렬한다.
   3. gap의 크기를 점점 줄여가며 정렬한다. --> gap의 크기에 따라 시간복잡도가 달라진다.
5. 합병정렬(merge sort)
   - 시간복잡도: O(n*log(n))
   - stable sort
   - Not in-place sort
   
   1. 분할: data set의 크기가 1이 될 때까지 분할한다.
   2. 합병: 비교하여, 정렬한다. 
      --> 분할된 두 배열의 맨 앞의 애부터 비교하여, 작은 것을 새로운 배열에 넣는다. --> in-place sort 아님!
6. 퀵정렬(quick sort)
   : 리스트를 2개의 부분리스트로 비균등 분할하고, 각각의 부분리스트를 다시 퀵정렬한다.
   - 시간복잡도: O(n^2)
   - unstable sort
   - in-place sort
   
   1. 배열의 가장 왼쪽: 피벗
   2. high 포인터, low 포인터 점점 가운데로 이동하여, 이동 중 low 포인터가 가리키는 값이 피벗보다 클 때, high 포인터의 값이 피벗보다 작을 때 두 배열을 교환한다.
   3. high 포인터와 low 포인터가 만나는 지점에서 작은 애와 피벗을 교환한다.
      --> 피벗의 위치는 최종 위치로 결정된다.
7. 기수정렬(radix sort)
   : 낮은 자릿수부터 분류하여 버킷에 넣었다가 꺼내는 과정을 반복한다. 레코드를 비교하지 않고 정렬하는 방법이다.
   - 시간복잡도: O(dn) -- n*log(n)을 능가하는 빠른 방법!
   - stable sort
   - Not in-place sort: buffer

 

---

12.1 정렬 (sorting)

: 물건을 크기순으로 오름차순이나 내림차순으로 나열하는 것

 

12.2 선택 정렬 (selection sort)

: 오른쪽 리스트에서 가장 작은 숫자를 선택하여 왼쪽 리스트로 이동하는 것

 

▶ 제자리 정렬(in-place sorting)

: 입력 배열에서 최소값을 발견한 다음, 이 최소값을 배열의 첫번째 요소와 교환한다.

(입력 배열 이외에 다른 추가 메모리를 요구하지 않는 정렬 방법)

선택정렬 과정

선택정렬 알고리즘

선택정렬 복잡도 분석

 

12.3 삽입 정렬 (insertion sort)

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

삽입정렬 과정

삽입정렬 알고리즘

삽입정렬 복잡도 분석

 

12.4 버블 정렬 (bubble sort)

: 인접한 2개의 레코드를 비교하여, 크기가 순서대로 되어 있지 않으면 서로 교환하는 비교-교환 과정을 리스트 왼쪽 끝에서 시작하여 오른쪽 끝까지 진행한다.

버블정렬

버블정렬 알고리즘

버블정렬 복잡도 분석

 

12.5 셸 정렬 (shell sort)

• 삽입 정렬(insertion sort): 삽입 정렬의 최대 문제점은 요소들이 삽입될 때, 이웃한 위치로만 이동한다는 것이다. 만약 삽입되어야 할 위치가 현재 위치에서 상당히 멀리 떨어진 곳이라면, 많은 이동을 해야만이 제자리로 갈 수 있다.

--> 셸 정렬에서는 요소들이 멀리 떨어진 위치로도 이동할 수 있다.

: 셸 정렬에서는 먼저 정렬해야 할 리스트를 일정한 기준에 따라 분류하여, 연속적이지 않은 여러 개의 부분 리스트를 만들고, 각 부분 리스트를 삽입 정렬을 이용하여 정렬한다. 만약 모든 부분 리스트가 정렬되면, 셸 정렬은 다시 전체 리스트를 더 적은 개수의 부분 리스트로 만든 후에 알고리즘을 되풀이한다.

셸 정렬

셸 정렬 복잡도 분석

 

12.6 합병 정렬 (merge sort)

: 하나의 리스트를 두 개의 균등한 크기로 분할하고, 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여, 전체가 정렬된 리스트를 얻는다.

 

▶ 분할 정복(divide and conquer) 기법:

1. 분할(Divide): 하나의 배열을 2개의 부분배열로 나눈다.
2. 정복(Conquer): 부분배열을 정렬한다.
3. 결합(Combine): 부분배열을 통합한다.

--> 합병 정렬에서 실제로 정렬이 이루어지는 시점은 2개의 리스트를 합병(merge)하는 단계이다.

Q. 해야하는 합병(merge)의 개수가 늘어나니까, 오히려 복잡도가 증가하지 않을까?

합병정렬

합병정렬 알고리즘

합병 알고리즘

합병정렬 복잡도 분석

 

12.7 퀵 정렬 (quick sort)

: 전체 리스트를 2개의 부분 리스트로 분할하고, 각각의 부분 리스트를 다시 퀵정렬한다. 하지만 합병정렬과 달리, 퀵정렬은 리스트를 비균등하게 분할한다.

 

▶ 분할 정복(divide and conquer) 기법:

1. 리스트 안에 있는 한 요소를 피봇(pivot)으로 선택한다.
2. 피봇보다 작은 요소들은 모두 피봇의 왼쪽으로 옮겨지고, 피봇보다 큰 요소들은 모두 피봇의 오른쪽으로 옮겨진다. 결과적으로 피봇을 중심으로 왼쪽은 피봇보다 작은 요소들로 구성되고, 오른쪽은 피봇보다 큰 요소들로 구성된다.
3. 이 상태에서 피봇을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬하면, 전체 리스트가 정렬된다.

퀵 정렬

퀵 정렬 알고리즘

퀵 정렬 복잡도 분석

 

12.8 히프 정렬 (heap sort)

: 정렬할 배열을 먼저 최소 히프로 변환한 다음, 가장 작은 원소부터 차례대로 추출하여 정렬하는 방법

 

12.9 기수 정렬 (radix sort)

• 기수(radix): 숫자의 자릿수

: 레코드를 비교하지 않고도 정렬하는 방법이다.

 

▶ 한자릿수 정렬

1. 버킷(bucket)을 만들어서, 입력 데이터를 각 자릿수의 값에 따라 상자에 넣는다.
2. 각 버킷 안에 들어 있는 숫자를 순차적으로 읽는다. 그러면 정렬된 숫자를 얻을 수 있다.

한자릿수 정렬

 

▶ 두자릿수 정렬

두자릿수 정렬

: 낮은 자리수로 먼저 분류한 뒤 기수정렬을 하고, 순서대로 읽어서 다시 높은 자리수로 기수정렬한다.

 

기수정렬 알고리즘

기수정렬 복잡도 분석

 

12.10 정렬 알고리즘의 비교

정렬 알고리즘의 비교