Python을 사용하여 설명하는 정렬 알고리즘: 선택 정렬

반응형

건배! 이전 기사에서 다루었던 삽입 정렬에 이어 오늘은 선택 정렬에 집중하겠습니다.

이 알고리즘은 O(N²) 평균 복잡성을 특징으로 합니다. 안타깝게도 최적의 성능(O(N²)을 살펴보면 상황이 더 나아 보이지 않지만, 적어도 더 나빠지지는 않으며 최악의 성능은 O(N²)입니다.

선택 정렬의 2차 복잡성은 큰 목록에서 비효율적으로 만든다. 유사한 알고리즘인 삽입 정렬은 일반적으로 이것보다 성능이 우수합니다. 그러나 그 단순성은 주목할 만하며 메모리 제약이 매우 엄격한 경우에는 더 복잡한 알고리즘보다 더 나은 성능을 발휘할 수 있습니다.

좋아, 그럼 이 알고리즘은 왜 움직이는 거지? 음, 그것은 내부 비교 정렬 알고리즘으로 표현됩니다. 입력 배열을 두 개의 배열로 볼 수 있는데, 맨 왼쪽이 정렬된 배열이고, 맨 오른쪽이 정렬되지 않은 섹션이 처음에는 전체 입력 배열과 동일합니다. 정렬된 섹션은 모든 요소를 정렬된 섹션으로 이동할 때까지 정렬되지 않은 컬렉션에서 요소를 얻습니다(내림차순으로 이동할 경우 최대값). 이 알고리즘의 2차 복잡도가 어느 정도인지 이미 알 수 있을 것입니다. 고려할 N개의 항목과 정렬되지 않은 한 항목의 집합에서 최소값을 찾기 위한 최대 N개의 연산입니다.

 

이 알고리즘의 또 다른 단점은 버블 정렬과 달리 모든 요소를 반복하기 전에는 배열이 정렬되었는지 확인할 수 없다는 것입니다.

하지만, "짐승의 배"에서 바로 뛰어내리자. 그리고 그렇게 하는 것보다 더 좋은 방법이 무엇이 있을까? 삽입 정렬을 사용하여 오름차순으로 정렬해야 하는 arr=[5, 4, 3, 2, 1]을 고려하십시오.

• i=0, 정렬된 섹션은 []이고 정렬되지 않은 섹션은 [5, 4, 3, 2, 1]입니다;
• 정렬되지 않은 섹션의 최소값이 필요합니다— 1;
• 전체 배열의 지수는 4이다.
• 나는 4와 같지 않으니 arr[i]와 arr[4]; arr=[1, 4, 3, 2, 5];
• i=1, 정렬된 섹션은 [1]이고 정렬되지 않은 섹션은 [4, 3, 2, 5]입니다;
• 정렬되지 않은 섹션의 최소값 - 2;
• 전체 배열의 지수는 3이다.
• 나는 3과 같지 않으니 arr[i]와 arr[3]; arr=[1, 2, 3, 4, 5];
• 배열은 이미 정리가 되었지만, 우리는 끝까지 계속할 것입니다.
• i=2, 정렬된 섹션은 [1, 2]로 간주되고 정렬되지 않은 섹션은 [3, 4, 5]입니다;
• 정렬되지 않은 섹션의 최소값이 필요합니다 — 3;
• 전체 배열의 지수는 2이다.
• I는 2와 같으므로 이번에는 스왑이 발생하지 않습니다.
• i=3, 정렬된 섹션은 [1, 2, 3], 정렬되지 않은 섹션은 [4, 5];
• 정렬되지 않은 섹션의 최소값 — 4;
• 전체 배열의 지수는 3이다.
• I는 3과 같으므로 이번에는 스왑이 발생하지 않습니다.
• i=4, 정렬된 섹션은 [1, 2, 3, 4]로 간주되고 정렬되지 않은 섹션은 [5]입니다;
• 정렬되지 않은 섹션의 최소값(및 유일한 값)은 5이다.
• 전체 배열의 지수는 4이다.
• I는 4와 같으므로 이번에는 스왑이 발생하지 않습니다.
• 루프가 끝나면 배열은 다음과 같습니다. [1, 2, 3, 4, 5]

아래 전체 파이썬 코드:

def selection_sort(arr):
    """Selection sort algorithm."""

    # iterate through all of the elements
        for i, _ in enumerate(arr):

                # get minimum index in unsorted section
                        # for descending order, change min() to max()
        min_index = arr.index(min(arr[i:]))

        # ensure minimum element is on i position
                if i != min_index:
                            arr[i], arr[min_index] = arr[min_index], arr[i]
return arr

 

꽤 간단하죠, 그렇죠? 아직 확실하지 않은 질문이나 문제가 있으면 알려주십시오. 그러면 모든 것이 해결됩니다(를 의도함).

또 다른 정렬 알고리즘 다이빙을 마쳤으니, 다음 번에서 뵙기를 고대하겠습니다! 건배와 해피 코딩!