[자료구조] 정렬과 탐색(1) - 삽입, 선택, 버블

1. 정렬 알고리즘

- 정렬알고리즘은 알고리즘 중에 가장 기본적인 알고리즘 이다.

- 이 글에서 살펴볼 알고리즘은 삽입, 선택, 거품(버블), 퀵, 합병(merge), 힙, 이진탐색 트리를 이용한 정렬이다.

 

1) 삽입정렬 - O(n^2)

- 배열의 모든 원소를 앞에서부터 차례대로 배열 부분과 비교하여, 삽입함으로써 정렬하는 알고리즘

- 처음 key 값(처음으로 뽑아 비교할 원소)은 두번째 원소이다

 

> 과정

• 두번째 원소 10을 뽑아 첫번째 원소와 비교하여 29보다 작으므로 29왼쪽으로 삽입된다.
• 세번째 원소 14를 뽑아 두번째 원소와 비교하여 29보다 작으므로 29왼쪽으로 삽입된다.
• 14는 10보다 크므로 바뀌지 않는다.
• 네번째 원소 37를 뽑아 세번째 원소인 29와 비교한다. 37이 29보다 크므로 바뀌지 않는다.
• 다섯번째 원소 13을 뽑아 37과 비교, 29와비교, 14와 비교한 후 14왼쪽으로 삽입된다. 
• 정렬 끝!

> 코드(c++)

#include <iostream>
using namespace std;


void Insert_sort(int arr[], int n) {
	int key;
	int i, j;
	for (i = 1; i < n; i++) {
		key = arr[i]; //키값은 두번째 원소부터 시작 
		for (j = i - 1; j >= 0; j--) { //키값과 비교할 원소
			if (arr[j] > key) {
				arr[j + 1] = arr[j];
			}
			else break;
		}
		arr[j + 1] = key;
	}
}



int main() {
	int n = 7; //정렬할 원소의 개수
	int arr[] = { 1,7,2,5,6,10,3 };

	Insert_sort(arr, n);

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

> 시간복잡도 

- 이중 반복문(n*(n-1))이므로  O(n^2)

 

 

2) 선택정렬 - O(N^2)

- 각 루프마다 최대원소를 찾고 제일 오른쪽 원소와 교환한다.(맨 오른쪽은 제외)

- 하나의 원소만 남을 때까지 위의 루프를 반복한다.

* 각 루프마다 최소원소를 찾고 제일 왼쪽 원소와 교환하는 방법과 같다

 

> 코드

void Selection_sort(int arr[], int n) {
	int indexMax, tmp;
	for (int i = n-1; i >= 0; i--) {
		indexMax = i;
		for (int j = i-1; j >= 0; j--) {
			if (arr[j] > arr[indexMax]) {
				indexMax = j;
			}
		}
		tmp = arr[indexMax];
		arr[indexMax] = arr[i];
		arr[i] = tmp;
	}
}
int main() {
	int n = 7; //정렬할 원소의 개수
	int arr[] = { 1,7,2,5,6,10,3 };

	Selection_sort(arr, n);

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

 > 시간복잡도 : n*(n-1)/2 만큼 걸리므로 O(n^2) 만큼 걸린다.

 

 

3) 버블정렬 - O(n^2)

- 서로 인접한 두 원소를 비교하여, 순서가 맞지 않으면 교환한다.

- 회전을 한번씩 할 때마다 차례대로 제일 오른쪽 원소는 정렬에서 제외된다(왜냐하면 가장 큰 원소이기 때문)

 

> 코드

void Bubble_sort(int arr[], int n) {
	int tmp;
	for (int i = 0; i < n-1; i++) {
		for (int j = 0; j < n - i-1; j++) {
			if (arr[j] > arr[j+1]) {
				tmp = arr[j];
				arr[j] = arr[j+1];
				arr[j+1] = tmp;
			}
			else continue;
		}
	}
}
int main() {
	int n = 7; //정렬할 원소의 개수
	int arr[] = { 1,7,2,5,6,10,3 };
    
	Bubble_sort(arr, n);

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

* 반목문에서 왜 n-1까지인지 헷갈릴 수도 있는데, 

예시로 i가 0일때, j가 0~ 5까지 들어가면 마지막에 j+1 이들어가니까 arr[5]와 arr[6]이 비교되어서 인덱스를 초과하지 않습니다.  n까지면 인덱스 범위를 넘어갑니다.

 

> 시간복잡도 

이것 또한 O(n^2) 입니다. 중복계산되는 부분이 많아 비효울적인 코드긴 합니다.