Algorithm - 선택 정렬(selection sort)

 

안녕하세요 :-)

 

이번 포스팅은 선택정렬 알고리즘에 대해 다루어보겠습니다.

 

정렬 알고리즘은 여러가지가 존재 하지만 각각의 효율성과 구현 난이도에서 차이가 드러납니다.

 

선택정렬 알고리즘의 경우 O(n^2)의 시간복잡도를 갖는 처리 속도가 비교적 좋은 알고리즘은 아니지만 정렬의 매커니즘을 이해하기 편하고 그만큼 구현이 쉽기때문에 가장 먼저 다루어볼 알고리즘입니다.

 

정렬할 타겟배열 내에서 가장 작은 값을 선택하여 가장 앞으로 보내는 아이디어를 이용하는 알고리즘으로 디버깅 과정은 아래와 같습니다.

 

 

정렬 절차

1. 전체배열을 조건검사하여 가장 작은 값을 첫번째 인덱스와 스위치 시킵니다.

2. 첫번째 인덱스를 제외한 나머지 배열을 조건검사하여 가장 작은 값을 두번째 인덱스와 스위치 시킵니다.

3. 첫번째와 두번째 인덱스를 제외한 나머지 배열을 조건검사하여 가장 작은 값을 세번째 인덱스와 스위치 시킵니다.

.

.

.

n. n-1번째 까지의 인덱스를 제외한 나머지 배열을 조건검사하여 n번째 인덱스와 스위치 합니다.

 

결과

위와 같은 과정을 거친다면 1번인덱스 부터 n번 인덱스까지 작은값이 순서대로 스위치되기때문에 최종적으로 오름차순으로 정렬된 배열을 얻을수 있습니다.

 

 

백준 사이트 문제 풀이(2750) 

사용 언어: python3

n = int(input())
lis = []
for i in range(n):
    lis.append(int(input()))
 
i =0
index=0
while(i<n):
    j=i
    min=1001
    while(j<n):
        if(lis[j]<min):
            min=lis[j]
            index = j
        j+=1
    
    temp = lis[i]
    lis[i] = lis[index]
    lis[index] = temp
    i+=1
 
 
for i in range(len(lis)):
    print(lis[i])

 

 

 

 

마치며)

이번 포스팅을 통해 선택정렬 알고리즘에 대해 다루어보고 백준 온라인 사이트의 시간복잡도 O(n^2)을 갖는 문제를 풀어 봄으로서 코드로 구현도 해보았습니다. 다음포스팅에서는 버블정렬에 대하여 다루어 보겠습니다.