정렬에 대해 공부해본 내용을 정리해보겠습니당 -.
0. 정렬 알고리즘의 안정성
정렬 알고리즘은 안정된 알고리즘과 그렇지 않은 알고리즘으로 나뉩니다.
안정된 알고리즘 : 같은 값의 기를 가진 요소의 순서가 정렬 전후에도 유지되는 것
안정되지 않은 알고리즘 : 같은 점수인 경우 반드시 학번 순으로 정렬되는 것은 아님
정렬 알고리즘의 핵심 요소 교환, 선택, 삽입
1. 버블 정렬
O(n²)
2개씩 비교하면서 끝까지 감. -> 가장 작은 원소부터(가장 큰 원소부터) 끝에 쌓이게 됨.
- 실제 요소를 교환하는 횟수 <- 배열의 요솟값에 영향을 많이 받음
- 교환 횟수의 평균값 = n(n-1)/4
- swap에서 값의 이동이 3회 발생하므로 이동 횟수의 평균 = 3n(n-1)/4
알고리즘의 개선
- swap이 일어나지 않으면
멈춤 - 마지막으로 교환을 수행한 위치를 저장함
-> 일정 부분부터 교환이 없다면 이미 정렬된 것이므로
2. 단순 선택 정렬
O(n²)
가장 작은 요소부터 선택해 알맞은 위치로 옮겨서 순서대로 정렬하는 알고리즘
(현시점) 가장 작은 요소를 제일 앞 원소랑 위치 교환
- 서로 떨어져 있는 요소를 교환하는 것이므로 안정적이지 않음
3. 단순 삽입 정렬
O(n²)
선택한 요소를 그보다 더 앞쪽의 알맞은 위치에 삽입하는 작업을 반복하여 정렬하는 알고리즘
-> 최소 원소를 교환하는(단순 선택 정렬) 것이 아니라 알맞은 위치로 옮기는 것
- 떨어져 있는 요소들이 서로 뒤바뀌지 않아
안정적임 - 요소의 비교횟수, 교환횟수 = n²/2회
특징
- 정렬의 마쳤거나 정렬을 마친 상태에 가까울수록 속도가 매우 빨라짐
- 삽입할 위치가 멀리 떨어져 있으면 이동해야 하는 횟수가 많아짐
4. 셸 정렬
단순 삽입 정렬의 장점은 살리고 단점은 보완하여 좀 더 빠른 알고리즘
정렬할 배열의 요소를 그룹으로 나눠 각 그룹별로 단순 삽입 정렬을 수행하고, 그 그룹을 합치면서 정렬을 반복하여 요소의 이동 횟수를 줄이는 방식
5. 퀵 정렬
O(n logn)
가장 빠른 정렬 알고리즘 중의 하나로 사용됨
- 배열을 두 그룹으로 나눔
(피벗, 왼쪽 끝 요소의 인덱스인 왼쪽 커서, 오른쪽 끝 요소인 오른쪽 커서를 설정)
2-1. 왼쪽 커서 >= x 가 성립하는 요소를 찾을 때까지 왼쪽 커서를 오른쪽으로 옮김.
2-2. 오른쪽 커서 <= x 가 성립하는 요소를 찾을 때까지 오른쪽 커서를 왼쪽으로 옮김.
- 분할 정복 알고리즘 -> 재귀 호출을 사용하여 구현
- 비재귀적으로도 구현 가능
6. 병합 정렬
O(n logn)
배열의 앞부분과 뒷부분으로 나누어 각각 정렬한 다음 병합하는 작업을 반복하여 정렬을 수행하는 알고리즘
-> 두 배열을 비교하면서 작은 요소들을 순차적으로 새 배열에 append
7. 힙 정렬
O(n logn)
선택 정렬을 응용한 알고리즘
힙: 부모의 값이 자식의 값보다 항상 크다는 조건을 만족하는 완전이진트리
가장 큰 값이 루트에 위치하는 특징을 이용한 정렬 알고리즘
-> 힙에서 가장 큰 값이 루트를 꺼냄
-> 힙의 마지막 요소를 루트 위치로 옮김
(이때, 루트를 제외하고는 힙 상태를 유지하고 있음)
-> 큰 값을 가지는 자식과 위치를 바꿈
-> 자식의 값이 작거나 리프 노드에 다다르면 작업이 종료됨
8. 도수 정렬
요소의 대소 관계를 판단하지 않고 빠르게 정렬할 수 있는 알고리즘
- 도수분포표 만들기
- 누적도수분포표 만들기
- 목적배열 만들기
- 요솟값과 누적도수분포표를 대조하여 정렬을 마친 배열을 만듬
- 배열 복사하기
