1. 버블 정렬
인접한 원소를 비교한 다음, 내가 원하는 정렬이 아니다! 하면 교환.
처음부터 마지막까지 쌍 비교.
이렇게.. n-1개의 쌍을 비교하면, 가장 큰 애는 가장 끝으로 이동하게 됨.
그 후, n-2개의 쌍(젤 큰 애는 비교 안 함. 이미 제자리임.)을 비교하면, 두 번째로 큰 애가 가장 큰 애의 옆으로 위치하게 됨.
즉, (n-1)+(n-2)+...+(1) = n(n-1)/2 번 비교.
2. 선택 정렬
우선, 주어진 배열에서 최댓값 찾아서 맨 뒤로 보냄.
최댓값 뺀 나머지 배열에서 최댓값 찾아서 맨 뒤에서 한 칸 앞으로 보냄.
이런 식으로 진행되는 건데, 계속 교체하진 않으므로 버블 정렬보단 효율적.
3. 삽입 정렬
얘는 우선 1번째 원소부터 비교를 시작한다.
0번째 원소와 비교해서, 1번째 원소의 위치를 정함.
그다음 2번째 원소를 0, 1번째 원소를 보며 그 중 어디에 넣을지 결정.
3번째 원소는 0, 1, 2번째 원소를 보며 어디에 넣을지 결정.. 이런 식으로
삽입정렬은 선형 시간에 실행됨.
만약 배열이 이미 많이 정렬돼있다면.. 정말 빠르게 정렬할 수 있음.
4. 쉘 정렬
5. 합병 정렬(merge sort)
두 개의 정렬된 배열을 갖고, 최솟값끼리 비교해서 더 작은 걸 먼저 배열에, 더 큰 걸 나중에 배열에 넣음.
그리고 그 다음 최솟값끼리 비교해서 또..
6. 퀵 정렬
배열 안의 한 요소를 선택해서 그 요소를 기준으로 작은 애들을 왼쪽 배열에, 큰 애들을 오른쪽 배열에 넣음
각각을 순환호출하여 정렬하면 됨.
7. 힙 정렬
내림차순 정렬하려면, 부모노드가 항상 자식노드보다 큰 최대힙을 사용하면 되고,
오름차순은 최소힙 사용.
그냥.. 정렬해야할 원소들을 최대(최소)힙 트리로 만들고 그걸 순서대로 적으면 정렬
8. 계수 정렬 == 카운팅 정렬
각 수가 얼마나 나왔는지 빈도를 따져서 이를 다시 배열로 만드는 기법.
ex) 0~5까지의 수가 있다면
배열 1 5 1 4 3 0 1 0 3 1
숫자 0 1 2 3 4 5
빈도 2 4 0 2 1 1
누적 2 6 6 8 9 10 (정렬될 배열의 인덱스)
원래 배열의 뒤 값부터 보면서 정렬될 배열을 채움.
값이 1이면 누적배열의 index 1 값을 보고 그 자리에 원래 배열의 값을 채우고, 누적 배열의 값을 1 감소시킴.
배열 1 5 1 4 3 0 1 0 3 1
인덱스 0 1 2 3 4 5 6 7 8 9 10
정렬배열 1
누적 배열 1 6 6 8 9 10
배열 1 5 1 4 3 0 1 0 3 1
인덱스 0 1 2 3 4 5 6 7 8 9 10
정렬배열 1 3
누적 배열 1 6 6 7 9 10
배열 1 5 1 4 3 0 1 0 3 1
인덱스 0 1 2 3 4 5 6 7 8 9 10
정렬배열 0 1 3
누적 배열 0 6 6 7 9 10
이런 식으로.. 됨
빠르긴 한데,
배열에 어떤 수가 있는지를 알아야 함.
