선택 정렬(Selection Sort)

 

선택 정렬 알고리즘은 https://visualgo.net/en/sorting 사이트로 들어가면 시각화 해서 확인할 수 있다.

데이터가 정렬되는 과정을 시각화한 영상을 참고하면서 포스팅을 함께 읽으면 정렬 알고리즘을 이해하는데 큰 도움이 될 것이라 생각한다.

 

정렬 알고리즘 다른 포스팅

2023.01.01 - 삽입 정렬(Insertion Sort)

선택 정렬(Selection Sort)

array=[7,5,9,0,3,1,6,2,4,8];

for i in range(len(array)):
    min_index=i
    for j in range(i+1,len(array)):
        if array[min_index]>array[j]: # min_index=>max_index로 고치고 부등호를 반대로 하면 내림차순으로 정렬할 수 있다.
            min_index=j

    array[i],array[min_index]=array[min_index],array[i] # 파이썬에서는 이와 같은 방식으로 간단히 SWAP을 작성할 수 있다.

print(array)

배열의 정렬되지 않은부분 중에서 가장 작은 값을 가지고 있는 index를 찾아 앞쪽부터 채워넣는다.

 

STEP0 : i=0 , j=1부터 순회

min_index=3이므로 SWAP(array[0],array[3])을 수행한다. (i==0이기 때문)

현재 array=[0,5,9,7,3,1,6,2,4,8]

 

STEP1 : i=1 , j= 2부터 순회

(j는 i+1부터 시작한다 이유는 0~i-1까지의 인덱스는 이미 정렬된 부분이므로 확인하지 않아도 되기때문이다.)

min_index=5 이므로 SWAP(array[1],array[5])를 수행한다. (i==1 이기 때문)

현재 array=[0,1,9,7,3,5,6,2,4,8]

 

STEP2 : i=2, j=3 부터 순회

min_index=7 이므로 SWAP(array[2],array[7])을 수행한다. (i==2)

현재 array=[0,1,2,7,3,5,6,9,4,8]

 

STEP3 : i=3, j=4 부터 순회

min_index=4 이므로 SWAP(array[2],array[7])을 수행한다. (i==2)

현재 array=[0,1,2,3,7,5,6,9,4,8]

 

위와 같은 형식으로 배열의 끝까지 진행된다.

최종 결과로는 array=[0,1,2,3,4,5,6,7,8,9]와 같이 정렬될 것이다.

 

아래는 선택정렬을 설명하는 유튜브 영상이다. 포스팅과 위에 첨부한 시각화 사이트를 확인하고도 이해가 가지 않는다면 참고하길 바란다.

 

 

 

시간복잡도

선택정렬의 시간 복잡도는 이중 for문이므로 O(N²)이다.

이는 퀵정렬이나 파이썬 기본 정렬 라이브러리를 사용하는것 보다 훨씬 느린 방식이다.

가장 단순하게 정렬알고리즘을 구현 할 수 있는 방법이지만 기본 라이브러리에 정렬이 포함되어있는 파이썬에서는 그닥 사용할 일이 잘 없을것으로 보인다.