버블 정렬(Bubble Sort)

인접한 두 숫자를 비교해서 변경하는 방법
오른쪽부터 최대값/최소값을 정렬해 나가는 방식

public void BubbleSort(int[] num) {
    for (int i = 0; i < num.length; i++) {
        for (int j = 1; j < num.length - i; j++) {
            if (num[j] < num[j - 1]) swap(j - 1, j, num);
        }
    }
}

선택 정렬(Selection Sort)

자신보다 뒤에있는 숫자들 중 가장 작은 숫자를 발견해서 맨 앞에서부터 채우는 정렬
왼쪽부터 최대값/최소값을 정렬해 나가는 방식

public void SelectionSort(int[] num) {
    for (int i = 0; i < num.length; i++) {
        int min = i;
        for (int j = i + 1; j < num.length; j++) {
            if (num[min] > num[j]) min = j;
        }
        if (num[min] < num[i]) swap(min, i, num);
    }
}

삽입 정렬(Insertion Sort)

i번째 배열 값부터 앞으로 탐색하며 자신보다 작다면 swap하는 정렬
n번째 수행시 n번째 까지 정렬되는 방법

public void InsertioinSort(int[] num) {
    for (int i = 1; i < num.length; i++) {
        int tmp = num[i];
        for (int j = i - 1; j >= 0; j--) {
            if (tmp < num[j]) {
                num[j + 1] = num[j];
                num[j] = tmp;
            }
        }
    }
}

퀵 정렬(Quick Sort)

pivot을 정하고 pivot 좌/우를 정렬하면서 전체 배열을 정렬
자바에서 Arrays.sort를 사용하변 내부는 Quick Sort로 구현되어있다.
평균 O(nlogn) 이지만 최악에 O(n^2) 이므로 데이터가 많은 경우 조심해야 한다.
최악의 경우란 아이러니하게도 정렬된 경우를 의미한다.

< 작동 방식 >

pivot을 가운데 값으로 설정하고 Left, Right 를 각 끝의 idx를 지정한다.

num[left] > pivot, num[right] < pivot 조건을 만족할 때까지 left, right를 움직인다.

둘의 위치를 바꾼다. 이렇게 되면 pivot 왼쪽에는 pivot보다 작은 값, 오른쪽에는 큰값이 정렬된다.

< 소스 코드 >

public int partition(int left, int right, int[] num) {
    int pivot = num[(left + right) / 2];
    while (left <= right) {
        while (num[left] < pivot) left++;
        while (num[right] > pivot) right--;
        if (left <= right) {
            swap(left, right, num);
            left++;
            right--;
        }
    }
    return left;
}
 
public void QuickSort(int left, int right, int[] num) {
    if (left < right) {
        int pivot = partition(left, right, num);
        if (left < pivot - 1) QuickSort(left, pivot - 1, num);
        if (right > pivot) QuickSort(pivot, right, num);
    }
}

합병 정렬(Merge Sort)

합병 정렬은 O(nlogn) 의 시간복잡도를 보장한다.
단점은 임시 배열 공간이 추가로 필요하다는 점이다.
분할 정복으로 구현하는데 배열을 최대한 나누고, 합병하면서 값을 비교해 정렬하는 방식이다.

< 작동 방식 >

left = start, right = mid+1로 설정하고 서로 비교해 작은 값을 data에 덮어씌운다.
left를 한칸 이동하고 작은 값을 data에 덮어씌운다.
right를 한칸 이동하고 작은 값을 data에 덮어씌운다.
right가 배열의 끝에 도달했기 때문에 남은 left를 data에 덮어씌운다.

< 소스 코드 >

public void mergeSort(int start, int end) {
    if (start < end) {
        int mid = (start + end) / 2;
        mergeSort(start, mid);
        mergeSort(mid + 1, end);
        merge(start, mid, end);
    }
}

public void merge(int start, int mid, int end) {
    for (int i = start; i <= end; i++) {
        tmp[i] = num[i];    //tmp 배열에 값을 옮긴다.
    }
    int left = start;
    int right = mid + 1;
    int idx = start;
    while (left <= mid && right <= end) {
        //num 배열에 비교하면서 저장
        if (tmp[left] >= tmp[right]) {
            num[idx++] = tmp[right++];
        } else {
            num[idx++] = tmp[left++];
        }
    }
    //어느 한쪽에 남은 tmp 배열을 num 배열에 저장
    while (left <= mid) num[idx++] = tmp[left++];
    while (right <= end) num[idx++] = tmp[right++];
}