12. 정렬
- 정렬이란?
- 선택 정렬
- 삽입 정렬
- 버블 정렬
- 셸 정렬
- 합병 정렬
- 퀵 정렬
히프 정렬- 기수 정렬
- 정렬 알고리즘의 비교
12.1 정렬이란?
정렬 알고리즘 분류
(1) 단순하지만 비효율적인 방법 vs. 복잡하지만 효율적인 방법
(2) 내부 정렬 vs. 외부 정렬
우리는 내부 정렬만을 다룬다.
- Space complexity: 새로운 공간이 필요한가?
(3) 안정성 (stability)
: 나중에도 순서가 유지될 애들은 처음부터 순서를 유지하면서 정렬하는가?
▶ Stable sort:
- 삽입정렬 (insertion sort): 정렬되지 않은 곳에서 정렬된 곳으로 삽입한다. (정렬된 곳에서 비교한다.)
- 버블정렬 (bubble sort): 2개의 레코드를 비교해서 순서를 바꾼다. 따라서 한 단계마다 가장 큰 레코드의 순서는 정해진다.
- 합병정렬 (merge sort): 부분 리스트로 분할해서 정렬한다.
▶ Unstable sort:
- 선택정렬 (selection sort): 최솟값을 발견하면 배열의 첫 번째 요소와 교환한다.
히프정렬 (heap sort)
12.2 선택정렬 (selection sort)
: 정렬되지 않은 곳에서 비교하여, 가장 작은 애와 배열의 맨 앞의 애의 자리를 바꿔서 (교환해서) 정렬한다.
- 왼쪽 리스트와 오른쪽 리스트를 두는 경우, extra space가 필요하다. --> 제자리 정렬!
- 비교연산: 정렬되지 않은 곳에서 가장 작은 애를 찾는다.
- 이동연산: 가장 작은 애를 맨 앞으로 보내고, 원래 그 자리에 있던 애를 원래 작은 애가 있던 자리로 옮긴다. (SWAP)
--> 정렬되지 않은 곳에서 비교하므로, 시간이 갈수록 비교할 애들의 수가 줄어든다.
- 비교연산: 정렬되지 않은 곳에서 비교하여, 가장 작은 애를 A[least]에 넣는다.
- SWAP: A[least]와 배열의 가장 앞에 있는 애(A[i])의 자리를 바꾼다. --> Unstable sort
- 비교: 정렬되지 않은 곳에서 비교해서 제일 작은 애를 골라, 정렬된 곳의 가장 뒤에 끼워넣는다. --> 정렬되지 않은 곳은 점점 줄어들기 때문에, 비교할 것들이 점점 줄어든다.
- 이동: SWAP
12.3 삽입정렬
: 정렬이 안 된 리스트에서 정렬된 리스트로 삽입한다. 이때, 정렬된 구간의 정렬이 유지되는 위치에 삽입해야 한다!
--> 정렬된 구간에서 비교한다.
: 정렬되지 않은 곳의 맨 앞의 애를, 정렬된 곳의 적절한 자리로 삽입한다.
▶ 선택정렬(selection sort) vs. 삽입정렬(insertion sort)
- 선택정렬: 정렬되지 않은 곳에서 가장 작은 애를 뽑아서, "교환"한다. --> Unstable sort!
- 삽입정렬: 정렬되지 않은 곳의 맨 앞의 애를 뽑아서, 정렬된 곳의 적절한 위치에 "삽입"한다. --> Stable sort!
- key값에 정렬되지 않은 부분의 가장 앞의 애를 넣는다.
- 비교연산: 정렬된 부분의 애들과 key를 비교하여,
- 이동연산: 만약 key가 정렬되지 않은 부분의 애보다 작으면, 그 앞에 밀어넣는다.
12.4 버블정렬
: 인접한 2개의 레코드를 비교하여, 순서대로 되어있지 않으면 서로 "교환"한다.
- 비교연산: 둘씩 비교한다.
- 이동연산: 둘씩 비교한 결과 교환 해야되면, 교환한다.
--> 1 round가 끝나면, 비교한 것들 중에 가장 큰 애는 최종위치가 결정된다.
+ Stable sort: "교환"에도 불구하고 안정적인 정렬 방법이다.
- Stable sort: 나중에도 순서가 유지될 애들은 순서를 유지하면서 정렬한다.
--> 2개씩 비교하여 교환하면, 큰 애는 뒤로, 작은 애는 앞으로 간다!
- 비교연산: inner for문 안에서 두 개씩 비교한다.
- 이동연산: SWAP - 비교 결과, 교환 해야되면 교환한다. --> 케이스가 나눠짐!
12.5 셸정렬
- 삽입정렬 - Problem: 이웃한 레코드와만 비교하여 이동할 수 있다.
- 셸정렬 - Solution: 부분 리스트로 나눠서, 이웃하지 않은 레코드와도 비교하여 이동할 수 있게 하자!
- 부분 리스트를 어느정도의 간격(gap)으로 나눌 것인지에 따라, 셸정렬의 성능이 달라진다.
: gap의 크기를 점점 줄여가며 정렬한다.
: 이 프로그램에서는 gap이 1/2가 되도록 프로그램을 짰다. 하지만 gap의 설정은 달라질 수 있다!
- 다만, gap은 점점 작아져서, 마지막에는 gap이 1이 되어, 삽입정렬(insertion sort)과 동일해져야 한다.
: 셸정렬(shell sort)의 복잡도는 gap을 어떻게 설정하느냐에 따라 달라진다!
Selection sort와 Bubble sort 모두 1 round마다 최종 자리를 확정하지만, 1 round의 의미가 다르다.
- Bubble sort: 2개씩의 비교가 처음부터 끝까지 진행된 것
- Selection sort: Unsorted part에서 비교해서 제일 작은 애를 골라서 sorted part의 가장 뒤에 끼워넣는 것
출처: 이화여자대학교 이숙영교수님 자료구조
'자료구조' 카테고리의 다른 글
| [자료구조] 1201 (1) (0) | 2023.12.05 |
|---|---|
| [자료구조] 1128 (0) | 2023.12.05 |
| [자료구조] 1121 (2) - 12. 정렬 (0) | 2023.11.28 |
| [자료구조] 1121 (1) (0) | 2023.11.28 |
| [자료구조] 1117 (0) | 2023.11.28 |
