[자료구조] 선택정렬이란?

선택정렬

오늘은 정렬 중에서 가장 쉬운 정렬, 선택정렬에 대해서 얘기해보려고합니다.

 

선택정렬이란, 데이터가 무작위로 여러 개 있을 때, 이 중에서 가장 작은 테이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 말합니다.

 

가장 작은 것을 선택해서 앞으로 보내는 과정을 반복해서 수행하다 보면, 전체 데이터의 정렬이 이루어집니다.

 

바로 소스코드로 보시는 것이 이해하기 수월하실 겁니다.

 

소스 코드

# 선택정렬

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)):
        # min_index의 숫자보다 더 작은 숫자가 있을 시
        if array[min_index] > array[j]:
            # 그 숫자가 min_index
            min_index = j
    # 자리 스와핑, 그리고 다음 숫자로 넘어감
    array[i], array[min_index] = array[min_index], array[i]

print(array)

 

선택 정렬은 간단한 정렬 알고리즘 중 하나로, 정렬되지 않은 리스트에서 가장 작은 원소를 찾아서 해당 위치와 맞바꾸는 방식으로 동작합니다. 

 

이를 표로 나타내면 다음과 같습니다. 아래의 예시에서는 오름차순으로 정렬하는 과정을 보여줍니다.

원래 리스트: [5, 2, 9, 3, 4]

단계	현재 리스트	가장 작은 원소	가장 작은 원소의 인덱스	정렬된 부분
초기	[5, 2, 9, 3, 4]			[]
1단계	[5, 2, 9, 3, 4]	2	1	[2]
2단계	[5, 9, 3, 4]	2	1	[2]
3단계	[5, 9, 3, 4]	3	2	[2, 3]
4단계	[5, 9, 4]	3	2	[2, 3]
5단계	[5, 9, 4]	4	2	[2, 3, 4]
완료	[5, 9, 4]	5	0	[2, 3, 4, 5]

최종적으로, 선택 정렬은 원래 리스트를 반복하면서 가장 작은 원소를 찾고, 해당 원소를 정렬된 부분으로 이동시키는 과정을 반복하면서 정렬을 수행합니다. 이러한 과정을 통해 리스트가 정렬됩니다.