선택정렬

선택정렬

• 모든 index에 대해서 그 index에 위치시킬 값을 “선택”하기 때문에 이 정렬 알고리즘을 “선택 정렬”또는 “Selection Sort”이라고 부른다.

1. 주어진 배열에서 가장 작은 값을 찾는다
2. 그 값을 배열의 맨 앞 값과 교환한다.
3. 맨 앞 값을 뺀 나머지 배열을 같은 방법으로 교환한다.
4. 하나의 값만 남을 때까지 반복한다.

def selectionSort(A) {
	for i in range(len(A) - 1) :
    	min = i
        for j in range(i + 1, len(A)):
        	if A[j] < A[min]:
            	min = j
        A[i], A[min] = A[min], A[i]

⏰ 선택정렬의 시간복잡도

데이터의 개수가 n개라고 했을 때,
첫 번째 회전에서의 비교횟수 : 1 ~ (n-1) => n-1
두 번째 회전에서의 비교횟수 : 2 ~ (n-1) => n-2
...
(n-1) + (n-2) + .... + 2 + 1 = n(n-1)/2

비교하는 것이 상수 시간에 이루어진다는 가정 아래,
n개의 주어진 배열을 정렬하는데 O(n^2) 만큼의 시간이 걸립니다.
최선, 평균, 최악의 경우 시간복잡도는 O(n^2) 으로 동일합니다.

선택정렬의 단점

단순하지만 비효율적인(O(n^2)) 정렬