It is just my opinion, so don't you attack me. please!
But if this posting has some incorrect informations, you comment about that
Please!!
Basic Sorting Alogrithms
Bubble sort(버블 정렬)
Insertion sort(삽입 정렬)
Selection sort(선택 정렬)
Heap sort(힙 정렬)
Quick sort(퀵 정렬)
merge sort(병합 정렬)
- Bubble sort (거품 정렬)
· 거품 정렬은 내가 알고리즘 시간에 처음 접했고, 쉽다고 생각했던 정렬이다. 이 녀석의 시간 복잡도는O(N^2)즉, 반복문 2개로 정렬을 할 수 있다. 로직은 현재 값에서 다음 값과 비교하여 현재 값이 크다면 서로 위치를 바꿔주는 것이다. 이 행위를 N번 반복한다.
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() {
for (int i = 0; i < data.length; i++) {
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;
}
}
}
}
}
여담이지만, 거품 정렬이 왜 거품정렬일까?
위 이미지를 왼쪽으로 90도 회전시키면 위로 올라가는 모양이 된다. 그래서 거품이 올라가는 형상같다고하여 Bubble sort라고 이름이 붙은 것이다.
- Insertion sort(삽입 정렬)
· 삽입 정렬은index = 1부터 시작한다. 일단 임시 변수에현재 index에 해당하는 값을 저장하고,index - 1~0까지 중에 알맞은 위치를 찾아서 삽입한다. 삽입 정렬은 이미 정렬이 되어있다면O(N)의 복잡도를 갖는다. 그 이유는 이전 값들을 보면서 삽입을 해야하는데, 바로 제 위치를 찾기 때문이다. 하지만 시간 복잡도는 보통의 경우 Bic-O,O(N^2)의 복잡도를 갖는다.
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;
}
}
}
- selection sort(선택 정렬)
· 선택 정렬은 내가 알고리즘 수업을 듣기 전부터 알고 있던 정렬 방법이다. 로직은 굉장히 단순하다. 현재 index에 맞는 값을 찾는 과정인데, 이전 값은 보지 않고index + 1~array.length - 1까지 중에 제일 작은 값을 찾는다. 시간 복잡도는O(N^2)를 갖는다.
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;
}
}
}
}
}
- Heap sort(힙 정렬)
· 힙 정렬은 자료구조인Heap을 이용한 정렬 방법이다.Heap에 대해서 모른다면 원리를 모르겠지만,heapify과정을 통해 시간 복잡도를O(NlgN)까지 낮춘 정렬 방법이다. (곧,Heap에 대한 정리도 할 예정이다, 밑의 코드는Priority큐를 이용하여 구현.)
import java.util.PriorityQueue;
import java.util.Queue;
public class HeapSort {
static int[] data = {14, 6, 45, 43, 41, 28, 38, 36, 49, 16, 34};
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(퀵 정렬)
· 퀵 정렬은 Java에서도 library에 구현될 정도로 일반적으로 많이 사용하는 정렬 방법이다. Java의 Arrays.sort()에서는 배열의 크기가 작을 때는 내부적으로insertion sort를 사용하고, 비교할 것이 많아지면quick sort를 사용도록 구현되어 있다고 한다. 알고리즘의 아이디어는D&Q즉, 분할정복을 이용한 방법이다.
솔직히 밑의 이미지를 봐도 잘 이해되지 않는다. 어떻게 저렇게 움직이는지... 그래서 코드로 보는 것을 추천한다.
1.pivot을 정한다.
2.왼쪽에서부터 값이pivot보다큰index(left 변수)를 찾는다, 동시에 오른쪽에서부터 값이pivot보다작은index(right 변수)를 찾는다.
3.case1 -(left <= right)
Swapping을 하고,(left > right)일 때까지 2.을 반복한다.
3.case2 -(left > right)
반복문을 탈출하여 분기한다.
✔︎ 왜 같을 때도 Swapping을 하는가?(left == right)인 상황에서 탈출하여 분기하면겹치는 영역이 발생하여 계속 분기하기 된다.
4.두 개의 재귀로 분할 되는데,left가right보다 크므로left~r(현재 함수에서 배열의 끝)까지,l(현재 함수에서 배열의 처음)~right으로 분할되어야 한다.
시간 복잡도는 최악의 경우O(N^2)의 복잡도를 갖지만 평균적으로는O(NlgN)의 복잡도를 갖는다.
위에서 언급한 최악의 경우는정렬이 되어있는 배열을 정렬하려고할 때 발생한다. 그 이유는 첫번 째 인덱스의 값을pivot으로 결정한 경우,left는 계속첫번 째index에 있게 되고,right는 계속 비교하면서첫 번째index까지 와야한다. 따라서 한번의 라운드에n번의 비교를 해야하기 때문에O(N^2)이라는 시간 복잡도가 발생한다. 따라서 보통은pivot을 배열의중간에 있는 값으로 결정하거나,랜덤하게 결정하는 경우도 있다.
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(병합 정렬)
· 병합 정렬은 역시D&Q의 아이디어를 사용한 정렬 방법이다. 정렬할 배열을 반으로 쪼개면서 좌우 배열을 계속해서 분할한 후 각 배열 내에서 정렬을 한 후 다시 합치는 과정을 통해 정렬하는 알고리즘이다. 시간 복잡도는O(NlogN)을 갖는다. 하지만 단점은 제자리에서 교체하는 방법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];
}
}
}
(위의 이미지들의 출처: https://cdn-images-1.medium.com )