| 정렬이란
- 특정 값을 기준으로 데이터를 순서대로 배치하는 방법
- 기본 : 버블, 삽입, 선택
- 비교적 속도가 빠른 정렬 : 합병, 힙, 퀵, 트리
- 하이브리드 정렬 : 팀, 블록병합, 인트로
- 기타 : 기수, 계수(카운팅), 셸, 보고
| 정렬의 시간복잡도 요약
- 안정성이라는 것은, 어떤 데이터 { 1, 2, 3, 1, 1, 1 } 을 정렬한다고 할 때,
같은 숫자 1에 대해서 { 1, 1, 1, 1 } 의 순서가 유지되도록 정렬되는 것을 '안정성이 있다'라고 한다.
- 아래의 보조 메모리는 추가적으로 드는 메모리를 이야기하는데,
버블이나 삽입, 선택의 경우 swap시에 드는 변수 1개만 필요하기 때문에 보조메모리가 1개만 소요된다.
| 정렬 방법 | 시간 복잡도 | 보조 메모리 | 안정성 | ||
| Ω(n) | Θ(n) | O(n) | |||
| 버블 정렬 | n | n^2 | n^2 | 1 | o |
| 삽입 정렬 | n | n^2 | n^2 | 1 | o |
| 선택 정렬 | n^2 | n^2 | n^2 | 1 | x |
| 합병 정렬 | n logn | n logn | n logn | n | o |
| 힙 정렬 | n logn | n logn | n logn | 1 | x |
| 퀵 정렬 | n logn | n logn | n^2 | logn | x |
| 트리 정렬 | n logn | n logn | n^2 | n | x |
| 기수 정렬 | dn (*d:자릿수) | dn | dn | n+k | o |
| 계수 정렬 | n+k (*k:max) | n+k | n+k | n+k | o |
| 셸 정렬 | n logn | gap에 따라 다름 | n^2 | 1 | x |
| 버블정렬 / 삽입 정렬 / 선택 정렬
// 버블 정렬
public static void bubbleSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
for (int j = 0; j < arr.length - i; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr, j, j + 1);
}
}
}
}
// 삽입 정렬
public static void insertionSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
for (int j = i - 1; j >= 0; j--) {
if (arr[j] > arr[j + 1]) {
swap(arr, j, j + 1);
} else {
break;
}
}
}
}
// 선택 정렬
private static void selectionSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
int min = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[min]) {
min = j;
}
}
swap(arr, i, min);
}
}
| 합병정렬 / 힙 정렬 / 퀵 정렬 / 트리 정렬
1. 합병정렬
public static void mergeSort(int[] arr, int[] tmp, int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
mergeSort(arr, tmp, left, mid);
mergeSort(arr, tmp, mid + 1, right);
merge(arr, tmp, left, right, mid);
}
}
public static void merge(int[] arr, int[] tmp, int left, int right, int mid) {
int lCursor = left;
int rCursor = mid + 1;
int idx = left;
while (lCursor <= mid || rCursor <= right){
if (lCursor <= mid && rCursor <= right) {
if (arr[lCursor] <= arr[rCursor]) {
tmp[idx++] = arr[lCursor++];
}else {
tmp[idx++] = arr[rCursor++];
}
} else if (lCursor <= mid && rCursor > right) {
tmp[idx++] = arr[lCursor++];
} else {
tmp[idx++] = arr[rCursor++];
}
}
for (int i = left; i <= right; i++) {
arr[i] = tmp[i];
}
}2. 힙 정렬
public static void heapSort(int[] arr) {
// 가장 끝의 자식이 있는 부모노드를 잡아서 최대힙구조로 정렬
for (int i = arr.length / 2 - 1; i >= 0; i--) {
heapify(arr, i, arr.length);
}
// 가장 앞의 노드가 최대값임을 이용하여 나머지 정렬
for (int i = arr.length - 1; i > 0; i--) {
swap(arr, 0, i);
heapify(arr, 0, i);
}
}
public static void heapify(int[] arr, int parentIdx, int size) {
int leftIdx = parentIdx * 2 + 1;
int rightIdx = parentIdx * 2 + 2;
int maxIdx = parentIdx;
if (leftIdx < size && arr[maxIdx] < arr[leftIdx]) {
maxIdx = leftIdx;
}
if (rightIdx < size && arr[maxIdx] < arr[rightIdx]) {
maxIdx = rightIdx;
}
if (maxIdx != parentIdx) {
swap(arr, parentIdx, maxIdx);
heapify(arr, maxIdx, size);
}
}
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}3. 퀵 정렬
- pivot 값은 처음값이거나 중앙값이 될 수 있다. (상황에 맞게 선택하면 된다)
- 퀵 정렬은 pivot을 기준으로 좌우 정렬을 하고, pivot의 양 옆을 다시 분할하여 정렬하는 것을 반복한다.
public static void quickSort(int[] arr, int left, int right) {
// 탈출문
if (left >= right) {
return;
}
// 피봇값 지정
int pivot = partition(arr, left, right);
// 피봇값의 좌우를 다시 퀵소트
quickSort(arr, left, pivot - 1);
quickSort(arr, pivot + 1, right);
}
public static int partition(int[] arr, int left, int right) {
// 피봇값과 양 옆의 커서를 지정
int pivot = arr[left];
int lCursor = left;
int rCursor = right;
// 1. 양 끝의 커서가 서로 같기 전까지
// 우측은 피봇값보다 더 작은 값을 찾고
// 좌측은 피봇값보다 같거나 더 큰 값을 찾아 swap
// 2. 양 끝의 커서가 서로 같아지면
// 한쪽 커서와 피봇을 swap
while (lCursor < rCursor) {
while (arr[rCursor] > pivot && lCursor < rCursor) {
rCursor--;
}
while (arr[lCursor] <= pivot && lCursor < rCursor) {
lCursor++;
}
swap(arr, lCursor, rCursor);
}
swap(arr, left, lCursor);
return lCursor;
}
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}4. 트리 정렬
- 이진탐색트리를 만들어 정렬하는 방식으로, 알고리즘 복잡도는 NlogN이다.
- 이 부분은 비선형구조 > 이진탐색트리 포스팅에 적은 AVL, Red-Black을 확인해주세요.
| 기수 정렬 / 계수 정렬 / 셸 정렬
1. 기수 정렬
- 기수 : 자릿수를 의미한다.
- 기수정렬 : 일의 자리, 십의 자리, 백의 자리.. 순으로 각 자릿수에 해당되는 수를 큐에 담은 후 기존 배열에 넣는 방식
public static void radixSort(int[] arr) {
// 각 자리에 큐를 담은 배열
ArrayList<Queue<Integer>> list = new ArrayList<>();
for (int i = 0; i < 10; i++) { // 10진수 기준으로 자리 수 0 ~ 9
list.add(new LinkedList<>());
}
// 최대 자릿수
int maxLen = getMaxLen(arr);
// 나누는 수
int div = 1;
// 배열에 넣어줄 인덱스
int idx = 0;
// 기수 정렬에 대한 반복문
for (int i = 0; i < maxLen; i++) {
// 해당 자릿수의 큐에 데이터를 추가
for (int j = 0; j < arr.length; j++) {
list.get((arr[j] / div) % 10).offer(arr[j]);
}
// 해당 자릿수의 큐를 가져와서, 기존 배열(arr)에 넣는다.
for (int j = 0; j < 10; j++) {
Queue<Integer> queue = list.get(j);
while (!queue.isEmpty()) {
arr[idx++] = queue.poll();
}
}
// 그 다음 자릿수를 위한 준비작업
idx = 0;
div *= 10;
}
}
// 데이터의 최대 자릿수 반환
public static int getMaxLen(int[] arr) {
int maxLen = 0;
for (int i = 0; i < arr.length; i++) {
int len = (int)Math.log10(arr[i]); // 자릿수
if (maxLen < len) {
maxLen = len;
}
}
return maxLen;
}2. 계수 정렬
- 계수 : 관계가 있는 수, 상수를 의미한다.
- 계수정렬 : 상수 data 수열에서 최대값 + 1을 size로 배열에 생성해, 카운트한 후 다시 기존 배열에 넣는 방식
public static void countingSort(int[] arr) {
// 최댓값의 + 1 만큼 배열을 잡아둔다
int max = Arrays.stream(arr).max().getAsInt();
int[] cntArr = new int[max + 1];
// 숫자데이터에 해당되는 인덱스의 cnt를 하나 늘린다.
for (int i = 0; i < arr.length; i++) {
cntArr[arr[i]]++;
}
// cntArr을 한바퀴씩 돌면서 기존 배열(arr)에 해당 인덱스의 갯수만큼 삽입
int idx = 0;
for (int i = 0; i < cntArr.length; i++) {
while (cntArr[i] > 0) {
arr[idx++] = i;
cntArr[i] -= 1;
}
}
}
//최댓값 하나만 너무 크면 비효율적 -> HashMap을 통해 보완할 수 있다
public static void countingSort2(int[] arr) {
// key : data, value : 갯수
HashMap<Integer, Integer> map = new HashMap<>();
for (int item : arr) {
map.put(item, map.getOrDefault(item, 0) + 1);
}
// key를 배열에 담아서 정렬한 후, 기존 배열(arr)에 해당인덱스의 갯수만큼 다시 삽입한다.
ArrayList<Integer> keyList = new ArrayList<>(map.keySet());
Collections.sort(keyList);
int idx = 0;
for (int key : keyList) {
int cnt = map.get(key);
while (cnt > 0) {
arr[idx++] = key;
cnt--;
}
}
}3. 셸 정렬
- 삽입 정렬을 보완한 형태로
- 삽입 정렬은 idx 1부터 arr.length-1까지 처음부터 좌측의 데이터를 확인했다면
- 셸 정렬은 간격을 두고 간격의 거리만큼 떨어진 데이터를 확인하는 것을 반복한다.
- 이렇게 하게 되면 기존의 삽입 정렬 보다는 교환 횟수가 감소할 수 있다.
public static void shellSort(int[] arr) {
// 초기 gap을 설정
int gap = arr.length / 2;
// 더 이상 간격이 없을 때까지 간격을 /2한다.
for (int g = gap; g > 0; g /= 2) {
// 초기 간격부터 간격의 길이만큼 증가하면서
for (int i = g; i < arr.length; i++) {
// 지정된 위치의 좌측 간격들의 데이터를 비교 & 교환한다.
int tmp = arr[i]; // 짚은 데이터를 tmp에 넣고
int j = 0; // 짚은 데이터의 좌측 데이터들을 확인
for (j = i - g; j >= 0; j -= g) {
// 큰 값이 나오면 좌측 데이터들을 하나씩 당긴다
if (arr[j] > arr[j + g]) {
arr[j + g] = arr[j];
} else {
break;
}
}
arr[j + g] = tmp;
}
}
}
[ 출처 ]
- 부트캠프 강의를 듣고 정리한 내용입니다.
'Computer Science > Algorithm' 카테고리의 다른 글
| [알고리즘] 탐색 - DFS, BFS, 이진 탐색 (0) | 2022.08.25 |
|---|---|
| HashSet<int[]>와 Hashset<ArrayList<Integer>> (0) | 2022.08.17 |
| [알고리즘] 알고리즘 개요 (0) | 2022.08.09 |
| [백준 11660] 구간 합 구하기 5 (0) | 2022.07.14 |
| [백준 17609] 회문 (팰린드롬) (0) | 2022.07.13 |
