선택 정렬

선택 정렬 알고리즘

• 배열의 각 셀을 왼쪽부터 오른쪽 방향으로 확인하면서 어떤 값이 최솟값인지 결정한다.
• 예시

선택 정렬 함수 설명

# 선택 정렬 함수
def selectionSort(array):
    for i in range(len(array)):
        lowestNumberIndex = i # 가장 작은 값의 인덱스를 저장하는 변수
        for j in range(i+1, len(array)): # j는 i+1 인덱스부터 시작하면 됨

            # array[i+1] < array[i]
            ## 그러니까 뒤에 있는 애가 앞에 있는 애보다 작은지 판별해서 더 작으면 j를 lowestNumberIndex로 대입
            if array[j] < array[lowestNumberIndex]:
                lowestNumberIndex = j

        if lowestNumberIndex != j:
            temp = array[i]
            array[i] = array[lowestNumberIndex]
            array[lowestNumberIndex] = temp
    return array

• 선택 정렬은 비교와 정렬 단계로 구성
  • 각 패스스루 내에서 각 원소를 현재까지 찾은 최솟갑과 비교하고 최솟값을 올바른 위치에 있는 수와 교환
  • 원소 N가 있을 때 비교 횟수
    • (N-1) + (N-2) + (N-3) + ... + 1
  • 교환 횟수 : 패스스루마다 한 번 교환
    • 각 패스스루마다 최솟값이 이미 올바른 위치에 있느냐에 따라 교환을 안하거나 한 번 교환

선택 정렬의 효율성

• 선택 정렬은 버블 정렬보다 단계 수가 반 정도 적다
• 선택 정렬이 두 배 더 빠르다

빅 오의 역할