[D-24] 정렬 - 삽입 & 퀵

📍 삽입 정렬

✅ 정의

정렬된 데이터 범위에 정렬되지 않은 데이터를 적절한 위치에 삽입시켜 정렬하는 방식
시간복잡도 O(n^2)
구현 방법은 쉬운 편이다.

삽입 정렬 (insertion sort)

✅ 핵심 이론

현재 정렬된 데이터 범위 내에서 적절한 위치에 삽입하는 것이 핵심이다.

✅ 정렬 과정

1. 현재 index에 있는 데이터 값을 선택한다.
2. 현재 선택한 데이터가 정렬된 데이터 범위에 삽입될 위치를 탐색한다.
3. 삽입 위치부터 index에 있는 위치까지 shift 연산을 수행한다.
4. 삽입 위치에 현재 선택한 데이터를 삽입하고 index++ 연산을 수행한다.
5. 전체 데이터의 크기만큼 index가 커질 때까지, 즉 선택할 데이터가 없을 때까지 반복한다.

✅ shift 연산 (삽입 정렬)

배열이나 리스트에서 특정 값을 이동시키는 과정을 말한다.
즉, 값을 한 칸씩 오른쪽(또는 왼쪽)으로 밀어내는 작업을 뜻한다.
ex. [3, 1, 4, 5]라는 리스트가 주어질 경우, 첫번째 값(3)을 기준으로 정렬을 시작한다.
두 번째 값이 1을 넣으려고 할 때, 3이 1보다 크므로 3을 오른쪽으로 한 칸 밀고, 1을 첫 번째 자리에 넣는다.
이때, 3을 오른쪽으로 밀고, 1을 빈 자리에 넣는 과정이 바로 shift 연산이다.

📍 퀵 정렬

✅ 정의

기준값(pivot)을 선정해 해당 값보다 작은 데이터와 큰 데이터로 분류하는 것을 반복해 정렬하는 알고리즘이다.
기준값 선정 방식에 따라 시간 복잡도에 많은 영향을 미친다.
평균적인 시간 복잡도는 O(nlogn)이다.

✅ 핵심 이론

pivot을 중심으로 계속 데이터를 2개의 집합으로 나누면서 정렬하는 것이 핵심이다.

✅ 정렬 과정

1. 데이터를 분할하는 pivot을 설정한다(아래 그림의 경우 가장 왼쪽 끝을 pivot으로 설정).
2. pivot을 기준으로 다음 a~e 과정을 거쳐 데이터를 2개의 집합으로 분리한다.
   2-a) low가 가리키는 데이터가 pivot이 가리키는 데이터보다 작으면 low를 오른쪽으로 1칸 이동한다.
   2-b) high가 가리키는 데이터가 pivot이 가리키는 데이터보다 크면 high를 왼쪽으로 1칸 이동한다.
   2-c) low가 가리키는 데이터가 pivot이 가리키는 데이터보다 크고,
   high가 가리키는 데이터가 pivot이 가리키는 데이터보다 작으면
   low, high가 가리키는 데이터를 swap하고 low는 오른쪽, high는 왼쪽으로 1칸씩 이동한다.
   2-d) low와 high가 만날 때까지 2-a ~2-c를 반복한다.
   2-e) low와 high가 만나면 만난 지점에서 가리키는 데이터와 pivot이 가리키는 데이터를 비교하여
   pivot이 가리키는 데이터가 크면 만난 지점의 오른쪽에, 작으면 만난 지점의 왼쪽에 pivot이 가리키는 데이터를 삽입한다.
3. 분리 집합에서 각각 다시 pivot을 선정한다.
4. 분리 집합이 1개 이하가 될 때까지 과정 1~3을 반복한다.