[알고리즘] 선택정렬

07 Feb 2022 in Study on Algorithm

선택정렬이란?

선택정렬의 과정은 아래와 같다.

1. 처음 인덱스의 값을 저장한다.
2. 처음 인덱스의 다음 인덱스부터 배열 끝까지의 값 중 최솟값의 인덱스를 구한다.
3. 처음 인덱스의 값과 최솟값의 인덱스의 값을 비교한다.
4. 최솟값의 인덱스의 값이 더 작을 경우 두 수를 바꾼다. 그렇지 않을경우 생략한다.
5. 처음 인덱스의 다음 인덱스부터 종료 시 까지 1번~4번 과정을 반복한다.

그림으로도 살펴보자
idx가 현재 인덱스, idx_L이 최솟값을 가지는 인덱스 값이다.

그리고 선택정렬로 인한 시간복잡도는 반복문이 2개이므로 $ O({n}^2) $ 이다.

파이썬 코드로 선택정렬 구현하기

파이썬 코드로는 for 문을 사용해서 아래와 같이 구현할 수 있다.

for i in range(len(data) - 1):
    low_idx = i
    for j in range(low_idx + 1, len(data)):
        if data[low_idx] > data[j]:
            low_idx = j
    data[i], data[low_idx] = data[low_idx], data[i]

# Test Code

for count in range(15):
    data = random.sample(range(100), 20)
    data_check = sorted(data)
    print(data)
    print(data_check)
    
    for i in range(len(data) - 1):
        low_idx = i
        for j in range(low_idx + 1, len(data)):
            if data[low_idx] > data[j]:
                low_idx = j
        data[i], data[low_idx] = data[low_idx], data[i]
    
    if data == data_check:
        print(True)
    else:
        print(False)
    
    print()

정렬이 잘 되었으면 True가 출력될 것이다.

# 실행 결과

[47, 13, 92, 3, 71, 2, 50, 73, 6, 38, 5, 14, 51, 60, 28, 33, 32, 22, 21, 34]
[2, 3, 5, 6, 13, 14, 21, 22, 28, 32, 33, 34, 38, 47, 50, 51, 60, 71, 73, 92]
True

[15, 79, 30, 67, 19, 49, 35, 23, 44, 8, 55, 74, 92, 86, 95, 62, 94, 47, 90, 54]
[8, 15, 19, 23, 30, 35, 44, 47, 49, 54, 55, 62, 67, 74, 79, 86, 90, 92, 94, 95]
True

[11, 23, 37, 7, 27, 48, 71, 93, 78, 69, 18, 1, 87, 5, 16, 51, 49, 32, 29, 80]
[1, 5, 7, 11, 16, 18, 23, 27, 29, 32, 37, 48, 49, 51, 69, 71, 78, 80, 87, 93]
True

[47, 67, 74, 87, 5, 4, 76, 9, 61, 33, 52, 15, 19, 11, 91, 53, 69, 46, 71, 20]
[4, 5, 9, 11, 15, 19, 20, 33, 46, 47, 52, 53, 61, 67, 69, 71, 74, 76, 87, 91]
True

[73, 62, 87, 39, 11, 19, 82, 26, 51, 10, 52, 64, 35, 68, 2, 36, 97, 20, 1, 33]
[1, 2, 10, 11, 19, 20, 26, 33, 35, 36, 39, 51, 52, 62, 64, 68, 73, 82, 87, 97]
True

[24, 26, 88, 97, 4, 16, 63, 96, 48, 21, 76, 82, 47, 37, 31, 33, 56, 53, 70, 43]
[4, 16, 21, 24, 26, 31, 33, 37, 43, 47, 48, 53, 56, 63, 70, 76, 82, 88, 96, 97]
True

[85, 17, 87, 89, 35, 68, 24, 92, 47, 64, 80, 91, 60, 73, 71, 19, 23, 44, 93, 11]
[11, 17, 19, 23, 24, 35, 44, 47, 60, 64, 68, 71, 73, 80, 85, 87, 89, 91, 92, 93]
True

