Quick_Sort

Quick sort with Hungarian, folk dance

Merge_Sort

Merge-sort with Transylvanian-saxon (German) folk dance.flv

Quick Sort (퀵 정렬) python으로 구현하기

분할정복 (Divide and Conquer)

• 문제 해결을 위한 알고리즘 디자인 패러다임 중 하나
  • 복잡한 문제를 작은 단위로 나누고(Divide)
    • 전체를 분해해서 비슷한 크기/ 유형의 작은 문제로 나눔
    • 재귀적으로 호출하며 연산의 단위를 줄여 나간다.
  • 해결(Conquer)한 다음, 그 결과를 이용해서
    • 하위 문제를 재귀적으로 해결(Base Case를 설정해야함)
  • 전체 문제를 해결하며 병합(Merge)하는 방법이다.
    • 하위 문제를 합쳐가며 전체 문제를 해결
• 조건
  • 서브문제로 분할 할 수 있는가 ?
  • 답을 병합(조합)해서 본 문제를 해결하는 것이 효율적인가 ?
• 재귀 vs 분할정복
  • 공통점 : 복잡한 큰 문제를 작은 단위로 나눠서 해결하는 접근법
  • 차이점
    • 재귀호출 : 같은 함수를 재호출 해서 base case와 나머지로 나눈다.
    • 분할정복 : 동일한 비율로 나눠서 비슷한 작업을 다시 수행 같은 함수가 아닐 수도 있다.
      • 분할 정복의 방법중 하나가 재귀

재귀를 사용하지 않고 분할정복하는 예시

반복문으로 퀵 정렬 구현하기

퀵 정렬과 병합 정렬

• 퀵 정렬은 분할(Divide), 병합정렬은 병합(Marge)과정에 더 집중되어있다.
• Quick Sort
  • ‘[Less than pivot] [pivot] [greater than pivot]’ 형태가 되도록 나눈 (파티션) 후, 피벗의 왼쪽과 오른쪽을 정렬한다.
    • 분할 : 기준이 되는 피벗을 선택 후 파티션
    • 정복 : 피벗을 기준으로 왼쪽과 오른쪽 요소들을 각각 재귀적으로 정렬
    • 결합 : 아무것도 하지 않음으로써 결합. 정복단계에서 이미 재귀적으로 정렬이 된 상태
  • 시간복잡도 : 평균O(nlogn), 최악 O(N^2)
• Merge Sort
  • 리스트를 최대한 작게 나눠주고, 그 안에서 swap해서 정렬 후 다시 합치며 정렬
    • 분할 : 리스트 / 배열을 반으로 분할
    • 정복 : 분할단계에서 만들어진 각각 하위 배열을 재귀적으로 정렬
    • 결합 : 정렬된 두 하위 배열들을 하나의 배열에 합병
      • 이 과정에서 별도의 메모리가 필요하다.

Stable vs Unstable

• 불안정 정렬 : 중복 원소의 지리가 정렬 이후에 바뀔 수 있다.
  • 선택정렬 , 퀵정렬
• 안정 정렬 : 데이터가 중복되더라도 영향을 덜 받는다.
  • 버블정렬, 삽입정렬, 병합정렬

제자리정렬(in-place)