#Algorithm 01. 선택 정렬

안녕하세요!

이번 포스팅에서는 python을 통한 정렬 알고리즘 중 기초인 선택 정렬(selection sort)에 대해 알아보겠습니다.

 

🚀 선택 정렬(Selection sort)

배열에서 가장 작은 원소를 찾아 첫 번째 원소와 교환하고 두 번째 작은 원소를 찾아 두 번째 원소와 교환하고 이러한 방식으로 전체가 정렬될때 까지 계속하는 정렬입니다. 

 

 

📌 선택 정렬 예시

3,2,5,1,4가 저장된 배열이 있다고 가정하고 자료를 오름차순으로 정렬해 봅시다. 

 

 

▪️ 1회전 

첫 번째 자료 3을 기준으로 두 번째 인덱스 부터 마지막까지 비교하여 가장 작은 값(1)과 교환합니다. 이 과정에서 자료는 4번(N-1) 비교합니다.  (N = 인덱스 크기)

 

▪️ 2회전

두 번째 자료 2를 기준으로 세 번째 인덱스 부터 마지막까지 비교하여 가장 작은 값과 교환합니다. 이 때 기준인 두 번째 인덱스 값 본인이 가장 작기 때문에 교환이 일어나지 않습니다. 이 과정에서 자료는 3번(N-2) 비교합니다.

 

▪️ 3회전

세 번째 자료 5를 기준으로 세 번째 인덱스 부터 마지막까지 비교하여 가장 작은 값(3)과 교환합니다. 이 과정에서 자료는 2번(N-2)번 비교합니다. (N = 인덱스 크기)

 

▪️ 4회전

네 번째 자료 5를 기준으로 마지막 인덱스와 비교합니다. 이 때 마지막 인덱스 값(4)이 더 작음으로, 교환을 합니다. 

 

 

 

📌 선택 정렬(selection sort) 코드

선택 정렬의 pseudocode

selectionSort(a[], n)
   for (i ← 1; i < n; i ← i + 1) do {
       minIndex ← i;
       for (j ← i + 1; j ≤ n; j ← j + 1) do 
            if (a[j] < a[minIndex]) then minIndex ← j;
       a[i]와 a[minIndex]를 교환;   
       }
end selectionSort()

 

선택 정렬 with Python

def selSort(a):
    n = len(a)
    for i in range(0, n - 1):
        min_idx = i
        for j in range(i + 1, n):
            if a[j] < a[min_idx]:
                min_idx = j
        a[i], a[min_idx] = a[min_idx], a[i]

 

 

📌 선택 정렬(selection sort)알고리즘 특징 

▪️ 장점

- 실행 시간은 입력 자료의 순서에 민감하지 않다. 

- 자료 이동 횟수가 미리 결정된다. 

 

▪️ 단점

- 불안정적이다. (같은 값을 가진 자료의 순서가 바뀔 수 있다)

- 단순(구현이 비교적 쉬운) 알고리즘 이지만 비효율적인 계산

 

 

📌 선택 정렬(selection sort) 시간 복잡도

- N개의 원소 각각에 대해 N-1번의 비교

- 외부 루프 : (N-1)번

- 내부 루프(인덱스 기준 최소값 찾기)

i = 1   ->   n-1

i = 2   ->   n-2

            .

            .

            .

i = n   ->   1

따라서, 내부 루프에 대한 복잡도 = N(N-1)/2

- 전체 시간 복잡도 : T(n) = (n-1) + (n-2) + … + 2 + 1 = n(n-1)/2 =  O(n^2) 

 

📌 데이터 수에 따른 시간 복잡도 계산

Main

import random
import time

#선택 정렬 알고리즘
def selSort(a):
    n = len(a)
    for i in range(0, n - 1):
        min_idx = i
        for j in range(i + 1, n):
            if a[j] < a[min_idx]:
                min_idx = j
        a[i], a[min_idx] = a[min_idx], a[i]


#데이터 수에 따른 시간 복잡도 계산
if __name__ == "__main__":
    
    a = [random.randint(1,5000) for i in range(5000)]
    start = time.time()
    selSort(a)
    print("선택정렬 (num = 5000): {0:.2f}" .format(time.time()-start))        
    
    a = [random.randint(1,10000) for i in range(10000)]
    start = time.time()
    selSort(a)
    print("선택정렬 (num = 10000): {0:.2f}" .format(time.time()-start))        


    a = [random.randint(1,15000) for i in range(15000)]
    start = time.time()
    selSort(a)
    print("선택정렬 (num = 15000): {0:.2f}" .format(time.time()-start)) 

 

실행 결과

 

 

📌 데이터 정렬에 따른 시간 복잡도 계산

Main

import random
import time

#선택 정렬 알고리즘
def selSort(a):
    n = len(a)
    for i in range(0, n - 1):
        min_idx = i
        for j in range(i + 1, n):
            if a[j] < a[min_idx]:
                min_idx = j
        a[i], a[min_idx] = a[min_idx], a[i]
        
if __name__ == "__main__" :
    #정렬의 민감도 측정    
    a = [random.randint(1,5000) for i in range(5000)]
    start = time.time()
    selSort(a)
    print("선택정렬 난수일때(num = 5000): {0:.2f}" .format(time.time()-start)) 

    a = [i for i in range(5000)]
    start = time.time()
    selSort(a)
    print("선택정렬 순차정렬(num = 5000): {0:.2f}" .format(time.time()-start)) 


    a = [ (5000-i) for i in range(5000)]
    start = time.time()
    selSort(a)
    print("선택정렬 역순(num = 5000): {0:.2f}" .format(time.time()-start))  

 

실행 결과

즉, 데이터 정렬 상태에 따른 시간 차이는 존재하지 않습니다.