버블 < 선택 < 삽입 < 병합 < 퀵 순으로 더 효율적인 알고리즘.
BEST - 이미 정렬되어 있는 배열
WORST - 역순으로 정렬되어 있는 배열
1. 버블정렬 (Bubble Sort)
서로 인접한 두 원소를 검사하여 정렬하는 알고리즘.
0번째 원소와 1번째 원소를 비교하여 정렬.
1번째 원소와 2번째 원소를 비교하여 정렬.
...
n-1번째 원소와 n번째 원소를 비교하여 정렬.
n번째에 있는 원소는 가장 큰 수 이므로 제외되고, 다음 회전에서는 0번째 ~ n-1 번째 원소를 비교하여 정렬한다. 이렇게 n번의 회전을 거치는 알고리즘.
BEST T(n) = O(n^2)
WORST T(n) = O(n^2)
역순으로 주어진 배열에서, 원소가 가장 왼쪽에서 가장 오른쪽으로 이동하기 위해서는 모든 다른 원소들과 교환되어야 한다. 또한, 교환 작업(SWAP)은 세 번의 이동 작업(MOVE)가 필요하기 때문에 더더욱 최악의 알고리즘. 정렬 알고리즘 중에 Run-time 이 가장 오래 걸린다.
2. 선택정렬 (Selection Sort)
배열 중 현재 위치에 맞는 원소를 찾아 선택하여 위치를 교환하여 정렬하는 알고리즘.
0번째 원소 ~ n번째 원소 중 가장 작은 값을 찾아 0번째 인덱스와 SWAP
1번째 원소 ~ n번째 원소 중 가장 작은 값을 찾아 1번째 인덱스와 SWAP
...
n-1번째 원소 ~ n번째 원소 중 가장 작은 값을 찾아 n-1번째 인덱스와 SWAP
BEST T(n) = O(n^2)
WORST T(n) = O(n^2)
3. 삽입정렬 (Insertion Sort)
0번째 원소 ~ 1번째 원소 중 1번째 원소가 들어가야 할 위치를 뒤에서부터 찾아서 삽입
0번째 원소 ~ 2번째 원소 중 2번째 원소가 들어가야 할 위치를 뒤에서부터 찾아서 삽입
...
0번째 원소 ~ n번째 원소 중 n번째 원소가 들어가야 할 위치를 뒤에서부터 찾아서 삽입
뒤에서부터 찾을 때, 삽입될 위치를 찾을 때 까지 비교된 원소는 뒤로 한 칸 씩 MOVE.
BEST T(n) = O(n)
WORST T(n) = O(n^2)
4. 병합정렬 (Merge Sort)
Divide And Conquer 알고리즘 중 하나. 큰 문제를 작은 여러 개의 문제로 쪼개서 해결한 후 결과 모아 원래 문제 해결하는 방법.
[10, 12, 20, 21] 과 [13, 15, 22, 25] 를 병합한다고 해보자.
10과 13 비교 -> [10]
12와 13 비교 -> [10, 12]
20과 13 비교 -> [10, 12, 13]
20과 15 비교 -> [10, 12, 13, 15]
...
BEST T(n) = O(nlogn)
WORST T(n) = O(nlogn)
- 각 합변 단계 연산 O(n) * 순환 깊이 O(logn)
5. 퀵정렬 (Quick Sort)
Divide And Conquer 알고리즘 중 하나.
배열 안의 한 원소를 선택. 이 원소를 pivot 이라고 부른다.
피벗 기준 피벗보다 작은 원소들은 모두 피벗 왼쪽으로, 큰 원소들은 오른쪽으로 옮겨진다.
왼쪽 배열끼리, 그리고 오른쪽 배열끼리 반복해서 수행한다. (배열의 길이가 1보다 같거나 작을 때 까지)
BEST T(n) = O(nlogn)
WORST T(n) = O(n^2)
배열이 계속 불균형하게 나누어지는 경우, 비효율적. 피벗을 중간값으로 선택하는게 좋음
