📌 Sorting

리스트를 어떤 순서에 따라 배열하는 것 - 오름차순, 내림차순, 알파벳 순 ,, 등등

✔️ Internal sorting
주기억장치에서 다룰 수 있는 크기의 데이터를 다루는 기존의 Sorting

✔️ External sorting
입력 크기가 너무 커서 보조 기억 장치에 저장할 수 밖에 없는 상태에서 Sorting 하는 것
예를 들어 주기억장치가 크기가 1GB고 데이터의 크기가 100GB면 주기억장치에 ❌
어떤 Internal 정렬 알고리즘으로도 직접 정렬할 수는 없어 보조기억장치(HDD,SDD)를 이용해야 한다.
그러면 입력을 분할해 주기억장치가 수용 가능한 만큼의 데이터에 대해 내부 정렬을 수행하고 다시 이를 저장하는 방법을 반복하여, 점진적으로 크기를 늘려나가는 방식을 고려해야 한다.

Internal Sorting

1. Insertion sort

• Sorting된 리스트로 시작
• 인서트 하기 위해서 리스트를 탐색 후 알맞은 위치를 찾아서 그 위치에 인서트
  

🚀 Performance : O(n^2)

• n = 비어있거나 기존의 정렬되어있는 목록에 넣어야 할 새로운 키의 수
• 현재 정렬된 목록에서 새 키의 올바른 위치를 검색하기 위한 시간
• 새 키를 저장할 공간을 확보하기 위해 현재 정렬된 목록에서 더 큰 키를 이동해야 하는 시간

✅ 최선은 O(n) : 모두 정렬이 되어있는 경우

✅ 최악의 경우는 O(n^2) : 역순으로 정렬되어 있을 때
(n-1) + (n-2) + .... + 2 + 1 => n(n-1)/2

✔️ 짧은 리스트에는 간단하고 좋음
✔️ 이미 대부분 sort되어 있으면 좋음
= 최선의 경우
한번씩 밖에 비교를 안하므로 O(n) 의 시간복잡도를 가지게 된다. 또한, 이미 정렬되어 있는 배열에 자료를 하나씩 삽입/제거하는 경우에는, 현실적으로 최고의 정렬 알고리즘이 되는데, 탐색을 제외한 오버헤드가 매우 적기 때문이다.

2. Selection sort

• 해당 순서에 원소를 넣을 위치는 정해져 있고 어떤 원소를 넣을지 선택하는 알고리즘
• Insertion sort랑 좀 다른데 Selection은 배열에서 해당 자리를 선택하고 그 자리에 오는 값을 선택한다고 생각하면 편하다.
  

🚀 Performance : O(n^2)

데이터의 개수가 n개라고 했을 때,

• 첫 번째 회전에서의 비교횟수 : 1 ~ (n-1) => n-1
  두 번째 회전에서의 비교횟수 : 2 ~ (n-1) => n-2
  ...
  ▶️ (n-1) + (n-2) + .... + 2 + 1 => n(n-1)/2

n개의 주어진 배열을 정렬하는데 O(n^2) 만큼의 시간이 걸린다.
최선, 평균, 최악의 경우 시간복잡도는 O(n^2) 으로 동일하다.

✔️ 장점

• 알고리즘이 단순하다.
• 정렬을 위한 비교 횟수는 많지만, Bubble Sort에 비해 실제로 교환하는 횟수는 적기 때문에 많은 교환이 일어나야 하는 자료상태에서 비교적 효율적이다.
• 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않는다. => 제자리 정렬(in-place sorting)

✔️ 단점

• 시간복잡도가 O(n^2)으로, 비효율적이다.
• 불안정 정렬(Unstable Sort) 이다. = 중복된 값이 입력 순서와 동일하게 저장이 되지 않는 정렬

3. Bubble sort

• 서로 인접한 두 원소의 크기를 비교하고 조건에 맞지 않으면 자리를 교환해서 정렬
  

🚀 Performance : O(n^2)

(n-1) + (n-2) + (n-3) + .... + 2 + 1 => n(n-1)/2이므로, O(n^2) 이다.
또한, Bubble Sort는 정렬이 돼있던 안돼있던, 2개의 원소를 비교하기 때문에 최선, 평균, 최악의 경우 모두 시간복잡도가 O(n^2) 으로 동일하다.

✔️ 장점

• 구현이 굉장히 간단하고 직관적이다.
• Selection sort와 마찬가지로 in-place sorting임
• stable sort이다

✔️ 단점

• 시간복잡도가 O(n^2)으로, 굉장히 비효율적이다.
• 교환이 너무 많이 일어난다.

4. Merge sort

• Divide and Conquer를 사용해서 구현함
  = 큰 문제를 작은 문제로 분할하여 해결하는 방식
• 이미 정렬된 리스트를 머지함
• 얘도 Stable sort임!
  
  이미 합병의 대상이 되는 두 영역이 각 영역에 대해서 정렬이 되어있기 때문에 단순히 두 배열을 순차적으로 비교하면서 정렬할 수가 있다.

🚀 Performance : O(nlog₂n)

• 순차적인 비교로 정렬을 진행하므로 링크드리스트의 정렬이 필요할 때 사용하면 효율적이라고 함.

