정렬 - 선택 정렬

정렬

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

 

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

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

 

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

 

 

 

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

 

선택 정렬

→ 가장 작은 수를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 수를 선택해 두번째 데이터와 바꾸고...

 

"매번 가장 작은 것을 선택하여 n번째 수와 바꾼다."

 

 

가장 작은 수인 0을 맨 앞에 있는 7과 자리를 교체한다.

 

그 다음 작은 수인 1을 두 번째 수 5와 자리를 교체한다.

 

그 다음다음 작은 수인 2를 세 번째 수 9와 자리를 교체한다...

 

이와 같은 방법을 반복하면,

 

위 그림처럼 마지막 한 수를 마지막 - 1위치의 수와 바꾸면 끝이난다.

 

 

선택 정렬 소스 코드

#include <iostream>
#include <vector>

using namespace std;

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

int main(void) {

	for (int i = 0; i < arr.size(); i++) {

		// 맨 앞 숫자를 임시 저장할 변수
		int tmp = arr[i];
		// 정렬되지 않은 수 중 가장 최소값의 인덱스를 저장할 변수
		int min_idx = i;

		// 최소값의 인덱스를 구하는 반복문
		for (int j = i + 1; j < arr.size(); j++)
			min_idx = arr[min_idx] > arr[j] ? j : min_idx;

		// 스와핑
		arr[i] = arr[min_idx];
		arr[min_idx] = tmp;

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

	return 0;
}

 

 

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