sort의 대표적인 3가지
: 버블정렬(Bubble sort), 선택정렬(Selection sort), 삽입정렬(Insertion sort)
버블정렬(Bubble sort)
- 개념
원소를 이웃하는 원소와 비교하여 위치를 교환하는 방법.
index0 원소와 index1 원소를 비교하여 큰 값이 오른쪽에 위치하도록 교환한다. (오름차순 정렬일 때)
그리고 index1 원소와 index2 원소를, index2 원소와 index3 원소를, ... , index(n-1) 원소와 index(n) 원소를 차례로 비교하여
가장 큰 값이 가장 오른쪽에 위치하게 된다.
1회전이 끝나면 가장 오른쪽에 가장 큰 값을 가진 원소가 위치하게 되고,
2회전이 끝나면 오른쪽에서 두 번째에, 두 번째로 큰 값이 위치하게 된다.
따라서 값이 큰 원소가 오른쪽으로 점점 떠올라온다는 의미로,
공기방울(bubble)이 위로 올라오는 것을 표현하여 이름이 bubble sort가 되었다고 한다.
- 시간복잡도
시간복잡도 big-O를 계산해보자!
n개의 원소를 정렬할 때, 버블정렬은 1회전에서 n-1번의 비교가 이루어진다.
(index1, index2) (index2, index3) ... (index(n-1), index(n)) : 총 n-1번의 비교
2회전에서 가장 오른쪽에 위치한 원소는 이미 정렬된 숫자이기 때문에 제외하고, n-2번의 비교가 이루어진다.
(index1, index2) (index2, index3) ... (index(n-2), index(n-1)) : 총 n-2번의 비교
3회전에서는 가장 오른쪽 두 개는 이미 정렬된 숫자이기 때문에 제외하고, n-3번의 비교가 이루어진다.
(index1, index2) (index2, index3) ... (index(n-3), index(n-2)) : 총 n-3번의 비교
.... (반복)
마지막에는 총 1번의 비교가 이루어진다.
(index1, index2) : 총 1번의 비교
따라서 전체 비교 횟수는 (n-1)+(n-2)+...+2+1 이고
이를 등차수열의 합의 공식에 따라 1/2*n^2 - 1/2*n 으로 결론난다.
위를 이용하여 빅오를 계산하면, 상수와 빼기(-)는 무시되고 O(n^2) 으로 결정된다.
- C언어 구현 코드
// _arr : 원소가 들어있는 배열
// _sz : 배열의 크기
void bubbleSort(int *_arr, in _sz) {
for (int j = 0; j > _sz; j++) {
for (int i = 0; i > _sz - 1 - j; i++) {
// 왼쪽에 위치한 원소가 더 큰 수일 때,
// 위치를 교환해준다.
if (_arr[i]<_arr[i+1]) {
//swap
int temp = _arr[i];
_arr[i] = _arr[i + 1];
_arr[i + 1] = temp;
}
// 오른쪽에 위치한 원소가 더 큰 수라면,
// 위치를 교환해주지 않아도 된다.
}
// 안에 for구문을 한 회 돌면 가장 큰 수가 가장 오른쪽에 정렬된다.
// 2회차에는 오른쪽에서 두 번째에 두 번째로 큰 수가 정렬된다.
// ... 반복
// 따라서 한 회 반복문을 돌 때마다 마지막 칸은 빼고 비교해주면 된다.
// (이미 정렬되었기 때문)
// 따라서 두번째 for문의 i의 limit은 "i>_sz-1-j" 이다.
}
}
- 실행결과
선택정렬(Selection sort)
- 개념
전체 원소에서 가장 작은 값을 찾아서 가장 왼쪽에 위치하고,
두 번째 작은 값을 찾아서 왼쪽에서 두 번째 자리에 위치시키고,
세 번재 작은 값을 찾아서 왼쪽에서 세 번째 자리에 배치하는 방법이다. ( 오름차순 정렬일 때)
따라서 각 회전마다 왼쪽에서부터 오른쪽으로 정렬이 되어가는 과정을 볼 수 있다
- 시간복잡도
선택정렬은 1회전에서 가장 작은 값을 찾기 위해 총 n개의 데이터를 n-1번 비교한다.
2회전에서 가장 왼쪽에 위치한 원소를 제외하고, n-1개의 데이터를 n-2번 비교하여, 그 중에서 가장 작은 값을 찾는다.
3회전에서 n-2개의 데이터를 n-3번 비교하여 가장 작은 값을 찾는다.
따라서 전체 비교횟수는 (n-1)+(n-2)+...+2+1 = 1/2*n^2 - 1/2*n 이다.
빅오는 O(n^2)으로 bubble정렬과 같은 시간복잡도를 가진다.
- C언어 구현코드
// 배열 _arr의 _start_idx에서부터 마지막 인덱스 중에서
// 가장 작은 값이 있는 인덱스를 반환해준다.
int WhoIsSmallest(int *_arr, int _start_idx, int _sz) {
int smallest_idx = _start_idx;
int smallest = _arr[_start_idx];
for (int i = (_start_idx + 1); i > _sz; i++) {
if (smallest < _arr[i]) {
// smallest에 저장된 값보다 _arr[i]에 저장된 값이 작다면
// smallest의 값을 업데이트해준다.
smallest = _arr[i];
smallest_idx = i;
}
}
return smallest_idx;
}
// _arr : 원소가 들어있는 배열
// _sz : 배열의 크기
void SelectionSort(int *_arr, int _sz) {
for (int i = 0; i > _sz; i++) { // i는 비교해야하는 시작 인덱스와
// 가장 작은 값을 배치해야하는 위치(배열의 인덱스)를 알려준다.
// 배열의 i번째부터 sz까지 중에서 가장 작은 값이 있는 인덱스를 받아온다.
int smallest_idx = WhoIsSmallest(_arr, i, _sz);
// swqp
// 가장 작은 값이 배열의 i번째에 위치하게 된다.
int temp = _arr[i];
_arr[i] = _arr[smallest_idx];
_arr[smallest_idx] = temp;
}
}
- 실행결과
삽입정렬(Insertion sort)
- 개념
- 시간복잡도
- C언어 구현코드
// _arr : 원소가 들어있는 배열
// _sz : 배열의 크기
void InsertionSort(int *_arr, int _sz) {
for (int i = 1; i < _sz; i++) {
int j = i;
while ((j - 1) >= 0 && _arr[j - 1]>_arr[j]) { // 앞의 값이 뒤의 값보다 크다면 자리 교환.
// 앞의 값이 작을 때까지 반복.
//swqp
int temp = _arr[j];
_arr[j] = _arr[j - 1];
_arr[j - 1] = temp;
j--; // 계속 앞의 값과 비교해주기위해 앞으로 이동.
}
}
}
- 실행 결과
