버블 정렬
배열의 2개의 아이템을 선택하고 비교해서 왼쪽이 오른쪽보다 크면 swap.
최악의 경우 모든 아이템을 스왑해야 한다.
시간 복잡도 : O(n^2)
❗시간 복잡도는 빠르고 느리다 개념이 아닌 스텝이라고 생각하자.
#include <iostream>
#include <vector>
using namespace std;
vector<int> bubble_sort(vector<int> target) {
int num = target.size(); // 7
int temp;
int cnt = 1;
for (int i = 0; i < num - 1; i++) {
for (int j = 0; j < num - i - 1; j++) {
if (target[j] > target[j + 1]) { // 해당 인덱스 오른쪽과 비교해서 큰 값을 오른쪽 배치
temp = target[j]; // temp = 55
target[j] = target[j + 1]; //0 인덱스 = 53
target[j + 1] = temp; // 1인덱스 = 55
}
}
cout << cnt << "회전 : ";
cnt++;
// 정렬 결과 출력
for (int c = 0; c < num; c++) {
cout << target[c] << " "; // << : 출력 연산자
}
cout << endl;
}
return target;
}
int main(void) {
vector<int> target = { 55, 53, 81, 34, 12, 70, 17 }; // int를 원소로 갖는 vector 생성하고 초기화
int num = target.size();
auto result = bubble_sort(target);
// 최종 정렬 결과 출력
cout << endl;
cout << "최종 : ";
for (int i = 0; i < num; i++) {
cout << result[i] << " ";
}
return 0;
}결과
선택 정렬
배열에서 최솟값을 찾아 0번 인덱스부터 순차적으로 위치를 지정한다. (매번 사이클마다 1번의 스왑만 하면 됨)
올바른 위치라면 스왑하지 않는다.
시간 복잡도 : O(n^2)
#include <stdio.h>
#define SWAP(x, y, temp) ((temp)=(x), (x)=(y), (y)=(temp)) // x, y 값 교환 매크로
#define MAX_SIZE 5
void selection_sort(int list[], int n) {
int i, j, least, temp;
// 마지막 숫자는 자동으로 정렬되기 때문에 (숫자 개수-1)만큼 반복
for (i = 0; i < n - 1; i++) {
least = i;
// 최솟값 탐색
for (j = i + 1; j < n; j++) {
if (list[j] < list[least])
least = j;
}
// 최솟값이 자기 자신이면 자리 이동하지 않음
if (i != least) {
SWAP(list[i], list[least], temp);
}
}
}
void main() {
int i;
int n = MAX_SIZE;
int list[5] = { 9, 6, 7, 3, 5 };
// 선택 정렬 수행
selection_sort(list, n);
// 정렬 결과 출력
for (i = 0; i < n; i++) {
printf("%d ", list[i]);
}
}결과
삽입 정렬
인덱스 1부터 시작해 해당 인덱스의 값이 왼쪽값보다 작으면 왼쪽으로 이동하면서 계속 비교하다가 왼쪽 값보다 더 클 때 멈추고, 다음 인덱스도 동일하게 비교 반복한다. 인덱스 0은 이미 정렬된 것으로 볼 수 있다.
삽입 정렬은 필요한 아이템만 스캔하므로 선택정렬보다 빠르다. (선택 정렬은 모두를 스캔함)
최악의 경우 시간 복잡도 : O(n^2)
#include <stdio.h>
#define MAX_SIZE 5
void insertion_sort(int list[], int n) {
int i, j, key;
// 인덱스 0은 이미 정렬된 것으로 볼 수 있음
for (i = 0; i < n; i++) {
key = list[i]; // 현재 삽입될 숫자인 i번째 정수를 key변수로 복사
// 현재 정렬된 배열은 i-1까지이므로 i-1번째부터 역순으로 조사한다.
// j 값은 음수가 아니어야 하고
// key값보다 정렬된 배열에 있는 값이 크면 j번째를 j+1번째로 이동
for (j = i - 1; j >= 0 && list[j] > key; j--) {
list[j + 1] = list[j]; // 레코드의 오른쪽으로 이동
}
list[j + 1] = key;
}
}
void main() {
int i;
int n = MAX_SIZE;
int list[n] = { 8, 5, 6, 2, 4 };
// 삽입 정렬 수행
insertion_sort(list, n);
// 정렬 결과 출력
for (i = 0; i < n; i++) {
printf("%d ", list[i]);
}
}결과
퀵 정렬
- 배열에서 임의로
pivot지정 - 피벗보다 작은 값은 모두 왼쪽 부분 리스트로, 큰 값은 오른쪽 부분 리스트로 옮긴다.
pivot값이 최대값이나 최소값으로 정해질 최악의 경우 시간복잡도는 O(n^2)
# include <stdio.h>
# define MAX_SIZE 9
# define SWAP(x, y, temp) ( (temp)=(x), (x)=(y), (y)=(temp) )
/* 2개의 비균등 배열 list[left...pivot-1]와 list[pivot+1...right]의 합병 과정 */
/* (실제로 숫자들이 정렬되는 과정) */
int partition(int list[], int left, int right) {
int pivot, temp;
int low, high;
low = left;
high = right + 1;
pivot = list[left]; // 정렬할 리스트의 가장 왼쪽 데이터를 피벗으로 선택(임의의 값을 피벗으로 선택)
/* low와 high가 교차할 때까지 반복(low<high) */
do {
/* list[low]가 피벗보다 작으면 계속 low를 증가 */
do {
low++; // low는 left+1 에서 시작
} while (low <= right && list[low] < pivot);
/* list[high]가 피벗보다 크면 계속 high를 감소 */
do {
high--; //high는 right 에서 시작
} while (high >= left && list[high] > pivot);
// 만약 low와 high가 교차하지 않았으면 list[low]를 list[high] 교환
if (low < high) {
SWAP(list[low], list[high], temp);
}
} while (low < high);
// low와 high가 교차했으면 반복문을 빠져나와 list[left]와 list[high]를 교환
SWAP(list[left], list[high], temp);
// 피벗의 위치인 high를 반환
return high;
}
// 퀵 정렬
void quick_sort(int list[], int left, int right) {
/* 정렬할 범위가 2개 이상의 데이터이면(리스트의 크기가 0이나 1이 아니면) */
if (left < right) {
// partition 함수를 호출하여 피벗을 기준으로 리스트를 비균등 분할 -분할(Divide)
int q = partition(list, left, right); // q: 피벗의 위치
// 피벗은 제외한 2개의 부분 리스트를 대상으로 순환 호출
quick_sort(list, left, q - 1); // (left ~ 피벗 바로 앞) 앞쪽 부분 리스트 정렬 -정복(Conquer)
quick_sort(list, q + 1, right); // (피벗 바로 뒤 ~ right) 뒤쪽 부분 리스트 정렬 -정복(Conquer)
}
}
void main() {
int i;
int list[9] = { 5, 3, 8, 4, 9, 1, 6, 2, 7 };
// 퀵 정렬 수행(left: 배열의 시작 = 0, right: 배열의 끝 = 8)
quick_sort(list, 0, 9 - 1);
// 정렬 결과 출력
for (i = 0; i < 9; i++) {
printf("%d ", list[i]);
}
}결과
병합 정렬
- 병합 정렬 이미지 ( 출처 위키백과 )
# include <stdio.h>
# define MAX_SIZE 8
int sorted[MAX_SIZE]; // 추가적인 공간이 필요
// i: 정렬된 왼쪽 리스트에 대한 인덱스
// j: 정렬된 오른쪽 리스트에 대한 인덱스
// k: 정렬될 리스트에 대한 인덱스
/* 2개의 인접한 배열 list[left...mid]와 list[mid+1...right]의 합병 과정 */
/* (실제로 숫자들이 정렬되는 과정) */
void merge(int list[], int left, int mid, int right) {
int i, j, k, l;
i = left;
j = mid + 1;
k = left;
/* 분할 정렬된 list의 합병 */
while (i <= mid && j <= right) {
if (list[i] <= list[j])
sorted[k++] = list[i++];
else
sorted[k++] = list[j++];
}
// 남아 있는 값들을 일괄 복사
if (i > mid) {
for (l = j; l <= right; l++)
sorted[k++] = list[l];
}
// 남아 있는 값들을 일괄 복사
else {
for (l = i; l <= mid; l++)
sorted[k++] = list[l];
}
// 배열 sorted[](임시 배열)의 리스트를 배열 list[]로 재복사
for (l = left; l <= right; l++) {
list[l] = sorted[l];
}
}
// 합병 정렬
void merge_sort(int list[], int left, int right) {
int mid;
if (left < right) {
mid = (left + right) / 2; // 중간 위치를 계산하여 리스트를 균등 분할 -분할(Divide)
merge_sort(list, left, mid); // 앞쪽 부분 리스트 정렬 -정복(Conquer)
merge_sort(list, mid + 1, right); // 뒤쪽 부분 리스트 정렬 -정복(Conquer)
merge(list, left, mid, right); // 정렬된 2개의 부분 배열을 합병하는 과정 -결합(Combine)
}
}
void main() {
int i;
int n = MAX_SIZE;
int list[8] = { 21, 10, 12, 20, 25, 13, 15, 22 };
// 합병 정렬 수행(left: 배열의 시작 = 0, right: 배열의 끝 = 7)
merge_sort(list, 0, n - 1);
// 정렬 결과 출력
for (i = 0; i < n; i++) {
printf("%d ", list[i]);
}
}결과
