(C/C++) 정렬 - 선택 정렬(Selection Sort) - 안정성 X, O(N²)

안녕하세요.

오늘은 선택 정렬에 대해서 알아보도록 하겠습니다.

 

1. 선택 정렬(Selection Sort)이란?

가장 작은 숫자를 찾아서 첫번째 놓고, 그 다음 작은 숫자를 찾아서 다음에 놓고 반복하는 정렬입니다.

 

2. 선택 정렬의 특징

많은 비교, 적은 교환

안정성 X

O(N²) 의 시간복잡도

역순일 경우 제일 느리나 정렬된 경우와 큰 차이가 나지 않는다.

삽입 정렬과 함께 많이 쓰이는 정렬 중에 하나

 

 

정렬 안정성 과 알고리즘 시간 복잡도 빅오(Big - Oh)

 

3. 선택 정렬의 구현

 

#include <iostream>
#include <stdio.h>

void SelectSort_1(int _arrays[], int _arraysLength)
{
	int minIndex;						//최소값 배열 인덱스

	for (int i = 0; i < _arraysLength - 1; i++)		//0 부터 length -1 까지
	{
		minIndex = i;		

		for (int j = i + 1; j < _arraysLength; j++)	//i + 1 부터 length 까지
		{
			if (_arrays[minIndex] > _arrays[j])	//남아있는 값 중에 최소값을 찾는다.
			{
				minIndex = j;			//최소값을 찾아서 index를 기억한다.
			}
		}

		int temp = _arrays[minIndex];			//i 번째와 최소값을 Swap 한다.
		_arrays[minIndex] = _arrays[i];
		_arrays[i] = temp;
	}
}

void SelectSort_2(int _arrays[], int _arraysLength)
{
	int minIndex;						//최소값 배열 인덱스
	int min;						//최소값

	for (int i = 0; i < _arraysLength - 1; i++)
	{
		minIndex = i;
		min = _arrays[i];

		for (int j = i + 1; j < _arraysLength; j++)
		{
			if (min > _arrays[j])
			{
				minIndex = j;			//최소값을 찾아서 index를 기억한다.
				min = _arrays[j];		//최소값을 찾아서 기억한다.
			}
		}

		_arrays[minIndex] = _arrays[i];			//i 번째와 최소값을 스왑한다.
		_arrays[i] = min;				//min 값이 있기에 temp 를 선언할 필요 없다.
	}
}

 

arrays[i] 를 사용 하는 것(위)과 min 을 사용 하는(아래) 2가지 방법을 구현 했습니다.

2가지의 차이점은

arrays[i] 를 사용했을 경우 arrays 의 주소 값을 찾은 뒤 i 만큼 뒤로 이동한 뒤 값을 읽고

min 을 사용 했을 경우 min 주소값으로 가서 값을 읽습니다

 

이는 배열이기 때문에 어쩔 수 없는 특성인데 루프문을 많이 돌면 돌수록 

값을 그냥 읽는 것 하고 i 만큼 뒤로 가서 값을 읽는 것의 차이가 나게 됩니다.

루프문을 돌 수 밖에 없는 정렬알고리즘 특성상 약간의 라도 속도 향상을 위해서

임시 변수(2번째 방식)를 사용하는 것을 추천드립니다.

감사합니다.

 

 

다른 정렬

버블 정렬(Bubble Sort) - 안정성 O, O(N²)

선택 정렬(Select Sort) - 안정성 X, O(N²)

삽입 정렬(Insert Sort) - 안정성 O, O(N²)

쉘 정렬(Shell Sort) - 안정성 X, O(n^1.5)

병합 정렬(Merge Sort) - 안정성 O, O(N log N)

퀵 정렬(Quick Sort) - 안정성 X, O(N log N)