선택정렬 (Selection Sort)

선택 정렬(Selection Sort)

-배열의 요소 중 최댓값 or 최솟값을 골라서(Selection),

배열의 가장 끝의 요소와 교환 하는 정렬 -

총 n개의 데이터가 있다면, 교환 횟수는 많아야 n-1번 

비교 횟수는 n(n-1) / 2번, 시간 복잡도는 O(n^2)이다.

비교 횟수가 버블 정렬과 같다는 특징이 있다. 

-Sample Source-

	#include <iostream>
	using namespace std;
	int main()
	{
	int Array[5] = {7,12,3,2,1 }; //정렬되지 않은 배열
	int MinVar, TempVar, Index; //최소값, 임시 변수, 최소값이 있는 인덱스
	cout <<" [0]" << "[1]" << "[2]" << "[3]" << "[4]" << endl; //인덱스 번호 표
	for (int i = 0; i < 4; i++) //정렬 루프
	{
	MinVar = Array[i]; //일단 첫번째 최소값은 정렬되지 않은 배열의 맨 앞 값을 넣어준다.
	for (int j = i + 1; j < 5; j++) //최소값 결정 루프
	{
	if (MinVar > Array[j]) //만약 MinVar에 있는 값보다 크면
	{
	MinVar = Array[j]; //MinVar에 더 작은값을 넣는다
	Index = j; //해 당인덱스 번호 저장
	}
	}
	if (MinVar != Array[i]) //만약 최소값이 변경 되었다면 교환
	{
	TempVar = Array[Index];
	Array[Index] = Array[i];
	Array[i] = TempVar;
	}
	cout << i+1 << ": "; //각각 정렬 싸이클마다의 배열 상태 출력
	for (int k = 0; k < 5; k++)
	cout << Array[k] << " ";
	cout << endl;
	}
	}

view raw SelectSort.cpp hosted with ❤ by GitHub