선택정렬

atesi·2022년 6월 5일

algorithm

목록 보기

4/5

Chapter. 0

빅 오 표기법에서는 한 알고리즘이 다른 알고리즘보다 훨씬 빠른 경우에도 두 경쟁알고리즘을 똑같은 방식으로 표현하기도 한다.

Chapter. 1

1. 선택정렬

선택정렬의 단계를 살펴보자.

배열의 최솟값 확인.
가장 작은 값을 변수에 저장.
변수에 있는 값보다 작은 값을 만나면 대체한다.
최소값의 인덱스와 스루패스를 처음 했을 때의 값을 교환한다.

2. 예제

배열 [4,2,7,1,3]을 선택정렬 해보자.
인덱스 0을 확인하며 들어간다. 인덱스 0이 최솟값이 되었다.

1. 현재 최솟값과 2를 비교한다. 2가 최솟값이 된다.
2. 현재 최솟값과 7을 비교한다.
3. 현재 최솟값과 1을 비교한다. 1이 새로운 최솟값이 된다.
4. 현재 최솟값과 3을 비교한다. 배열의 끝에 도달했으므로 배열의 최솟값은 1
5. 1과 인덱스 0(패스스루를 시작했던 인덱스)를 교환한다.
.
.
.
12. 4와 7을 비교한다. 4가 여전히 이 패스스루의 최솟값이므로 배열이 올바르게 정렬되었다.

3. 선택정렬 구현

def selection_sort(array):
	
    #패스스루에 해당하는 루프, 이어서 현재까지의 최솟값이 들어있는 인덱스를 저장
	for i in range(len(array) - 1):
    	lowestNumberIndex = i
        
        #안쪽 루프 실행
    	for j in range(i + 1, len(array)):
    		
            # 배열 내에 아직 정렬되지 않은 각 원소를 확인해서 최솟값을 찾는다.
            # 가장 작은 수가 있는 인덱스를 변수에 계속해서 저장한다.
            if array[j] < array[lowestNumberIndex]:
            	lowestNumberIndex = j
        # 위치를 교환        
        array[i], array[lowestNumberIndex] = array[lowestNumberIndex], array[i]

효율성

선택정렬도 비교와 교환 단계로 이루어져 있다. 5개의 원소 배열이라면 10번의 비교 이와 달리 교환은 한패스스루당 한번 총 4번의 교환이 일어난다.
원소가 5개일때의 버블정렬은 20단계이고 선택정렬은 14단계이다. 10개일때는 90단계 54단계, 20개일때는 380단계, 199단계이다. 버블정렬보다 단계수가 반정도 적다. 하지만 선택정렬을 빅오로 표현하면 $O(N^2)$ 이다. 실제로는 $O(N^2/2)$ 정도로 보여진다. 하지만 빅오표기법은 상수를 무시한다.