5. Quick sort

• Divide and Conquer를 사용해서 구현함
• JAVA에서 Arrays.sort()에 사용되는 알고리즘!

✅ Quick sort vs Merge sort

• Quick sort : 우선 피벗을 통해 정렬 (partition) => 영역을 쪼갬 (quick sort)

  • 임의 접근
  • 배열을 비균등하게 분열

• Merge sort : 영역을 쪼갤 수 있는 만큼 쪼갬 (merge sort) => 정렬 (merge)

  • 순차 접근
  • 배열을 균등하게 분열

✅ 프로세스

1. 배열 가운데서 하나의 원소를 고른다. 이렇게 고른 원소를 피벗(pivot) 이라고 한다.

• 피벗은 가장 처음 원소, 마지막 원소, 중간에 있는 원소중에 고름

2. 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 배열을 둘로 나눈다. 이렇게 배열을 둘로 나누는 것을 분할(Divide) 이라고 한다. 분할을 마친 뒤에 피벗은 더 이상 움직이지 않는다.

3. 분할된 두 개의 작은 배열에 대해 재귀(Recursion)적으로 이 과정을 반복한다.

• 재귀 호출이 한번 진행될 때마다 최소한 하나의 원소는 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있다.

✅ 코드

• 입력 배열을 피벗을 기준으로 비균등하게 2개의 부분 배열 (피벗을 중심으로 왼쪽 : 피벗보다 작은 요소들, 오른쪽 : 피벗보다 큰 요소들) 로 분할한다.

public int partition(int[] array, int left, int right) {
    /**
    // 최악의 경우, 개선 방법
    //정렬하고자 하는 배열이 오름차순 정렬되어있거나 내림차순 정렬되어있으면 O(n^2)의 시간복잡도를 가진다. 
    //이때, 배열에서 가장 앞에 있는 값과 중간값을 교환해준다면 확률적으로나마 시간복잡도 O(nlog₂n)으로 개선할 수 있다. 
    //하지만, 이 방법으로 개선한다해도 Quick Sort의 최악의 시간복잡도가 O(nlog₂n)가 되는 것은 아니다.
    
    int mid = (left + right) / 2;
    swap(array, left, mid);
    */
    
    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;
    
    return i;
}

• 부분 배열을 정렬한다.

public void quickSort(int[] array, int left, int right) {
    if(left >= right) return;
    
    // 분할 
    int pivot = partition(); 
    
    // 피벗은 제외한 2개의 부분 배열을 대상으로 순환 호출
    quickSort(array, left, pivot-1);  // 정복(Conquer)
    quickSort(array, pivot+1, right); // 정복(Conquer)
}

🚀 Performance : Θ(nlog₂n)

📌 최선의 경우

• 비교 횟수 : log₂n
  레코드의 개수 n이 2의 거듭제곱이라고 가정(n=2^k) 했을 때, n=2^3의 경우, 2^3 -> 2^2 -> 2^1 -> 2^0 순으로 줄어들어 순환 호출의 깊이가 3임을 알 수 있다.
  

이것을 일반화하면 n=2^k의 경우, k(k=log₂n) 임 을 알 수 있다.

• 각 순환 호출 단계의 비교 연산 : n
  각 순환 호출에서는 전체 리스트의 대부분의 레코드를 비교해야 하므로 평균 n번 정도의 비교가 이루어진다.

따라서, 최선의 시간복잡도는 순환 호출의 깊이 * 각 순환 호출 단계의 비교 연산 = nlog₂n 가 된다. 이동 횟수는 비교 횟수보다 적으므로 무시할 수 있다.

📌 최악의 경우 : 정렬하고자 하는 배열이 오름차순이나 내림차순으로 정렬되어 있는 경우

• 비교 횟수 : n
  

레코드의 개수 n이 2의 거듭제곱이라고 가정(n=2^k)했을 때, 순환 호출의 깊이는 n 임을 알 수 있다.

• 각 순환 호출 단계의 비교 연산 : n
  각 순환 호출에서는 전체 리스트의 대부분의 레코드를 비교해야 하므로 평균 n번 정도의 비교가 이루어진다.

따라서, 최악의 시간복잡도는 순환 호출의 깊이 * 각 순환 호출 단계의 비교 연산 = n^2 다. 이동 횟수는 비교 횟수보다 적으므로 무시할 수 있다.

📌 평균의 경우 : T(n) = O(nlog₂n)

✔️ 장점

• 불필요한 데이터의 이동을 줄이고 먼 거리의 데이터를 교환할 뿐만 아니라, 한 번 결정된 피벗들이 추후 연산에서 제외되는 특성 때문에, 시간 복잡도가 O(nlog₂n)를 가지는 다른 정렬 알고리즘과 비교했을 때도 가장 빠르다.
• 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않는다.

✔️ 단점

• 불안정 정렬(Unstable Sort) 이다.
• 정렬된 배열에 대해서는 Quick Sort의 불균형 분할에 의해 오히려 수행시간이 더 많이 걸린다.

참조 : https://gyoogle.dev/blog/algorithm/Quick%20Sort.html