버블정렬, 선택정렬, 삽입정렬

버블정렬

인접한 인자와 비교하여 더 큰 원소를 뒤로 보내는 방식

시간복잡도 : Best-N^2, Avg-N^2, Worst-N^2

공간복잡도 : O(N)

#include<iostream>
using namespace std;

int main() {
	int arr[10] = { 4,2,5,1,10,6,8,9,7,3 };
	int n = 10;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n - i - 1; j++) {
			int temp;
			if (arr[j] > arr[j + 1]) { //앞에 있는게 뒤에꺼보다 크면 스왑해준다
				temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
		}
	}
	for (int i = 0; i < n; i++) {
		cout << arr[i] << ' ';
	}
}

 

 

선택정렬

가장 작은 값들을 앞으로 하나씩 보내는 방식

시간복잡도 : Best-N^2, Avg-N^2, Worst-N^2

공간복잡도 : O(N)

버블정렬보다는 조금 빠름

비교는 많지만 교환하는 횟수는 적기때문에 교환이 많은 곳에는 효율적

 

#include<iostream>
using namespace std;

int main() {
	int arr[10] = { 4,2,5,1,10,6,8,9,7,3 };
	int n = 10;
	
	int min, minindex, temp;
	for (int i = 0; i < n-1; i++) {
		min = 1000;
		for (int j = i; j < n; j++) { //i번째부터 뒤에까지
			if (arr[j] < min) { //가장 작은 값을 찾아서
				min = arr[j]; //값 저장
				minindex = j; //인덱스 저장해주고
			}
		}
        //i번째와 가장 작은 값을 스왑해준다
		temp = arr[minindex]; 
		arr[minindex] = arr[i];
		arr[i] = temp;
	}

	for (int i = 0; i < n; i++) {
		cout << arr[i] << ' ';
	}
}

 

삽입정렬

2번째 원소부터 시작해서 현재 자리의 앞의 원소들과 비교해 현재의 원소가 앞의 원소들보다 작다면 더 앞으로 옮기는 방식

맨앞으로 가장 작은걸 하나씩 옮겨줌

시간복잡도 : Best-N, Avg-N^2, Worst-N^2

공간복잡도 : O(N)

최선의 경우가 O(N)

데이터의 상태 및 데이터의 크기에 따라서 성능의 편차가 굉장히 심한 정렬

#include<iostream>
using namespace std;

int main() {
	int arr[10] = { 4,2,5,1,10,6,8,9,7,3 };
	int n = 10;
	int key, i, j;

	for (i = 1; i < n; i++) {
		key = arr[i]; //i번째값을 초기 key값으로 두고
		for (j = i - 1; j >= 0; j--) {
			if (arr[j] > key) arr[j + 1] = arr[j]; //앞에 있는값을 뒤에 값으로 옮겨두고
			else break; //앞에 있는 것이 더 작을때까지
		}
		arr[j + 1] = key; //마지막 key가 들어갈 자리를 찾으면 key를 넣어준다
	}

	for (int i = 0; i < n; i++) {
		cout << arr[i] << ' ';
	}
}