[66, 1, 97, 73, 50, 30, 99, 24, 41, 45, 63, 39, 13, 69, 56, 77, 5, 87, 38, 16]
[1, 5, 13, 16, 24, 30, 38, 39, 41, 45, 50, 56, 63, 66, 69, 73, 77, 87, 97, 99]
True

[75, 62, 84, 93, 29, 6, 12, 61, 20, 17, 4, 21, 50, 35, 1, 38, 42, 41, 15, 72]
[1, 4, 6, 12, 15, 17, 20, 21, 29, 35, 38, 41, 42, 50, 61, 62, 72, 75, 84, 93]
True

[19, 27, 45, 39, 22, 85, 79, 65, 69, 54, 11, 78, 98, 9, 41, 18, 86, 56, 82, 8]
[8, 9, 11, 18, 19, 22, 27, 39, 41, 45, 54, 56, 65, 69, 78, 79, 82, 85, 86, 98]
True

[65, 28, 97, 30, 62, 0, 58, 39, 98, 36, 18, 34, 10, 72, 96, 22, 9, 11, 44, 31]
[0, 9, 10, 11, 18, 22, 28, 30, 31, 34, 36, 39, 44, 58, 62, 65, 72, 96, 97, 98]
True

[42, 52, 10, 41, 32, 46, 37, 47, 2, 31, 51, 17, 13, 33, 30, 28, 49, 38, 78, 34]
[2, 10, 13, 17, 28, 30, 31, 32, 33, 34, 37, 38, 41, 42, 46, 47, 49, 51, 52, 78]
True

[54, 35, 75, 11, 65, 93, 55, 31, 21, 9, 26, 60, 66, 70, 85, 22, 99, 13, 37, 47]
[9, 11, 13, 21, 22, 26, 31, 35, 37, 47, 54, 55, 60, 65, 66, 70, 75, 85, 93, 99]
True

[43, 93, 87, 0, 3, 19, 64, 91, 16, 11, 36, 55, 74, 72, 66, 2, 24, 98, 57, 1]
[0, 1, 2, 3, 11, 16, 19, 24, 36, 43, 55, 57, 64, 66, 72, 74, 87, 91, 93, 98]
True

[24, 63, 93, 97, 2, 37, 61, 59, 71, 50, 39, 49, 72, 73, 91, 36, 12, 69, 48, 60]
[2, 12, 24, 36, 37, 39, 48, 49, 50, 59, 60, 61, 63, 69, 71, 72, 73, 91, 93, 97]
True

15회 실행한 결과, 모두 True가 잘 출력되었다.

결과는 같지만 선택정렬과는 조금 다른 코드..?

본래 선택정렬은 처음 idx를 제외한 리스트의 나머지 부분에서 최솟값의 idx를 골라서 처음 idx의 값과 값을 교환하는 형식이다.

    for i in range(len(data) - 1):
       for j in range(i + 1, len(data)):
           if data[i] > data[j]:
               data[i], data[j] = data[j], data[i]

여기서 중간에 low_idx를 저장하는 과정을 빼고 그냥 i번 인덱스랑 j번 인덱스의 값을 바꾸는 것만 넣어도 정렬이 잘 된다. 다만 자리를 바꾸는 횟수가 늘어날 뿐이다.

기왕 바꿀 거면 한꺼번에 다 측정하고 난 다음에 바꾸는 것이 좋긴 하지만, 코드의 양을 조금 줄이고 싶다면 위 방법도 나쁘지는 않은 것 같다.

C언어로 선택정렬 구현하기.

void select_sort(int* arr, int size) {
	
	int i, j, temp;
	int minIdx;

	for (i = 0; i < size - 1; i++) {
		minIdx = i;
		for(j = i + 1; i < size; j++) {
			if(arr[minIdx] > arr[j]) {
				minIdx = j;			
			}
		}
		temp = arr[i];
		arr[i] = arr[minIdx];
		arr[i] = temp;

	}
	
}

C언어로 구현하면 위와 같이 구현할 수 있다. (입력데이터 : 배열 포인터, 배열의 크기)