선택 정렬

선택 정렬이란?

 

* 데이터 배열에서 가장 작은(또는 가장 큰) 데이터를 선택하여 오름차순(또는 내림차순)으로 정렬할 때 사용

 

* 최소선택정렬 / 최대선택정렬 로 나뉨

 

  - 최소선택정렬 (Min-selection sort) : 매번 가장 작은 데이터를 선택하여 배열을 오름차순으로 변경
  - 최대선택정렬 (Max-selection sort) : 매번 가장 큰 데이터를 선택하여 배열을 내림차순으로 변경

 

 

 

 

 

 

 

 

 

선택 정렬 동작과정

(최소선택정렬 예시)

Step1. 전체 데이터에서 최솟값을 찾아냄
Step2. 찾은 최솟값을 배열의 가장 앞 원소와 교환
Step3. 그 다음으로 작은 데이터를 선택하여, 맨 앞에서 두번째 데이터와 자리 교환
Step4. 위와 같은 방식으로 오름차순 정렬 완료될 때까지 데이터를 선택하고 자리를 교환하는 과정을 반복

 

 

 

 

 

 

 

선택 정렬 알고리즘 구현

1) C

#include <stdio.h>
#include <stdlib.h>

int main() {
	int i, j, min, index, temp;
	int arr[10] = { 1, 9, 4, 6, 11, 10, 3, 15, 2, 13 };
	for (i = 0; i < 10; i++) {
		min = INT_MAX;
		for (j = i; j < 10; j++) {
			if (min > arr[j]) {
				min = arr[j];
				index = j;
			}
		}
		temp = arr[i];
		arr[i] = arr[index];
		arr[index] = temp;
	}
	for (i = 0; i < 10; i++)
		printf("%d ", arr[i]);
	return 0;
}

2) Python

arr = [8, 3, 0, 9, 1, 6, 2, 4, 7, 5]

n = len(arr)
for i in range(n):
    # 가장 작은 데이터의 인덱스
    min_idx = i
    for j in range(i+1, n):
        # 최솟값 찾기
        if (arr[min_idx] > arr[j]):
            min_idx = j
    # 데이터 간의 자리 변경
    arr[i], arr[min_idx] = arr[min_idx], arr[i]

print(arr)

 

 

 

 

 

 

 

선택정렬 시간 복잡도

N개의 데이터가 있을 때 N-1번만큼 가장 작은 데이터를 찾고 맨 앞으로 보내는 과정이 필요

따라서 N + (N-1) + (N-2) + (N-3) + (N-4) + ... + 2 만큼의 연산횟수가 필요

 

이를 근사치로 계산하면 N * (N+1) / 2

빅오 표기법으로는 O(N*N) 으로 표시