(오름차순 기준)
단순 선택 정렬
- 가장 작은 요소부터 선택해 알맞은 위치로 옮겨서 순서대로 정렬하는 알고리즘
- 과정
- 아직 정렬하지 않은 부분에서 가장 작은 키의 값(a[min])을 선택
- a[min]과 아직 정렬하지 않은 부분의 첫 번째 요소를 교환
- 이 과정을 n - 1회 반복
void selection(int a[], int n)
{
int i, j;
for (i = 0; i < n - 1; i++) {
int min = i;
for (j = i + 1; j < n; j++)
if (a[j] < a[min])
min = j;
swap(int, a[i], a[min]);
}
}
- 요솟값 비교 횟수 : (n^2 - n) / 2회
- 서로 떨어져 있는 요소를 교환하는 것이기 때문에 안정적이지 않음 (같은 값을 가진 두 요소의 순서가 뒤바뀌는 등)
- 시간 복잡도 : O(n^2)
단순 삽입 정렬
- 선택한 요소를 그보다 더 앞쪽의 알맞은 위치에 삽입하는 작업을 반복하여 정렬하는 알고리즘
- 두 번째 요소부터 진행
- 과정
- 아직 정렬되지 않은 부분의 첫 번째 요소를 정렬된 부분의 알맞은 위치에 삽입
- 위 과정을 n - 1회 반복
void insertion(int a[], int n)
{
int i, j;
for (i = 1; i < n; i++) {
int tmp = a[i];
for (j = i; j > 0 && a[j - 1] > tmp; j--)
a[j] = a[j - 1];
a[j] = tmp;
}
}
- 요솟값 비교 횟수 n^2 / 2회
- 떨어져 있는 요소들이 서로 뒤바뀌지 않아 안정적임
- 시간 복잡도 : O(n^2)