거품 정렬(Bubble Sort)

1. 1회전에 첫 번째 원소와 두 번째 원소를, 두 번째 원소와 세 번째 원소를, 세 번째 원소와 네 번째 원소를, … 이런 식으로 마지막-1 번째 원소와 마지막 원소를 계속해서 비교하여 매번 앞의 원소가 뒤의 원소보다 더 크다면(오름차순 정렬일 때) 서로 교환한다.
2. 1회전을 수행하고 나면 가장 큰 원소가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 원소는 정렬에서 제외되고, 2회전을 수행하고 나면 끝에서 두 번째 원소까지는 정렬에서 제외된다. 이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어난다.

특징

• 시간복잡도: O(n^2)
• 제자리 정렬(in-place sorting)
• 안정 정렬(Stable Sort)

출처: https://gyoogle.dev/blog/algorithm/Bubble%20Sort.html

선택 정렬(Selection Sort)

1. 주어진 배열 중에 최소값의 위치를 찾는다.
2. 그 값을 맨 앞에 위치한 값과 교체한다. (pass)
3. 맨 처음 위치를 뺀 나머지 배열을 같은 방법으로 교체한다.

특징

• 시간복잡도: O(n^2)
• 정렬을 위한 비교 횟수는 많지만, Bubble Sort에 비해 실제로 교환하는 횟수는 적기 때문에 많은 교환이 일어나야 하는 자료상태에서 비교적 효율적
• 제자리 정렬(in-place sorting)
• 불안정 정렬(Unstable Sort)

출처: https://gyoogle.dev/blog/algorithm/Selection%20Sort.html

삽입 정렬(Insertion Sort)

1. 첫 번째 원소 앞(왼쪽)에는 어떤 원소도 갖고 있지 않기 때문에, 두 번째 위치(index)부터 탐색을 시작한다. temp에 임시로 해당 위치(index)의 값을 저장하고, prev에는 해당 위치(index)의 이전 위치(index-1)를 저장한다.

• 배열 {1, 2, 4, 7, 8, 6} 에서 마지막 6를 정렬해야 하는 상황이라면 temp에 6을 저장하고 prev에 4를 저장

2. prev가 음수가 되지 않고 prev의 값이 temp의 값보다 크다면, prev+1의 값에 prev의 값을 옮기고 prev를 더 이전 위치를 가리키도록 한다. prev의 값이 temp보다 작을 때까지 이를 반복하면 prev에는 temp보다 작은 값들 중 제일 큰 값의 위치를 가리키게 되어 prev+1의 자리에 temp를 저장한다.

• 8(prev의 값)은 6보다 크므로 8을 prev+1 위치(5)에 저장하고 prev를 1 감소시킨다 // {1, 2, 4, 7, 8, 8}
• 7(prev의 값)은 6보다 크므로 7을 prev+1 위치(4)에 저장하고 prev를 1 감소시킨다 // {1, 2, 4, 7, 7, 8}
• 4(prev의 값)는 6보다 작으므로 prev+1에 temp를 저장하고 반복문을 종료 // {1, 2, 4, 6, 7, 8}

3. '1'번으로 돌아가 다음 위치(index+1)의 값을 temp에 저장하고, 반복한다.

특징

• 시간복잡도: O(n^2)
• 제자리 정렬(in-place sorting)
• 안정 정렬(Stable Sort)
• Selection Sort나 Bubble Sort과 같은 O(n^2) 알고리즘에 비교하여 상대적으로 빠름
• 대부분의 원소가 이미 정렬되어 있는 경우에 매우 효율적: Selection Sort는 k+1번째 요소를 찾기 위해 나머지 모든 요소들을 탐색하지만 Insertion Sort는 k+1번째 요소를 배치하는 데 필요한 만큼의 요소만 탐색

출처: https://gyoogle.dev/blog/algorithm/Insertion%20Sort.html

퀵 정렬(Quick Sort)

1. 하나의 값을 뽑고 그 값보다 작은 것은 왼쪽으로, 큰 것은 오른쪽으로 위치시킨다.

int pivot = array[left]; // 가장 왼쪽값을 피벗으로 설정
int i = left, j = right;
while(i < j) {
        while(pivot < array[j]) {
            j--;
        }
        while(i < j && pivot >= array[i]){
            i++;
        }
        swap(array, i, j);
    }
array[left] = array[i];
array[i] = pivot;

2. 뽑은 값을 기준으로 왼쪽과 오른쪽으로 분할하여 각각에서 재귀(Recursion)적으로 1번의 작업을 반복한다.

특징

• 최선의 경우 시간복잡도: O(nlog₂n)
• 최악의 경우 시간복잡도: O(n^2) - 오름차순/내림차순으로 정렬되어있을 때
• 평균의 경우 시간복잡도: O(nlog₂n)
• 제자리 정렬(in-place sorting)
• 불안정 정렬(Unstable Sort)
• 정렬된 배열에 대해서는 Quick Sort의 불균형 분할에 의해 오히려 수행시간이 더 많이 걸림
• 불필요한 데이터의 이동을 줄이고 먼 거리의 데이터를 교환할 뿐만 아니라, 한 번 결정된 피벗들이 추후 연산에서 제외되는 특성 때문에, 시간 복잡도가 O(nlog₂n)를 가지는 다른 정렬 알고리즘과 비교했을 때도 가장 빠름
• 퀵정렬은 순차 접근이 아닌 임의 접근이기 때문에 LinkedList를 정렬하는 것은 성능이 좋지 않음: LinkedList는 삽입, 삭제 연산에서 유용하지만 접근 연산에서는 비효율적이기 때문
• JAVA에서 Arrays.sort() 내부적으로도 Dual Pivot Quick Sort로 구현되어 있을 정도로 효율적인 알고리즘

출처: https://gyoogle.dev/blog/algorithm/Quick%20Sort.html

병합 정렬(Merge Sort)

1. 요소를 쪼갠다.

public void mergeSort(int[] array, int left, int right) {
    if(left < right) {
        int mid = (left + right) / 2;
        
        mergeSort(array, left, mid);
        mergeSort(array, mid+1, right);
        merge(array, left, mid, right);
    }
}

2. 다시 크기 순서대로 병합하는 과정을 재귀적으로 반복한다.

public static void merge(int[] array, int left, int mid, int right) {
    int[] L = Arrays.copyOfRange(array, left, mid + 1);
    int[] R = Arrays.copyOfRange(array, mid + 1, right + 1);
    
    int i = 0, j = 0, k = left;
    int ll = L.length, rl = R.length;
    
    while(i < ll && j < rl) { // 가장 작은 값부터 순서대로 배치
        if(L[i] <= R[j]) {
            array[k] = L[i++];
        }
        else {
            array[k] = R[j++];
        }
        k++;
    }
    
    // remain
    while(i < ll) {
        array[k++] = L[i++];
    }
    while(j < rl) {
        array[k++] = R[j++];
    }
}

특징

• 시간복잡도: O(nlog₂n)
• 안정 정렬(Stable Sort)
• 병합 정렬은 순차적인 비교로 정렬을 진행하므로, LinkedList의 정렬이 필요할 때 사용하면 효율적
• 퀵정렬과의 차이점

  퀵 정렬 : 우선 피벗을 통해 정렬(partition) → 영역을 쪼갬(quickSort)
  병합 정렬 : 영역을 쪼갤 수 있을 만큼 쪼갬(mergeSort) → 정렬(merge)

출처: https://gyoogle.dev/blog/algorithm/Merge%20Sort.html