[sorting] 선택 정렬 | Selection Sort

Selection Sort

 

• 제자리 정렬 알고리즘 중 하나.
• 정렬되지 않은 입력 배열 외에 다른 추가 메모리를 요구하지 않는다.
• 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘.
• 첫번째 자료를 두번째 자료부터 마지막 자료까지 차례대로 비교하여 가장 작은 값을 찾아 첫 번째에 놓는 행위를 반복하며 정렬을 수행한다.
  • 1회전을 하고 나면 가장 작은 값의 자료가 맨 앞에 위치.
  • 다음 회전에는 두번째 위치의 배열부터 처리한다.

 

 

정렬 과정

 

1. 주어진 배열에서 최소값을 찾는다.
2. 현재 범위 내에서 맨 앞의 값과 교환한다.
3. 교환한 위치를 제외한 나머지 배열을 같은 방법으로 교체한다.
4. 하나의 원소만 남을 때 까지 반복한다.

 

#include <stdio.h>
#include <iostream>
using namespace std;

int main(void) {
	int arr[10] = { 4,5,6,2,3,10,8,1,9,7 };

	for (int i = 0; i < 9; i++) {
		int least = i;

		for (int j = i+1; j < 10; j++) {

			if (arr[least]>arr[j]) {
				least = j;
			}
		}
		if (i != least) {
			int temp = arr[i];
			arr[i] = arr[least];
			arr[least] = temp;
		}
	}
}

실행 결과

 

• 마지막 숫자는 자동으로 정렬되기 때문에 배열의 길이(n)-1 만큼 반복한다.
• 또한 최솟값이 현 위치의 자신이라면 이동하지 않는다.

 

 

 

 

 

장단점

장점 : 자료 이동 횟수가 미리 결정된다.

단점 : 안정성을 만족 하지 않는다. == 값이 같은 원소가 있을 경우 상대적인 위치가 변경될 수 있다.

 

 

시간 복잡도

1. 비교횟수 
   • 두 번의 for 루프 실행
     • 외부 루푸 : n-1 번
     • 내부 루프 : 최솟값을 찾는 역할 n-1번 -> n-2번 -> ... -> 2번 -> 1번
2. 교환 횟수
   • 외부루프의 실행 횟수와 동일 == 상수시간. 
   • 한 번 값을 교환하기 위해서 3번의 이동이 발생 => 3*(n-1)번

 

T(n) = (n-1) + (n-2) + ... + 2 + 1 = n(n-1)/2 = O(n^2)

=> 최상, 최악, 평균 모두 동일

 

 

 

참고 url : https://gmlwjd9405.github.io/2018/05/06/algorithm-selection-sort.html