[Algorithms] Sort Special - Inserting, Counting, Quick, Heap

Inserting Sort

  - N 크기의 배열

  - 두 번째 index부터 시작해서, 앞 부분에 자신보다 작은 값이 있을 때까지 지나가는 값을 (현재 위치+1)로 이동시킴

  - 시간복잡도 O(N^2)

 

 

Counting Sort

  - N 크기의 배열, K 크기의 배열 (counting 용도)

  - 배열 내 각 값들의 개수를 counting → counting된 array를 누적해가며 index 계산 → N 크기 배열 순회하며 배치

  - 시간복잡도 O(N+K)

  - reference) http://www.cs.miami.edu/home/burt/learning/Csc517.091/workbook/countingsort.html

 

 

Quick Sort

  - N 크기의 배열

  - Divide and Conquer 방법

  - 과정 (왼쪽 pivot 기준)

    1. 리스트 내 가장 왼쪽 요소를 pivot으로 지정함.

    2. 리스트 내 pivot을 제외하고 (pivot+1)에서 부터 pivot보다 크면 정지 (왼쪽에서 오른쪽으로 진행)

    3. 리스트 내 pivot을 제외하고 (last index in list)에서 부터 pivot작으면 정지 (오른쪽에서 왼쪽으로 진행)

    4. 2, 3번 과정에서 선택된 원소를 서로 교체하고, 다시 2번부터 진행함.

       - 이 과정에서 좌우에서 진행되는 index가 서로 교차할 때 정지.

    5. 교차 지점과 pivot 교환 후 pivot의 왼쪽 리스트와 오른쪽 리스트를 각각 다시 1번 과정부터 진행함.

  - 시간복잡도 O(NlogN)

    → 최악의 경우는 이미 정렬된 리스트이거나 역순으로 정렬된 리스트 (시간복잡도 O(N^2)

    → 이러한 문제를 해결하기 위해 중간값 퀵정렬이 있음.

 

 

Median of Three Quick Sort

  - 과정

    1. first index, middle index, last index에 대한 sort 진행

    2. middle index의 값을 pivot으로 지정함.

    3. Quick sort 진행

  - 장점

    - 이미 정렬되어 있거나 유사한 상황에서 최대한 중간 값으로 pivot을 선정하여, 

      pivot을 기준으로 최대한 비슷한 크기로 이분 파티셔닝을 하기 위함

  

 

Heap Sort

  - Max heap tree 또는 min heap tree를 구성해 정렬하는 방법

  - 시간복잡도 O(NlogN)

  - 과정

    1. data가 입력되면 우선 tree의 마지막에 붙인다.

    2. parent node의 값과 비교해가며, 계속해서 위치 변경