[c++] 선택정렬, 버블정렬, 삽입정렬

아래 정렬은 모두 오름차순 정렬을 기준으로 정리하였다.

선택정렬(Selection Sort)

가장 작은 수를 찾아 앞으로 보내는 과정을 반복

1. 배열의 처음부터 끝까지 반복문을 통해 돌며 가장 작은 수를 찾는다.
2. 가장 작은 수를 배열의 맨 앞으로 보낸다.
3. 그 다음 배열부터 끝까지 또 작은 수를 찾아 맨 앞으로 보낸다.
4. 이 과정을 배열이 끝날때까지 반복하여 정렬을 한다.

시간복잡도는 O(n^2)

 

#include<stdio.h>
int main() {
	freopen("input.txt", "rt", stdin);
	int a[101], n, tmp, idx, i, j;
	scanf("%d", &n);
	for(i=0; i<n; i++){
		scanf("%d", &a[i]);
	}
	for(i=0; i<n-1; i++){
		idx=i;
		for(j=i+1; j<n; j++){
			if(a[j]<a[idx]) idx=j;
		}
		tmp=a[i];
		a[i]=a[idx];
		a[idx]=tmp;
	}
	for(i=0; i<n; i++){
		printf("%d ", a[i]);
	}
	return 0;
}

---

버블정렬(Bubble Sort)

이웃하는 두 수의 크기를 비교하여 숫자가 더 작은 것을 앞으로 위치시키며 정렬한다.

1. 첫번째 반복 후 가장 큰 수가 가장 오른쪽에 가게 된다.
2. 다시 배열 시작부터 배열의 크기 -1, n-1까지 반복을 돌며 이웃하는 수와 비교하면서 정렬을 계속하며 그 다음 작은 수를 그 다음 오른쪽에 놓게 된다.

시간복잡도는 O(n^2)

 

#include <stdio.h>
int main() {
	freopen("input.txt", "rt", stdin);
	int a[101], n, i, j, tmp;
	scanf("%d", &n);
	for(i=0; i<n; i++){
		scanf("%d", &a[i]);
	}
	for(i=0; i<n-1; i++){
		for(j=0; j<n-i-1; j++){
			if(a[j]>a[j+1]){
				tmp=a[j];
				a[j]=a[j+1];
				a[j+1]=tmp;
			}
		}
	}
	for(i=0; i<n; i++){
		printf("%d ", a[i]);
	}	
	return 0;
}

---

삽입정렬(Insertion Sort)

두 번째부터 비교를 시작하며, 앞의 값들과 비교하여 자신의 자리를 찾는 정렬 방법

1. 숫자를 한 개 선택하고 선택된 숫자를 적절한 위치에 삽입하며 정렬한다.
2. 선택된 숫자의 왼쪽 숫자와 크기를 비교하여 숫자가 더 작은 것을 앞으로 위치시킨다.
3. 그 다음 한 칸 오른쪽으로 이동하여 해당 숫자를 또 왼쪽 숫자들과 비교하여 정렬을 하게 되는데, 왼쪽 숫자들은 정렬이 되어 있는 상태이기 때문에 바로 왼쪽 옆 숫자 한 개씩 비교하며 선택된 숫자보다 작은 숫자가 나올 때까지만 이동을 하면 된다.

시간복잡도는 O(n^2) -> 최선의 경우 n번 만으로도 정렬 가능, 다만 시간 복잡도는 최악의 경우를 표기

 

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
	freopen("input.txt", "rt", stdin);
	int a[100], n, tmp, i, j;
	scanf("%d", &n);
	for(i=0; i<n; i++){
		scanf("%d", &a[i]);
	}
	for(i=1; i<n; i++){
		tmp=a[i];
		for(j=i-1; j>=0; j--){
			if(a[j]>tmp) a[j+1]=a[j];
			else break;
		}
		a[j+1]=tmp;
	}
	for(i=0; i<n; i++){
		printf("%d ", a[i]);
	}	
	return 0;
}