정렬알고리즘- Selection Sort (선택 정렬) | C, Python 코드 구현

정렬 알고리즘 중 세번째이다. 선택 정렬이다. 개인적으로 bubble sort와 insertion sort보다는 직관적으로 더 쉽다고 생각이 들었다. 왜냐하면 selection sort는 그냥 전체에서 최솟값을 찾아서 앞으로 옮기는 걸 계속 반복하는 알고리즘이기 때문이다. 우리가 흔히 프로그래밍이아닌 현실에서 숫자들을 정렬한다고 하면 바로 이 selection sort와 같은 방법을 쓸 것이다.

 

📌선택 정렬 Selection Sort

선택 정렬이란, 먼저 최소값을 찾고 그 최소값을 정렬된 이후의 맨 앞 인덱스까지 옮기며 정렬하는 것이다.

즉,

1. 주어진 데이터 중 최소값을 찾음
2. 해당 최소값을 데이터 맨 앞에 위치한 값과 교체함
3. 맨 앞의 위치를 뺀 나머지 데이터를 동일한 방법으로 반복함

 

pseudo code 구현

• for stand in range(len(data_list)-1): -> 기준점 잡고 반복(len-1을 한 이유는 마지막 index는 검사할 필요가 없기 때문)
  • lowest = stand
  • for num in range(stand, len(data_list)) ->기준점 이후부터 끝까지 돌면서
    • (처음 lowest는 기준점부터 시작되는) data_list[lowest] > data_list[num]이면:
      • lowest = num --> lowest를 더 작은 num으로 update
      • data_list 끝까지 반복
  • data_list[stand], data_list[num] = data_list[num], data_list[stand] -> 현재의 기준점과 최솟값을 swap

 

📌알고리즘 구현 (C)

void swap(int *arr, int i, int j){
	int tmp;

	tmp = arr[i];
	arr[i] = arr[j];
	arr[j] = tmp;
}

void selection_sort(int *num_arr, int arr_len){
	int min_idx;

	for (int idx = 0; idx < arr_len; idx++)
	{
		min_idx = idx;
		for (int i = idx; i < arr_len; i++)
		{
			if (num_arr[i] <= num_arr[min_idx])
				min_idx = i;
		}
		swap(num_arr, idx, min_idx);
	}
}

 

📌알고리즘 구현 (Python)

def selection_sort(data):
    for stand in range(len(data)-1):
        lowest = stand
        for index in range(stand, len(data)):
            if data[lowest] > data[index]:
                lowest = index
        data[stand], data[lowest] = data[lowest], data[stand]
    return data

 

📌알고리즘 분석

for 반복문에 2개이고 모두다 len(data)의 영향을 받으므로 시간복잡도는 $$O(n^2)$$
실제로 상세하게 계산하면, $$n*(n-1)/2$$