[Udemy] JavaScript 알고리즘 & 자료구조 마스터클래스_Section 12

* 수업은 JS 기반이지만 Python으로 구현

Section 12

선택 정렬: 소개

버블 정렬과 비슷하지만, 작은 값을 한 번에 하나씩 위치에 배열하는 방법이다. swap하는 횟수가 버블보다 적기때문에 메모리 활용면에서 더 낫기는 하지만, 일반적으로는 아주 좋지 않으며 쉽다는 장점을 가지고 있다. 몇몇 알고리즘의 준비 단계가 된다.

선택 정렬: 구현

• 최솟값을 저장할 변수 선언하고 처음에는 배열의 첫 요소와 같게 설정한다.
• 다음 요소와 비교하여 무엇이 더 작은지 비교한다.
• 다음 요소와 비교하여 더 작은 경우 그것을 최솟값으로 갱신하고, 이 행위를 배열의 끝까지 수행한다.
• 만약 최솟값이 처음과 같지 않다면, 처음것과 위치를 바꾼다.
• 다음 요소부터 위의 과정을 정렬이 다 될 때까지 반복한다.

# Selection Sort
def Select(arr):

    # i번째 요소를 Min으로 두고 나머지 요소와 비교하여
    # 더 작은 것을 Min으로 배정
    for i in range(len(arr)):

        # 최솟값 위치를 루프 내 배열 첫 번째 요소로 배정
        lowest = i

        for j in range(i+1, len(arr)):
            # 잘 수행되는지 확인하는 부분
            print(i, j, lowest, arr[lowest])

            # 배열의 최솟값 위치와 배열 j번째 비교하여 후자가 더 작다면
            # lowest값을 j로 바꾼다
            if arr[lowest] > arr[j]:
                lowest = j
        # swap
        # 루프 내 배열 첫 번째 값과 배열 lowest번 째 값을 서로 교환
        if i != lowest:
            arr[i], arr[lowest] = arr[lowest], arr[i]

        # 잘 수행되는지 확인하는 부분
        print(arr)
    
    # 정렬된 배열 return
    return arr


Select([33, 14, 223, 54, 21, 9, 0, 14])
Select([1, 2, 9, 13, 15, 6, 8])

선택 정렬: 빅오 복잡도

• 시간복잡도
  • Best: O(n^2)
  • Average: O(n^2)
  • Worst: O(n^2)
• 공간복잡도
  • O(1)