5일차 정리(버블정렬, 단순선택정렬, 단순삽입정렬, 셀정렬)

- 내부 정렬 : 정렬한 모든 데이터를 하나의 배열에 저장할 수 있는 경우에 사용하는 알고리즘

- 외부 정렬 : 정렬할 데이터가 너무 많아서 하나의 배열에 저장할 수 없는 경우에 사용하는 알고리즘

- 정렬 알고리즘의 핵심 요소 : 교환, 선택, 삽입이며 대부분의 정렬 알고리즘은 이 세 가지 요소를 응용한것

1. 버블정렬(bubble sort) : 이웃한 두 요소의 대소관계를 비교하여 교환을 반복

2. 단순 선택 정렬(straight selection sort) : 가장 적은 요소부터 선택해 알맞은 위치로 옮겨서 순서대로 정렬하는 알고리즘

3. 단순 삽입 정렬(straight insertion sort) : 선택한 요소를 그보다 더 앞쪽의 알맞은 위치에 '삽입하는' 작업을 반복하여 정렬하는 알고리즘
- 시간복잡도 $O(n^2)$ 입니다.(효율이 나쁨)

- 특징)

 A. 정렬을 마쳤거나 정렬을 마친 상태에 가까우면 정렬 속도가 매우 빨라집니다(장점)

 B. 삽입할 위치가 멀리 떨어져 있으면 이동(대입)해야 하는 횟수가 많아집니다(단점)

4. 셸 정렬

- 도널드 셸(D. L. Shell)이 제안 : 먼저 정렬한 배열의 요소를 그룹으로 나눠 각 그룹별로 단순 삽입 정렬을 수행하고, 그 그룹을 합치면서 정렬을 반복하여 요소의 이동 횟수를 줄이는 방법

- 셀 정렬의 시간 복잡도는 $O(n^{1.25})$ 그러나 이 알고리즘도 멀리 떨어져 있는 요소를 교환해야 하므로 안정적이지 않다.

- h는 그룹을 몇개로 쪼갤지를 결정하는데 너무 크면 효과가 없기 때문에 코드에서는 요솟수 n을 9로 나눈 값을 넘지 않도록 정함