Basic Sorting Algorithms
기본적인 정렬 알고리즘에 대해 알아보자
목차
Bubble sort(버블 정렬)
Selection sort(선택 정렬)
Insertion sort(삽입 정렬)
Heap sort(힙 정렬)
Quick sort(퀵 정렬)
merge sort(병합 정렬)
- Bubble sort (거품 정렬)
· 시간 복잡도: 평균과 최악의 경우 O(N^2), 최선의 경우 O(N)
· 방법은 오른쪽으로 i와 i + 1번 째를 비교하면서 뒤로 제일 큰 것을 이동시키는 것이다.
· 최선의 경우는 스와핑이 한번도 일어나지 않는 경우이다.
· 이름의 유래는 아래 이미지를 90도 회전시켜서 볼 경우 위로 올라가는 것이 거품과 같다하여 붙여진 이름이다.
public class BubbleSort {
static int[] data = {14, 6, 45, 43, 41, 28, 38, 36, 49, 16, 34};
public static void main(String[] args) {
bubbleSort();
for (int i = 0; i < data.length; i++) {
System.out.print(data[i]);
if (i < data.length - 1) System.out.print(" ");
}
}
public static void bubbleSort() {
boolean isSwapped;
for (int i = 0; i < data.length; i++) {
isSwapped = false;
for (int j = 1; j < data.length - i; j++) {
if (data[j] < data[j - 1]) {
int tmp = data[j - 1];
data[j - 1] = data[j];
data[j] = tmp;
isSwapped = true;
}
}
if (!isSwapped) break;
}
}
}
- selection sort(선택 정렬)
· 시간 복잡도: 평균과 최악과 최선 모든 경우 O(N^2)
· 방법은 i와 j(i + 1 ~ array.length - 1)를 비교하여 위치를 변경하여 작은 값을 왼쪽으로 보내는 것이다.
· 이 경우, 최선의 경우도 O(N)인데, 그 이유는 i와 비교하는 대상이 j이기 때문에, 다음 i와의 상관 관계가 없기 때문이다.
public class SelectionSort {
static int[] data = {14, 6, 45, 43, 41, 28, 38, 36, 49, 16, 34};
public static void main(String[] args) {
selectionSort();
for (int i = 0; i < data.length; i++) {
System.out.print(data[i]);
if (i < data.length - 1) System.out.print(" ");
}
}
public static void selectionSort() {
for (int i = 0; i < data.length - 1; i++) {
for (int j = i + 1; j < data.length; j++) {
if (data[i] > data[j]) {
int tmp = data[i];
data[i] = data[j];
data[j] = tmp;
}
}
}
}
}
- Insertion sort(삽입 정렬)
· 시간 복잡도: 평균과 최악의 경우 O(N^2), 최선의 경우 O(N)
· 방법은 0번 째 인덱스가 아니라 1번 째 인덱스부터 시작하여 이전 값들을 확인하여, 자신의 적절한 위치를 확인하여 삽입한다.
· 최선의 경우는 입력이 정렬되어있는 경우이다. 이 이유는 이전 값들을 확인할 때 자신의 위치를 바로 찾고 탈출하기 때문이다.
public class InsertionSort {
static int[] data = {14, 6, 45, 43, 41, 28, 38, 36, 49, 16, 34};
public static void main(String[] args) {
insertionSort();
for (int i = 0; i < data.length; i++) {
System.out.print(data[i]);
if (i < data.length - 1) System.out.print(" ");
}
}
public static void insertionSort() {
for (int i = 1; i < data.length; i++) {
int tmp = data[i], here = i - 1;
for (int j = i - 1; j > -1; j--) {
if (data[j] > tmp) data[j + 1] = data[j];
else {
here = j + 1;
break;
}
}
data[here] = tmp;
}
}
}
- Heap sort(힙 정렬)
· 시간 복잡도: 평균과 최악과 최선 모든 경우 O(NlogN)
· Heap의 원리로 작동한다.
·
import java.util.PriorityQueue;
import java.util.Queue;
public class HeapSort {
static int[] data = {6, 5, 3, 1, 8, 7, 2, 4};
static Queue priorityQueue = new PriorityQueue();
public static void main(String[] args) {
for (int i = 0; i < data.length; i++) {
priorityQueue.add(data[i]);
}
heapSort();
}
public static void heapSort() {
while (!priorityQueue.isEmpty()) System.out.print(priorityQueue.poll() + " ");
}
}
- Quick sort(퀵 정렬)
· 시간 복잡도: 평균과 최선의 경우 O(NlogN), 최악의 경우 O(N^2)
· 퀵 정렬은 Java에서도 library에 구현될 정도로 일반적으로 많이 사용하는 정렬 방법이다.
· Java의 Arrays.sort()에서는 배열의 크기가 작을 때는 내부적으로 insertion sort를 사용하고, 비교할 것이 많아지면 quick sort를 사용도록 구현되어 있다고 한다.
· 방법은 D&C 즉, 분할정복을 이용한 방법이다.
· 최악의 경우는 입력으로 주어진 배열이 정렬이 되어있고, pivot을 첫 번째 인덱스로 선택할 때 발생한다. 그 이유는 left는 pivot보다 무조건 크기 때문에 1번째 인덱스에 멈춰있고, right가 n번의 비교를 통해 0이되면 한 라운드가 종료된다. 마치 selection sort처럼 진행하게 된다.
1.pivot을 정한다. (여기서는 중간 값)
2.왼쪽에서부터 값이 pivot보다 큰 index(left 변수)를 찾는다, 동시에 오른쪽에서부터 값이 pivot보다 작은 index(right 변수)를 찾는다.
3.case1 - (left <= right)
Swapping을 하고, (left > right)일 때까지 2.을 반복한다.
3.case2 - (left > right)
반복문을 탈출하여 분기한다.
✔︎ 왜 같을 때도 Swapping을 하는가? (left == right)인 상황에서 탈출하여 분기하면 l ~ right, left ~ r, 로 각각 분기하는데
겹치는 영역(right, left)이 발생하여 첫 번째 분기점에서 실행되어 arr[right]인 지점의 값이 변경되고, 이후 두 번째 분기에서 arr[left]의 값이 변경되면 sorting 의 결과가 이상해지고, 무한 calling이 발생한다.
if (left < right) swap 인 경우
예제) arr = [14, 6, 45, 43, 41]
pivot = 45, left = 0, right = 4;
do while안의 while을 각각 실행 후,
left = 4, right = 4
스왑 안하고 탈출한다면, l ~ right인 분기를 또 타게 된다.
public class QuickSort {
static int[] data = {14, 6, 45, 43, 41, 28, 38, 36, 49, 16, 34};
public static void main(String[] args) {
quickSort(data, 0, data.length - 1);
for (int i = 0; i < data.length; i++) {
System.out.print(data[i]);
if (i < data.length - 1) System.out.print(" ");
}
}
public static void quickSort(int[] arr, int l, int r) {
int left = l, right = r;
int pivot = arr[(l + r) / 2];
do{
while (arr[left] < pivot) left++; // find index that higher than pivot
while (arr[right] > pivot) right--;// find index that lower than pivot
if (left <= right) {
int tmp = arr[left];
arr[left] = arr[right];
arr[right] = tmp;
left++;right--;
}
}while (left < right);
if (l < right) quickSort(arr, l, right);
if (r > left) quickSort(arr, left, r);
}
}
- merge sort(병합 정렬)
· 시간 복잡도: 평균과 최악과 최선 모든 경우 O(N^2)
· 방법은 D&C의 아이디어를 사용하여 배열을 나눴다가 합치는 방식으로 진행한다.
· 장점은 제한된 메모리 환경에서 병합정렬을 사용할 수 있다는 점이다.
· 단점은 제자리에서 교체하는 방법 in-place sorting이 아닌 배열만큼의 공간을 더 사용하기 때문에 공간 복잡도가 다른 정렬에 비해 높다.
public class MergeSort {
static int[] sortedArray = new int[11];
public static void main(String[] args) {
int[] data = {14, 6, 45, 43, 41, 28, 38, 36, 49, 16, 34};
mergeSort(data, 0, data.length - 1);
for (int i = 0; i < sortedArray.length; i++) {
System.out.print(sortedArray[i]);
if (i < sortedArray.length - 1) System.out.print(" ");
}
}
public static void mergeSort(int[] arr, int m, int n) {
int mid;
if (m < n) {
mid = (m + n) >> 1;
mergeSort(arr, m, mid);
mergeSort(arr, mid + 1, n);
merge(arr, m, mid, n);
}
}
public static void merge(int[] arr, int m, int mid, int n) {
int i = m, j = mid + 1, k = m;
while (i <= mid && j <= n) {
sortedArray[k] = (arr[i] <= arr[j]) ? arr[i++] : arr[j++];
k++;
}
int start = (i > mid) ? j : i, end = (i > mid) ? n : mid;
for (int t = start; t <= end; t++, k++) {
sortedArray[k] = arr[t];
}
for (int t = m; t <= n; t++) {
arr[t] = sortedArray[t];
}
}
}
일반적으로 퀵소트와 머지소트가 비교되는데 배열을 사용하는 경우라면 퀵소트를 리스트를 사용하는 경우라면 머지소트를 사용하는 것이 좋다.
그 이유는 퀵소트는 인덱스를 이용하여 정렬을 하고, 머지소트는 리스트를 쪼개서 정렬을 하기 때문이다.
마지막으로 stable & unstable sort에 대해서 정리를 해보자.
stable: 같은 값을 가진 i, j가 sort 전 후 위치가 서로 바뀌지 않는 경우.
unstable: 같은 값을 가진 i, j가 sort 전 후 위치가 서로 바뀌는 경우.
stable: bubble, insertion, merge
unstable: selection, heap, quick
이미지 출처: https://cdn-images-1.medium.com