선택정렬 문제풀이 및 해석 (Python3)

문제 링크

시간측정에 사용한 코드

IDE에 프로파일링에서는 더 미세한 시간을 측정할 수 없었으므로 함수를 작성해 임시 측정을 진행했습니다. 또한 매번 해당 사이트에서 테스트를 진행하기에는 불편하여 랜덤배열을 작성하는 코드를 따로 작성해서 테스트를 진행했습니다. 그 밖에도 여러가지로 검증을 위해서 사용한 코드가 있습니다. 해당 코드들은 아래 링크를 참조해주세요 정렬 문제 정답 확인 함수들

import time
import numpy as np

def timer(fun, *args, result_print=False):
    st = time.perf_counter()
    
    result = fun(*args)
    if result_print: print(result)

    ed = time.perf_counter()
    return f'{ed - st:.6f}'


def int_array_test(fun, size=None):
    if size is None:
        size = [10, 100, 1000, 10000, 50000]

    for s in size:
        arr = np.random.randint(0, 1000, s).tolist()
        result = timer(fun, arr)
        print(f'생성된 크기 : {s} / 경과 시간 : {result}/s')

풀이1 (라이브러리 x, 정답 o, 시간 초과)

설명

정답은 맞으나, 시간초과가 발생한 풀이식입니다. 이중 for문으로 검색을하며, 두번째 for문에서는 이미 첫번째 for문에서 탐색한 배열은 검색할 필요가 없으므로 i값에서 부터 시작하도록 하였습니다.

테스트 결과

생성된 크기 : 10 / 경과 시간 : 0.000008/s

생성된 크기 : 100 / 경과 시간 : 0.000172/s

생성된 크기 : 1000 / 경과 시간 : 0.018991/s

생성된 크기 : 10000 / 경과 시간 : 1.851767/s

생성된 크기 : 50000 / 경과 시간 : 46.443738/s

생성된 크기 : 10 / 경과 시간 : 0.000008/s

생성된 크기 : 100 / 경과 시간 : 0.000168/s

생성된 크기 : 1000 / 경과 시간 : 0.018405/s

생성된 크기 : 10000 / 경과 시간 : 1.862033/s

생성된 크기 : 50000 / 경과 시간 : 46.680322/s

코드

def sortArray(self, nums: list[int]) -> list[int]:
    # len의 호출수를 줄이기 위해서 사용한 변수
    length = len(nums)

    for min_index in range(length):
        max_index = min_index

        # 두번째 for문에서는 max값을 탐색한다. max_index 배열의 값보다 배열번호 j의 값이 더 크다면 max_index의 값을 j의 배열번호로 교체한다.
        for j in range(min_index + 1, length):
            if nums[max_index] > nums[j]:
            	    max_index = j

        # 불필요한 변경을 하지 않기 위한 if문 비교이다. 조건의 충족시 min과 max의 배열을 교환한다.
        if max_index != min_index:
            nums[min_index], nums[max_index] = nums[max_index], nums[min_index]

    return nums

풀이2 (라이브러리 x, 정답 o, 개선힌트 검색 o, 시간초과)

설명

아주 기초적인 지식만 가지고 시간초과를 해결하려 하다가 여러번의 실패끝에 개선 할 수 있는 방법에 대해서 검색을 진행후 풀어보았습니다.

우선은 위키 페이지의 개선방법을 참조하고 선택정렬 for 위키피디아 이중선택 정렬이 무엇인지 이해가 가지 않아 좀더 검색을 해보았습니다.

짧게 정리하자면 한번의 탐색에서 최소값과 최대값을 찾아 이를 동시에 정렬하는것이라고 이해했습니다.

그리고 또, 동일한 min 혹은 max의 값을 찾을 경우, 이미 그 배열도 탐색한것으로 취급하여 한번에 탐색에서 움직이게 만드는것도 개선 방식중 하나라고 이해했습니다.

그렇기에 해당 방식들을 적용하여 풀어본 문제입니다. 하지만 여전히 정답은 맞으나 시간초과가 발생했습니다.

하지만 크기가 일정 배열의 크기가 1000 이하일때는 더 속도가 느렸지만, 그 이상일때부터는 속도가 눈에 띌정도로 더 빠른 모습을 보였습니다. 그렇기 때문에 시간 초과문제를 해결하고 있다는 점은 확실했습니다.

