6. 삽입정렬, 퀵정렬, 병합정렬, 기수정렬

p. 113~143(6, 7일차)

강의:  04-3, 04-6

---

1. 삽입정렬

- 이미 정렬된 데이터 범위에 정렬되지 않은 데이터를 적절한 위치에 삽입 시켜 정렬하는 방법

- O(n²)으로 느린 편이지만 구현하기 쉽다

✔ 수행 과정

- 현재 index에 있는 데이터 값을 선택한다.

- 삽입될 위치를 탐색한다.

- index에 있는 위치까지 shift 연산을 수행한다.

- 전체 데이터의 크기만큼 index가 커질 때까지 반복 (index++ 연산 수행)

 

✔ 핵심 이론

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

 

✔백준 11399번 - ATM 인출 시간 계산하기

 

 

 

2. 퀵정렬

- 기준값을 선정해 해당 값보다 작은 데이터와 큰 데이터로 분류하는 것을 반복해 정렬을 하는 알고리즘

- 기준값이 어떻게 선정되는지에 따라 시간복잡도에 영향을 줌 O(nlogn) ~ O(n²)

 

---

3. 병합정렬 * 코테자주 등장

-  총 3번 만에 정렬된 데이터가 나옴 = 2³ =log8

- 분할정복 방식을 사용해 데이터를 분할하고 분할한 집합을 정렬하며 합치는 알고리즘

 

✔2개의 그룹을 병합하는 과정

- 투포인터 개념을 사용하여 왼쪽, 오른쪽 그룹을 병합

- 왼포와 오포의 값을 비교하여 작은 값을(오름차순 기준) 배열에 추가하고

   포인터를 오른쪽으로 1칸 이동시킴

 

4. 기수정렬 * 원리 이해하기

일의 자리로 먼저 정렬 > 정렬된 데이터 > 십의 자리로 정렬

- 값을 비교하지 않는 특이한 정렬

- 자릿수를 정한 다음 해당 자릿수만 비교

- O(kn), k=자릿수