[알고리즘] 선택, 버블, 삽입정렬

정렬

시간 복잡도 O(N^2)인 세 가지 정렬을 알아보자.

모두 N이 1~100 사이로 지정되고, 임의의 N 개의 숫자를 오름차순 정렬한다고 가정한다.

선택 정렬

  • 첫 번째 for 문이 처음부터 까지 순회한다.
  • 첫 번째 for 문의 인덱스를 idx라는 변수에 선언한다.
  • 두 번째 for 문이 첫 번째 for 문의 다음 수 부터 순회한다.
  • j에서 순회하는 배열의 수가 idx 번째 배열의 수 보다 작으면 idx를 j로 바꿔준다.
  • 두 번째 순회가 끝나면 idx 번째 수와 첫 번째 for 문의 i번 째 수를 서로 교체한다.
#include <iostream>
using namespace std;
int main(void) {
	int arr[101];
	int N;
	cin >> N;
	for (int i = 0; i < N; i++) cin >> arr[i];
	for (int i = 0; i < N; i++) {
		int idx = i;
		for (int j = i + 1; j < N; j++) {
			if (arr[j] < arr[idx]) idx = j;
		}
		int tmp = arr[i];
		arr[i] = arr[idx];
		arr[idx] = tmp;
	}
	for (int i = 0; i < N; i++) cout << arr[i] << ' ';
	cout << 'endl';
}

버블 정렬

  • 첫 번째 for 문이 처음부터 끝-1까지 순회한다.
  • 두 번째 for 문은 항상 처음부터 끝 - i - 1까지 순회한다.
  • 두 번째 for 문의 j번 째 수가 j + 1 번째 수 보다 크다면 두 수를 swap 한다.
  • 두 번째 for 문이 끝나면 가장 큰 수가 가장 오른쪽에 위치하게 된다.
  • 이를 첫 번째 for 문의 횟수만큼 반복하면 오름차순으로 정렬된다.
#include <iostream>
using namespace std;
int main(void) {
	int N;
	cin >> N;
	int arr[101];
	for (int i = 0; i < N; i++) cin >> arr[i];
	for (int i = 0; i < N - 1; i++) {
		for (int j = 0; j < N - i - 1; j++) {
			if (arr[j] > arr[j + 1]) {
				int tmp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = tmp;
			}
		}
	}
	for (int i = 0; i < N; i++) cout << arr[i] << ' ';
	return 0;
}

삽입 정렬

  • 첫 번째 for 문이 처음+1부터 까지 순회한다.
  • 두 번째 for 문은 항상 i-1부터 0까지 반대로 순회한다.
  • 두 번째 for 문을 시작할 때, 첫 번째 for 문 인덱스의 수를 tmp에 저장한다.
  • tmp에 저장된 수 보다 j에 있는 수가 크다면 j+1에 j 번째 수를 삽입한다.
  • 크지 않다면 for 문을 종료하고 마지막으로 돌았던 j에 다음 인덱스에 tmp의 값을 삽입한다.
  • for 문이 break 없이 돌았다면 -1 + 1인 0번째 인덱스에 tmp가 삽입된다.
  • 이러한 과정을 거치면, 첫 번째 for 문이 진행될 때마다 큰 수는 오른쪽으로 이동하고 tmp는 자신의 순서에 맞게 삽입된다.
#include <iostream>
using namespace std;
int main(void) {
	int N;
	cin >> N;
	int arr[101];
	for (int i = 0; i < N; i++) cin >> arr[i];
	for (int i = 1; i < N; i++) {
		int tmp = arr[i];
		int j;
		for (j = i - 1; j >= 0; j--) {
			if (tmp < arr[j]) arr[j + 1] = arr[j];
			else break;
		}
		arr[j + 1] = tmp;
	}
	for (int i = 0; i < N; i++) cout << arr[i] << ' ';
	return 0;
}