테스트 결과

생성된 크기 : 10 / 경과 시간 : 0.000020/s

생성된 크기 : 100 / 경과 시간 : 0.000235/s

생성된 크기 : 1000 / 경과 시간 : 0.015888/s

생성된 크기 : 10000 / 경과 시간 : 0.350807/s

생성된 크기 : 50000 / 경과 시간 : 2.001006/s

생성된 크기 : 10 / 경과 시간 : 0.000022/s

생성된 크기 : 100 / 경과 시간 : 0.000226/s

생성된 크기 : 1000 / 경과 시간 : 0.015032/s

생성된 크기 : 10000 / 경과 시간 : 0.347643/s

생성된 크기 : 50000 / 경과 시간 : 1.885785/s

코드

def sortArray(nums: list[int]) -> list[int]:
    st = 0
    ed = len(nums) - 1

    while not st >= ed:
        # min, max와 동일한 숫자일 경우에 한 탐색에서 움질일수 있게 저장하기 위한 배열 변수 선언
        min_indexes = [st]
        max_indexes = [ed]

        for i in range(st, ed + 1):
            # nums[i] 의 값보다 min의 값이 더 크거나 같으면 작동합니다.
            if nums[i] <= nums[min_indexes[0]]:
                # 만약에 min이 더 크다면은 기존에 있는 min값을 i 값으로 대체합니다.
                if nums[i] < nums[min_indexes[0]]:
                    min_indexes = [i]
                # 동일하다면, min의 배열에 i 값을 추가합니다.
                elif nums[i] == nums[min_indexes[0]] and min_indexes[0] != i:
                    min_indexes.append(i)

            # min의 동작과 동일하지만 nums[i]의 값이 max의 값보다 더 클때 작동합니다.
            if nums[i] >= nums[max_indexes[0]]:
                if nums[i] > nums[max_indexes[0]]:
                    max_indexes = [i]
                elif nums[i] == max_indexes[0]:
                    max_indexes.append(i)

        # min, max는 배열형태이고, 동일한 수들은 모두 '이동'한것으로 취급하기 때문에 그에 따른 이동해야할 배열도 변화합니다.
        temp_max = ed
        temp_min = st

        for i in max_indexes:
            nums[temp_max], nums[i] = nums[i], nums[temp_max]
            # 만약 최소값들의 마지막 배열이 현재 이동한 temp_max 배열값과 동일하다면 그 배열은 움직인것 취급해야한다.
            if min_indexes[-1:][0] == temp_max:
                # 만약 현재 순회하고 있는 max의 값들이 temp_min(현재 최소 배열의 번호)의 값과 동일하다면은 그 배열은 이미 이동된것 취급해야합니다.
                # 그러므로 최소값들의 마지막 요소를 삭제하고, 그것은 이미 이동된것 취급하기 위해서 temp_min의 값을 한 단계 올려줍니다.
                if i == temp_min:
                    min_indexes.pop()
                    temp_min += 1
                # 하지만 그렇지 않다면은 최소값들의 배열의 마지막 값은 현재 조건문에서는 항상 끝점에 있으므로 그 값은 이미 현재 for max값에 배열로 이동했으니 현재 i값으로 교체를 진행합니다.
                else:
                    min_indexes[-1] = i

            # 최대값을 한번 이동하였고, 이미 이동된 배열이니 최대값을 줄여줍니다.
            temp_max -= 1

        # max 값을 선택이동하면서, 최소값들의 배열번호도 바뀌었습니다.
        # 하지만 max 선택 이동에서 배열번호의 순서를 보장하지 않아, min 정렬시 이미 정렬된 최소 배열들의 값들을 바꿀 우려가 있으므로 한번 정렬해줍니다.
        sortArray(min_indexes)

        # 최소값들을 정렬합니다.
        for i in min_indexes:
            nums[temp_min], nums[i] = nums[i], nums[temp_min]
            temp_min += 1

        # 최소 시작점과, 최대 시작점을 조정합니다.
        st += len(min_indexes)
        ed -= len(max_indexes)

    return nums

이후에도 여러가지 풀이를 진행해보았지만 여전히 시간초과는 개선되지 않았습니다. 그렇기에 해당 문제는 아직 제 역량이 미치지 못한다고 생각이들어 추후에 다시 풀어보기로 결정했습니다.