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!!
Bubble sort(버블 정렬)
Insertion sort(삽입 정렬)
Selection sort(선택 정렬)
Heap sort(힙 정렬)
Quick sort(퀵 정렬)
merge 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;
}
}
}
}
}
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;
}
}
}
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을 이용한 정렬 방법이다. 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() + " ");
}
}
insertion sort를 사용하고, 비교할 것이 많아지면 quick sort를 사용도록 구현되어 있다고 한다. 알고리즘의 아이디어는 D&Q 즉, 분할정복을 이용한 방법이다.pivot보다 큰 index(left 변수)를 찾는다, 동시에 오른쪽에서부터 값이 pivot보다 작은 index(right 변수)를 찾는다.(left <= right)(left > right)일 때까지 2.을 반복한다.(left > right)(left == right)인 상황에서 탈출하여 분기하면 겹치는 영역이 발생하여 계속 분기하기 된다.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);
}
}
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];
}
}
}