Notice
Recent Posts
Recent Comments
Link
쟈미로그
기본 정렬 알고리즘들 본문
1. 버블 정렬 (Bubble Sort)
버블 정렬은 서로 인접한 원소 간에 대소 비교를 통해 차례대로 큰 수를 뒤로 보내는 정렬 방식이다.
- 시간복잡도(최선/평균/최악) : 모두 O(N^2)
- 안정 정렬 : YES
- 제자리 정렬 : YES (swap의 tmp 변수로 인해서 공간복잡도가 O(N)이라서 큰 메모리를 필요로 하지 않는다.)
어떤 경우라도 전체 원소를 비교해야해서 매우 비효율적이다.
static int[] num = { 4, 2, 2, 1, 7, 3, 10, 9, 6, 8 };
public static bubble() {
for (int i = 1; i < num.length; i++) {
for (int j = 0; j < num.length - i; j++) {
if (num[j] > num[j + 1])
swap(j, j + 1);
}
}
}2. 선택 정렬 (Selection Sort)
선택 정렬은 순서대로 위치를 선택하여, 해당 위치에 들어갈 원소를 찾아서 넣는 정렬 방식이다.
- 시간복잡도(최선/평균/최악) : 모두 O(N^2)
- 안정 정렬 : YES
- 제자리 정렬 : YES
버블정렬과 함께 항상 시간복잡도가 O(N^2)이라서 비효율적이지만, swap 횟수가 적게 일어나므로 버블정렬보단 빠르다.
void selectionSort() {
int minIndex;
for (int i = 0; i < num.length - 1; i++) {
minIndex = i;
for (int j = i + 1; j < num.length; j++) {
if (num[minIndex] > num[j])
minIndex = j;
}
swap(i, minIndex);
}
}3. 삽입 정렬 (Insert Sort)
삽입정렬은 순서대로 원소를 선택하여, 해당 원소의 index보다 낮은 위치의 원소들을 탐색해서 들어갈 위치를 찾아 넣는 정렬 방식이다.
- 시간복잡도(최선/평균/최악) : 정렬돼있는 경우 O(N)/O(N^2)/O(N^2)
- 안정 정렬 : YES
- 제자리 정렬 : YES
버블정렬, 선택정렬 보다 빠르지만 여전히 평균 O(N^2)의 성능을 보인다.
void insertSort() {
for (int i = 1; i < num.length; i++) {
int tmp = num[i];
int j = i - 1;
while ((j >= 0) && (num[j] > tmp)) {
num[j + 1] = num[j];
j--;
}
num[j + 1] = tmp;
}
}4. 병합 정렬 (Merge Sort)
병합정렬은 분할 정복법 알고리즘을 사용한다.
원소가 하나만 남을 때까지 이분할 한 후, 대소관계를 비교하며 병합해나가는 정렬 방식이다.
- 시간복잡도(최선/평균/최악) : 모두 O(N*logN)
- 안정 정렬 : YES
- 제자리 정렬 : NO (병합할 때마다 mid를 기준으로 왼쪽, 오른쪽 배열을 copy해야해서 계속해서 추가 메모리가 필요함)
레코드를 LinkedList로 구성할 경우?
merge 진행 시 L, R 배열을 항상 순차탐색으로 비교해서 값을 순서대로 삽입한다. L, R은 항상 정렬 돼있는 배열이기에 특정 값을 임의적으로 탐색하여 임의의 위치에 넣을 필요가 없다. 즉, index를 통한 임의 접근이 거의 일어나지 않는다!!
그래서 LinkedList 정렬 시 사용하면 효율적이다!
static void mergeSort(int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
mergeSort(left, mid);
mergeSort(mid + 1, right);
merge(left, mid, right);
}
}
static void merge(int left, int mid, int right) {
int[] L = Arrays.copyOfRange(num, left, mid + 1);
int[] R = Arrays.copyOfRange(num, mid + 1, right + 1);
int i = 0, j = 0, k = left;
int ll = L.length, rl = R.length;
while (i < ll && j < rl) {
if (L[i] <= R[j]) {
num[k] = L[i++];
} else {
num[k] = R[j++];
}
k++;
}
while (i < ll)
num[k++] = L[i++];
while (j < rl)
num[k++] = R[j++];
}5. 퀵 정렬 (Quick Sort)
퀵정렬은 분할 정복법 알고리즘을 사용한다.
피봇 원소를 기준으로 대소비교를 해서 재배열하고 피봇 기준으로 분할하는 과정을, 분할된 원소가 1개 남을 때까지 반복하는 정렬 방식이다.
- 시간복잡도(최선/평균/최악) : O(N_logN)/O(N_logN)/O(N^2) (정렬돼있는 경우, pivot을 맨 첫번 째 원소로 잡는다면 pivot 기준 특정 한 쪽에만 원소들이 몰리게 된다. 이 경우 pivot 기준 분할을 N번이나 하게 된다.)
- 안정 정렬 : NO
- 제자리 정렬 : YES
병합정렬과의 차이점?
병합정렬 : 원소 1개 될 때까지 분할 -> 재배열 반복
퀵정렬 : pivot 기준 재배열 -> 분할 반복
swap과 인덱스를 이용한 임의 접근이 빈번하다. 그래서 LinkedList 보다 Array에서 좋은 성능을 보인다.
static void quickSort(int left, int right) {
if (left >= right)
return;
int pivot = replace(left, right); // 재배열
quickSort(left, pivot - 1); // 분할
quickSort(pivot + 1, right);
}
static int replace(int left, int right) {
int pivot = num[left];
int i = left, j = right;
while (i < j) {
while (pivot < num[j])
j--;
while ((i < j) && (pivot >= num[i]))
i++;
swap(i, j);
}
num[left] = num[i];
num[i] = pivot;
return i;
}6. 힙 정렬 (Heap Sort)
힙정렬은 힙 자료구조를 통해 정렬한다.
힙은 완전이진트리이고, (최소힙 기준) 부모 노드는 항상 자식 노드보다 작은 값을 가져야한다. 그래서 push/pop 연산 시 앞의 성질을 갖도록 재배열 (heapify) 과정을 거치게 된다.
- 시간복잡도(최선/평균/최악) : 모두 O(N*logN) (pop 연산 N * 재배열 logN)
- 안정 정렬 : NO
- 제자리 정렬 : YES
static void heapSort() {
int len = num.length;
for (int i = len / 2 - 1; i >= 0; i--) // 배열 heap 구조로 변경
heapify(len, i);
for (int i = len - 1; i > 0; i--) {
swap(0, i);
heapify(i, 0);
}
}
static void heapify(int len, int i) {
int p = i;
int l = i * 2 + 1, r = i * 2 + 2;
if (l < len && num[p] < num[l])
p = l;
if (r < len && num[p] < num[r])
p = r;
if (i != p) {
swap(p, i);
heapify(len, p);
}
}7. 계수 정렬 (Counting Sort)
계수정렬은 배열 내 원소 값 별로 개수를 세서 정렬하는 방식으로, 원소 간 대소비교를 하지 않는 non-comparison 방식이다.
개수 카운팅 후에는 누적합을 구해서 해당 값을 가지는 원소가 들어갈 인덱스를 나타낼 수 있다.
- 시간복잡도(최선/평균/최악) : 모두 O(N + K) (K = 원소 최대값)
- 안정 정렬 : YES
- 제자리 정렬 : NO
원소를 누적합 위치에 넣을 때, 배열을 역순 순회하는 이유?
안정 정렬을 보장하기 위해서 역순으로 순회한다.
계수정렬은 선형 시간으로 정렬이 가능하다. 하지만 치명적인 문제들을 가지고 있어서 실제로 잘 쓰이지 않는다.
단점
- 자릿수를 갖는 데이터만 정렬 가능하다.
- 메모리 낭비 매우 심하다. { 1, 100, 1000, 100000 } 를 정렬한다 했을 때, 4개 데이터만 정렬하는 데에 100000 크기의 추가적인 배열이 필요하다..
int[] countingSort() {
int[] sortedNum = new int[num.length];
int max = Arrays.stream(num).max().getAsInt();
int[] counting = new int[max + 1]; // 1. 최대값 크기만큼 counting 배열 생성
for (int i = 0; i < num.length; i++) // 2. 개수 세기
counting[num[i]]++;
for (int i = 1; i < counting.length; i++) // 3. 누적합 구해서 index 범위 구하기
counting[i] += counting[i - 1];
for (int i = num.length - 1; i >= 0; i--) { // 4. 역으로 순회하면서 해당 원소가 들어갈 위치에 바로 넣음
counting[num[i]]--;
sortedNum[counting[num[i]]] = num[i];
}
return sortedNum;
}8. 기수 정렬 (Radix Sort)
기수정렬은 자릿수 기준으로 정렬해나가는 방식으로, 원소 간 대소비교를 하지 않는 non-comparison 방식이다.
자릿수 기준으로 계수정렬하는 식으로 구현할 수 있는데, 0~9까지만 counting 배열을 생성하면 된다는 장점이 있다.
- 시간복잡도(최선/평균/최악) : 모두 O(N * d) (d = 원소의 최대 자릿수)
- 안정 정렬 : YES
- 제자리 정렬 : NO
단점
- 자릿수를 갖는 데이터만 정렬 가능하다.
- 메모리 낭비 심하다.
static void radixSort() {
int max = Arrays.stream(num).max().getAsInt();
for (int exp = 1; max / exp > 0; exp *= 10) // 최대값의 자릿수만큼 counting 정렬 시행
countingSort(exp);
}
static void countingSort(int exp) {
int[] tmp = new int[num.length];
int[] counting = new int[10]; // 특정 자릿수 기준으로만 정렬해서, 0~9까지의 공간만 필요
for (int i = 0; i < num.length; i++) // 1. 개수 세기 <카운팅 정렬>
counting[(num[i] / exp) % 10]++;
for (int i = 1; i < 10; i++) // 2. 누적합 구하기
counting[i] += counting[i - 1];
for (int i = num.length - 1; i >= 0; i--) { // 3. 해당하는 인덱스에 원소 넣기
counting[(num[i] / exp) % 10]--;
tmp[counting[(num[i] / exp) % 10]] = num[i];
}
for (int i = 0; i < num.length; i++) // 자릿수 기준 정렬한 결과로 기존배열 갱신
num[i] = tmp[i];
}
Reference
https://gyoogle.dev/blog/algorithm/Radix%20Sort.html
https://roytravel.tistory.com/328
Comments