정렬이란 데이터를 정해진 기준에 따라 배치해서 의미있는 구조로 재설정하는 것.
| 정렬 알고리즘 | 정의 |
| 버블 (bubble) | 데이터의 인접 요소끼리 비교하고 swap 연산을 수행하여 정렬 |
| 선택 (selection) | 대상에서 가장 크거나 작은 데이터를 찾아가 선택을 반복하면서 정렬 |
| 삽입 (insertion) | 대상을 선택해 정렬된 영역에서 선택 데이터의 적절한 위치를 찾아 삽입하며 정렬 |
| 퀵 (quick) | pivot 값을 선정해 해당 값을 기준으로 정렬 |
| 병합 (merge) | 이미 정렬된 부분 집합들을 효율적으로 병합해 전체를 정렬하는 방식 |
| 기수 (radix) | 데이터의 자릿수를 바탕으로 비교해 데이터를 정렬하는 방식 |
버블 정렬
버블 정렬은 두 인접한 데이터의 크기를 비교해 정렬하는 방법.
빅-세타 : O(n^2)
빅-오 : O(n^2)
// 포인트는 n - 1 - i
// 이때, i는 조건에서만 사용된다
// if 절에서는 j만 사용된다
// -1 하는 이유는 항상 다음 인덱스를 보기 때문
// -i 하는 이유는 이미 정렬된 항목은 안봐도 되기 때문
int temp;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}선택 정렬
선택 정렬은 대상 데이터에서 최대나 최소 데이터를 데이터가 나열된 순으로 찾아가며 선택하는 방법.
빅-세타 : O(n^2)
빅-오 : O(n^2)
// arr.length - 1 인 이유는 마지막 인덱스까지 선택하지 않아도 되기 때문
// i + 1 인 이유는 선택된 인덱스는 제외하고 최소/최대 값을 찾으면 되기 때문
int[] arr = {1, 2, 3, 4};
int temp;
for (int i = 0; i < arr.length - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[minIndex] < arr[j]) {
minIndex = j;
}
}
temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
// 4, 3, 2, 1삽입 정렬
삽입 정렬은 이미 정렬된 데이터 범위에 정렬되지 않은 데이터를 적절한 위치에 삽입시켜 정렬하는 방식.
빅-세타 : O(n^2)
빅-오 : O(n^2)
// 삽입 정렬, 오름차순
int[] arr = {4, 2, 5, 7, 6, 3, 1, 9, 8, 0};
int n = arr.length;
for (int i = 1; i < n; i++) {
int target = arr[i];
int index = -1;
for (int j = 0; j < i; j++) {
if (arr[j] > target) {
index = j;
break;
}
}
if (index != -1) {
// shift
for (int k = i; k > index; k--) {
arr[k] = arr[k - 1];
}
arr[index] = target;
}
}퀵 정렬
퀵 정렬은 기준값(pivot)을 선정해 해당 값보다 작은 데이터와 큰 데이터로 분류하는 것을 반복해 정렬하는 알고리즘.
기준 값에 따라 시간 복잡도에 많은 영향을 미친다.
빅-세타 : O(nlogn)
빅-오 : O(n^2)
아래는 가장 왼쪽을 피벗으로 지정하는 코드.
투 포인터를 사용한다. (start, end)
1.왼쪽에서 오른쪽으로 가면서 피벗보다 큰 값을 찾는다. (start)
2.오른쪽에서 왼쪽으로 가면서 피벗보다 작은 값을 찾는다. (end)
3.데이터를 찾았다면 두 데이터의 값을 바꾼다.
4.start와 end가 서로를 지나칠때 까지 1~3 을 반복한다.
5.start와 end가 서로를 지나치면 end와 피벗의 값을 바꾼다.
-> 이때 피벗을 기준으로 왼쪽은 피벗보다 작은 값, 오른쪽은 피벗보다 큰 값이 된다.
-> 이렇게 하기 위하여 모든 과정이 있는 것!
6.피벗을 기준으로 좌측 배열과 우측 배열을 1~5 를 반복하여 정렬한다.
/**
* 퀵 정렬
* @param arr 정렬할 배열
* @param start 정렬할 범위의 처음
* @param end 정렬할 범위의 마지막
*/
public static void quickSort(int[] arr, int start, int end) {
int pivot = start; // 피벗 설정, 항상 제일 왼쪽 값으로 설정
int head = start; // start 값은 변하기 때문에 초기값 저장
int tail = end; // end 값도 변하기 때문에 초기값 저장
int temp;
// start와 end는 계속해서 증가하거나 감소하는데 서로를 지나치면 루프를 멈춘다.
while (start < end) {
// start와 end 값은 지정된 범위를 벗어나면 안된다.
// head와 tail 사이에 있어야 한다.
while (start < tail && arr[pivot] >= arr[start]) start++; // 피벗보다 큰 값을 만날때까지 start 증가
while (end > head && arr[pivot] <= arr[end]) end--; // 피벗보다 작은 값을 만날때까지 end 감소
// 여기까지 왔다면 피벗보다 작은 값과 큰값에 대한 인덱스가 설정된 상태
//swap
if (start < end) {
temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
}
}
// 여기까지 왔다면 루프를 빠져나온 상태
// start와 end가 서로 지나친 상태
// end 인덱스의 위치에 피벗값을 넣어준다.
temp = arr[pivot];
arr[pivot] = arr[end];
arr[end] = temp;
// 피벗을 기준으로 왼쪽 데이터 정렬
if (head < end - 1) quickSort(arr, head, end - 1);
// 피벗을 기준으로 오른쪽 데이터 정렬
if (end + 1 < tail) quickSort(arr, end + 1, tail);
}병합 정렬
병합 정렬은 분할 정복(divide and conquer) 방식을 사용해 데이터를 분할하고 분할한 집합을 정렬하며 합치는 알고리즘.
빅-세타 : O(nlogn)
빅-오 : O(nlogn)
/**
* 병합 정렬
* @param arr 정렬할 배열
* @param head 정렬할 배열의 첫번째 인덱스
* @param tail 정렬할 배열의 마지막 인덱스
*/
public void mergeSort(int[] arr, int head, int tail) {
if (head < tail) {
int mid = (head + tail) / 2; // 중간값 설정
mergeSort(arr, head, mid); // 중간값 기준으로 왼쪽
mergeSort(arr, mid + 1, tail); // 중간값 기준으로 오른쪽
// 여기까지 도달했다면 최소 단위로 나누는 작업은 모두 끝남
// 이제 중간 값을 기준으로 좌우 배열을 비교하여 정렬할 차례
int[] temp = new int[arr.length]; // 정렬된 값을 담을 임시 배열
int left = head; // 중앙값 기준으로 왼쪽 배열 첫번째 인덱스
int right = mid + 1; // 중앙값 기준으로 오른쪽 배열 첫번째 인덱스
int index = head; // 정렬된 값을 차례로 넣을 인덱스 설정
while (left <= mid || right <= tail) {
// 아래 조건이 중요
// right > tail : 오른쪽 배열값이 모두 정렬됐다면 왼쪽 값을 차례로 삽입
// left <= mid : right가 tail을 넘어가는 상황도 left가 mid를 넘어가는 상황도 발생하기 때문에 조건을 걸어줌
if (right > tail || (left <= mid && arr[left] <= arr[right])) {
temp[index++] = arr[left++];
} else {
temp[index++] = arr[right++];
}
}
// 임시로 정렬된 값을 실제 배열에 넣어줌
for (int i = head; i <= tail; i++) {
arr[i] = temp[i];
}
}
}기수 정렬
기수 정렬(radix sort)는 값을 비교하지 않는 특이한 정렬.
값을 놓고 비교할 자릿수를 정한 다음 해당 자릿수만 비교.
모든 경우의 시간 복잡도 : O(n)
public static void radixSort(int[] arr) {
Queue<Integer>[] qa = new LinkedList[10];
for (int i = 0; i < 10; i++) {
qa[i] = new LinkedList<>();
}
int jarisu = 1; // 1 -> 10 -> 100 으로 늘어남. 1의자리 10의자리 100의자리.
int max_jarisu = 5; // 숫자의 최대 자리수. ex) 123 -> 3자리, 52344 -> 5자리
for (int i = 0; i < max_jarisu; i++) {
// 자리수를 기준으로 값들을 나누어 담음
for (int j = 0; j < arr.length; j++) {
qa[(arr[j] / jarisu) % 10].add(arr[j]); // 값을 자리수로 나눠서 %10 연산을 하는 것이 핵심!
}
// 자리수로 나누어진 값들을 순서대로 꺼내서 배열에 삽입
for (int j = 0, k = 0; j < arr.length; j++) {
while (qa[k].peek() == null) {
k++;
}
arr[j] = qa[k].poll();
}
jarisu *= 10;
}
}