🎶 단순 정렬
버블 정렬 (Bubble Sort)
- 이웃한 두 요소의 대소 관계를 비교해 교환을 반복 (가장 기본적인 정렬)
- n개 요소의 정렬이 모두 끝나려면 n-1회의 패스가 수행되어야 함
- 하나의 패스에서 요소 간의 교환이 이루어지지 않았다면 정렬이 완료된 상태로 간주하여 정렬 작업 중단
- 나아가 특정 인덱스부터 요소 간의 교환이 이루어지지 않았다면 해당 인덱스까지는 정렬 완료 상태로 간주
for(int i = 0; i < n - 1; i++) {
int chk = 0;
/** for문 내부에서 또 다시 loop를 사용해 우선순위가 높은 요소(배열의 앞)부터 정렬 완료
배열의 앞부터 정렬을 마치려면 내부 for문에서는 요소의 끝에서부터 앞으로 스캔 */
for(int j = n - 1; j > i; j--) {
if(a[j-1] > a[j]) { // 앞의 요소와 비교 및 교환
swap(a, j, j-1);
chk++;
}
}
if(chk == 0) { break; } // 패스 내에서 요소 간 교환이 이루어지지 않았으므로 정렬 종료
}
/**
개선된 버블 정렬
*/
int k = 0;
while(k < n-1) {
int last = n-1;
for(int j = n-1; j > k; j--) { // 정렬 되지 않은 요소 까지만 정렬 수행
if(a[j-1] > a[j]) { // 앞의 요소와 비교 및 교환
swap(a, j, j-1);
last = j;
}
k = last;
}
}
단순 선택 정렬 (Straight Selection Sort)
- 가장 작은 요소부터 선택해 알맞은 위치로 옮겨서 순서대로 정렬하는 알고리즘으로,
- 1. 정렬되지 않은 리스트의 가장 작은 요소를 선택
- 2. 정렬되지 않은 리스트의 첫 번째 요소와 위치 교환
의 과정을 n-1회 반복
for(int i = 0; i < n-1; i++) {
int min = i;
for(int j = i + 1; j < n; j++) {
if(a[j] < min) {
min = j;
}
}
swap(a, i, min);
}
단순 삽입 정렬 (Straight Insertion Sort)
- 선택한 요소를 그 앞쪽의 요소들과 비교해 알맞은 위치에 삽입
- 즉, 아직 정렬되지 않은 부분의 첫 번째 요소를 정렬된 리스트의 알맞은 위치에 삽입
for(int i = 1; i < n; i++) {
int j;
int tmp = a[i];
for(j = i; j > 0 && a[j-1] > tmp; j--) {
a[j] = a[j-1]; // 한 칸씩 뒤로 밈
}
a[j] = tmp; // 삽입
}
셀 정렬 (Shell Sort)
- 단순 삽입 정렬의 장점을 살리고 단점을 보완해 정렬 속도가 개선됨
- 정렬을 수행할 배열의 요소를 그룹으로 나눠 각 그룹 별로 단순 삽입 정렬을 수행한 후, 그룹을 합치면서 정렬을 반복하여 요소의 이동 횟수를 줄이는 방식
- 요소 스캔 횟수는 늘지만, 요소 이동의 횟수는 줄어듦
- 가장 효과적인 i값(그룹을 나누는 값)은 1부터 시작하여 3배한 값에 1을 더하는 수열이면서 배열의 요솟수 n을 9로 나눈 값을 넘지 않는 값
- 시간 복잡도 O(n1.25)
- 단순 정렬에 비해 매우 빠른 속도이나, 멀리 떨어져 있는 요소를 교환해야 하므로 안정적이지 않음
for(int i = n / 2; i > 0; i /= 2) { // 배열을 그룹으로 나눔
for(int j = i; j < n; j++) {
int k;
int tmp = a[j];
for(k = j-i; k >= 0 && a[k] > tmp; k-=i) {
a[k+i] = a[k];
}
a[k+i] = tmp;
}
}
/**
개선된 방법
*/
int i;
for(i = 1; i < n/9; i = i*3+1) ; // 그룹을 나눌 초기값
for(; i > 0; i /= 3) {
for(int j = i; j < n; j++) {
// 상동
}
}
퀵 정렬
- 가장 빠른 정렬 알고리즘 중 하나로 널리 사용됨
- 피벗(Pivot)이라고 하는 기준을 정해 그보다 값이 큰 그룹과 작은 그룹으로 나눔
- 각 그룹에 대해 피벗 설정과 그룹을 나누는 과정을 반복해 모든 그룹의 요소가 한 개가 될 때 정렬 종료
- 시간 복잡도 O(n log n), 최악의 경우 O(n2)
/**
Recursive
*/
int pl = left;
int pr = right;
int x = a[(pl+pr)/2; // pivot
do {
while(a[pl] < x) pl++;
while(a[pr] > x) pr++;
if(pl <= pr) {
swap(a, pl++, pr--);
}
} while(pl <= pr);
if(pl < right) quickSort(a, pl, right);
if(left < pr) quickSort(a, left, pr);
/**
Non-Recursive (Stack 사용)
*/
Stack<Integer> lStack = new Stack<>();
Stack<Integer> rStack = new Stack<>();
lStack.push(left);
rStack.push(right);
while(!lStack.isEmpty()) {
int pl = left = lStack.pop();
int pr = right = rStack.pop();
int x = a[(left+right)/2];
// 상동
do {
while(a[pl] < x) pl++;
while(a[pr] > x) pr++;
if(pl <= pr) {
swap(a, pl++, pr--);
}
} while(pl <= pr);
if(pl < right) { lStack.push(pl); rStack.push(right); }
if(left < pr) { lStack.push(left); rStack.push(pr); }
}
병합 정렬
- 배열을 앞 부분과 뒷 부분으로 나누어 각각 정렬한 후 병합하는 작업을 반복하여 정렬을 수행
while(pa < na && pb < nb) {
c[pc++] = a[pa] < b[pb] ? a[pa++] : b[pb++];
}
while(pa < na) {
c[pc++] = a[pa++);
} // 남아있는 값 저장(b배열은 비어있고, a배열에만 값이 남아있다는 전제)
while(pb < nb) {
c[pc++] = b[pb++);
}
힙 정렬
- 힙 자료구조를 이용한 정렬, 우선순위 큐(Priority Queue)가 대표적인 예
- [부모의 값이 자식 요소의 값보다 우선순위가 언제나 높다] 는 조건을 만족하는 완전이진트리