24.06.22 알고리즘

알고리즘

퀵 정렬(Quick Sort)

• 분할 정복(divide and conquer) 방법을 통해 주어진 배열을 정렬한다.
  • 분할 정복
    • 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다.
• Quick Sort은 불안정 정렬에 속하며, 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다. 또한 Merge Sort는 배열을 비균등하게 분할한다.

과정

1. 배열 가운데서 하나의 원소를 고른다. 이렇게 고른 원소를 피벗(pivot)이라고 한다.
2. 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 배열을 둘로 나눈다. 이렇게 배열을 둘로 나누는 것을 분할(Divide) 이라고 한다. 분할을 마친 뒤에 피벗은 더 이상 움직이지 않는다.
3. 분할된 두 개의 작은 배열에 대해 재귀(Recursion)적으로 이 과정을 반복한다.
   1. 재귀 호출이 한번 진행될 때마다 최소한 하나의 원소는 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있다.

Quick Sort 개선

• 피벗 값이 최솬 최대값으로 지정되어 파티션이 나누어지지 않았을 때, O(n^2)에 대한 시간복잡도를 가진다.
• 즉, 정렬하고자 하는 배열이 오름차순 정렬되어있거나 내림차순 정렬되어있으면 O(n^2)의 시간복잡도를 가진다. 이때, 배열에서 가장 앞에 있는 값과 중간값을교환해준다면 확률적으로나마 시간복잡도를 O(nlogn)으로 개선할 수 있다.

시간복잡도

• 최선의 경우 T(n) = O(nlogn)
• 최악의 경우 T(n) = O(n^2)
• 평균의 경우 T(n) = O(nlogn)

공간복잡도

• 주어진 배열 안에서 교환(swap)을 통해, 정렬이 수행되므로 O(n)이다.

장점

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

단점

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

병합 정렬(Merge Sort)

• 합병 정렬이라고도 부르며, 분할 정복 방법을 통해 구현된다.
• 빠른 정렬로 분류되며, 퀵소트와 함께 많이 언급되는 정렬 방식이다.
• 퀵소트와는 반대로 안정 정렬에 속한다.
• 요소는 분리하고 다시 합병시키면서 정렬해나가는 방식으로, 분리하는 방식은 퀵정렬과 유사하다.
  • Quick Sort : 피벗을 통해 정렬 → 분리
  • Merge Sort : 분리되지 않을 때 까지 분리 → 정렬
• Merge Sort는 순차적인 비교로 정렬을 진행하므로, LinkedList의 정렬이 필요할 때 사용하면 효율적이다.

시간복잡도

• O(nlogn)

공간복잡도

• 병합 정렬이 입력 배열에서 분할 및 정복 방식으로 작동하고 정렬된 후 하위 배열이 다시 병합되기 때문에 공간복잡도는 O(n)이다.

장점

• 병합 정렬은 동일한 값을 가진 요소의 상대적 순서를 유지하므로 안정적인 정렬 알고리즘이며, 대규모 데이터 세트에 효율적이다.
• 병합 정렬은 시간 복잡도가 O(nlogn)이므로 요소 수가 많은 경우에도 성능이 우수하여, 외부 정렬에 적합하다.
• 병합 정렬은 효율적인 병합 기술을 활용하여 외부 데이터 정렬을 처리할 수 있다.

단점

• 병합 정렬은 임시 하위 배열을 저장하기 위해 추가 공간이 필요하므로 메모리가 제한된 환경에는 적합하지 않으며, 작은 데이터 집합에는 가장 효율적이지 않다.
• 병합 정렬은 재귀 호출 및 병합 프로세스에 대한 오버헤드로 인해 작은 데이터 세트의 경우 삽입 정렬 또는 버블 정렬과 같은 다른 정렬 알고리즘보다 효율성이 떨어진다.