정렬 - 삽입 정렬

정렬

→ 데이터를 특정한 기준에 따라 순서대로 나열하는 것

 

정렬 알고리즘을 배우고 데이터를 정렬한 후, 다음에 배울 이진 탐색이 가능!

(즉, 정렬 알고리즘은 이진 탐색의 전처리 과정) 

 

정렬 알고리즘의 종류 : 선택 / 삽입 / 퀵 / 계수 등

 

 

 

이 카드들을 오름차순으로 정렬해보자.

 

삽입 정렬

→ 앞에 있는 수들과 비교하여 자신의 자리를 찾아가기

 

 

맨 앞 인덱스는 정렬되어 있다 가장하고, 두번째 인덱스부터 자신의 앞에 있는 인덱스의 수들과 자신을 비교한다. 이 때, 앞에 있는 수는 7이고 대상은 5이므로, 5가 7에 앞으로 간다.

 

 

그 다음 대상인 세번째 인덱스의 9는, 자신의 앞에 있는 인덱스의 수들과 자신을 비교하여 자신의 자리를 찾는다. 9는 5와 7보다 크므로 7의 뒤에 위치한다. (결국 제자리에 있다.)

 

 

그 다음 대상인 네번재 인덱스의 0도, 자신의 앞에 있는 인덱스의 수들과 자신을 비교하여 자신의 자리를 찾늗나. 0은 5와 7, 9보다 작으므로 5 앞으로 이동한다.

 

 

그 다음 대상인 다섯번째 인덱스의 3도 마찬가지로 0, 5, 7, 9와 비교하여 자신의 자리를 찾는다. 0보다는 크고 5보다는 작으므로 0과 5사이로 이동한다. 이와 같은 과정을 반복한다.

 

 

4도 자신의 자리를 찾고

 

 

마지막 인덱스의 값 8도 자신의 자리를 찾아간다. 그러면 아래와 같이 정렬이 완성된다.

 

 

삽입 정렬 소스코드 (C++)

#include <iostream>
#include <vector>

using namespace std;

vector<int> arr = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};

int main(void) {

	int tmp;

	// 두번째 데이터부터 제자리를 찾아가는 방식의 반복문
	for (int i = 1; i < arr.size(); i++) {

		// i번째 데이터 앞의 수부터 앞으로 가면서 자리 찾기
		for (int j = i; j > 0; j--) {

			// 자리를 찾아가다 자기보다 큰 수를 만나면 정지
			if (arr[j] < arr[j - 1]) {
				tmp = arr[j];
				arr[j] = arr[j - 1];
				arr[j - 1] = tmp;
			}
			else
				break;
		}

		// 단계별로 정렬되는 배열 출력
		for (int k = 0; k < arr.size(); k++)
			cout << arr[k] << " ";
		cout << endl;
	}

	return 0;
}

 

 

출처 : 이것이 취업을 위한 코딩테스트다 with 파이썬 : 취업과 이직을 결정하는 알고리즘 인터뷰 완벽 가이드