쉽게 배우는 알고리즘 3장 요약

3장 정렬

1. 선택정렬
배열에서 가장 큰 원소를 찾아 이 원소와 배열의 맨 끝자리에 있는 원소와 자리를 바꾼다. 이렇게 하면 가장 큰 수가 배열의 제일 마지막에 오게 되고 이 원소는 자리를 찾은 셈이 된다. 이제 나머지 원소를 가지고 앞에서 사용한 방법을 반복하면 된다.

2. 버블 정렬
선택정렬처럼 제일 큰 원소를 끝자리로 옮기는 작업을 반복한다. 다만 제일 큰 원소를 오른쪽으로 옮기는 방법이 다르다. 왼쪽부터 이웃한 수를 비교하면서 순서가 제대로 되어 있지 않으면 하나하나 바꾸어 나간다.

3. 삽입 정렬
이미 정렬되어 있는 i개짜리 배열에 하나의 원소를 더 더하여 정렬된 i+1개짜리 배열을 만드는 과정을 반복한다.
배열이 거의 정렬되어 있는 상태로 입력되는 경우에는 가장 매력적인 알고리즘이 된다.

4. 병합정렬
입력을 반으로 나눈다. 이렇게 반으로 나눈 전반부와 후반부를 독립적으로 정렬한다. 마지막으로 정렬된 두 부분을 합쳐서 정렬된 배열을 얻는다.

5. 퀵정렬
배열에서 기준원소를 하나 고른다.(랜덤 또는 맨뒤) 이 기준원소를 중심으로 작거나 같은수는 왼쪽으로 큰수는 오른쪽으로 재배치한다. 이렇게 분할된 왼쪽부분과 오른쪽 부분을 따로 정렬한다.
기준 원소 고르기: 맨 앞 vs 맨 뒤 vs 랜덤

6. 힙정렬
(최소힙)
- 먼저 주어진 배열을 힙으로 만든다. 그런 다음, 힙에서 가장 작은 값을 차례로 하나씩 제거하면서 힙의 크기를 줄여나간다(원소 제거후 힙의 성질을 만족하도록 수선하는 과정이 필요). 정렬순서는 힙에서 원소들이 제거된 순서대로이다.

- 힙: 이진트리로서 맨 아래 층을 제외하고는 완전히 채워져 있고 맨 아래층은 왼쪽부터 꽉 채워져 있다.
힙의 모든 노드는 다음의 힙성질을 만족한다. - 각 노드의 값은 자신의 자식의 값보다 작다.

- 힙으로 만드는 방법
  * 링크나 포인터 같은 것을 쓰지 않고도 배열을 써서 간단하게 구현할 수 있음.
  * 원소를 배열에 넣는다 -> 배열의 중간(n/2, 자식이 있는 제일 마지막 원소)에서 부터 힙의 성질을 만족하도록 수선 시작 -> 두 자식 중 작은 값과 비교하여 자식이 작으면 값을 교환 -> 이와 같은 식으로 루트까지 수선한다.

7. 기수정렬
처음에는 가장 낮은 자리수만 가지고 모든 수를 배열한다. 그 다음에는 두번째로 낮은 자리수만 가지고 모든 수를 배열한다. 이렇게 가장 높은 자리수까지를 반복한다. 이때 안정성을 유지하면서 정렬한다.
입력이 모두 k 이하의 자리수를 가진 자연수인 특수한 경우에 사용

8. 계수정렬
배열의 원소를 훑어보고 1부터 k까지의 자연수가 각각 몇번 나타나는지를 센다. 이 정보가 있으면 배열의 각 원소가 몇 번째에 놓이면 되는지를 계산해낼 수 있다.

9. 위의 정렬들에 대한 Haskell 구현
https://github.com/spriteye/learn-algorithm/blob/master/haskell/Sort.hs