이 글은 이것이 취업을 위한 코딩 테스트다 with 파이썬을 보고 작성하였습니다.

정렬이란

정렬이란 데이터를 특정한 기준에 따라서 순서대로 나열한 것을 의미합니다.

프로그램에서 데이터를 가공할 때 오름차순이나 내림차순 등으로 정렬해서 사용하는 경우가 많기에 많이 사용되는 알고리즘 중 하나입니다.

이 정렬 알고리즘으로 데이터를 정렬하면 이진 탐색이 가능해집니다.
이진 탐색 정리 후 링크 연결

선택 정렬

1. 개요

데이터가 무작위로 있을 때, 이 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복하는 것이 선택 정렬입니다.

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

가장 원시적인 정렬 알고리즘으로 매번 '가장 작은 것을 선택한다'는 의미에서 선택 정렬 이라고 불립니다.

2. 선택 정렬 예시

처리된 것은 하늘색, 처리하고 있는 것은 회색으로 표시하겠습니다.

1. 초기 단계에서는 모든 데이터가 정렬되어 있지 않으므로, 전체 중에서 가장 작은 데이터를 선택합니다. 따라서 '0'과 맨 앞에 있는 데이터인 '4'를 변경합니다.

2. 이제 정렬된 데이터는 제외하고 정렬되지 않은 데이터 중에서 가장 작은 데이터인 '1'을 선택해서 처리되지 않은 데이터 중 가장 앞에 있는 데이터 '3'과 바꿉니다.

3. 다시 step 2와 마찬가지로 정렬된 데이터는 제외하고 정렬되지 않은 데이터 중에서 가장 작은 '2'를 선택합니다. 이를 처리하지 않은 데이터 중 가장 앞에 있는 '4'와 바꿉니다.

4. 위와 같은 과정을 반복하면 됩니다. 가장 작은 데이터를 앞으로 보내는 과정을 4번 반복한 상태에는 아래와 같고 마지막 데이터는 가만히 두어도 이미 정렬된 상태입니다. 따라서 이 단계에서 정렬을 마칠 수 있습니다.

3. 선택 정렬 코드

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 = j

    # 스와프를 사용하여 값 변경
    array[i], array[min_index] = array[min_index], array[i]

print(array)

4. 시간 복잡도

선택 정렬은 N-1(여기서 N은 원소의 개수)번 만큼 가장 작은 수를 찾아서 맨 앞으로 보냅니다.

또한 매번 가장 작은 수를 찾기 위해서 비교 연산이 필요합니다.

따라서 앞의 그림대로 구현하면 연산 횟수는 N + (N - 1) + (N - 2) + ... + 2로 볼 수 있습니다.

이 등차수열을 근사치로 N * (N + 1) / 2번의 연산을 수행한다고 가정하면, 이는 (N^2 + N) / 2인데 빅오 표기법으로는 O(N^2)이라고 표현할 수 있습니다.

시간 복잡도 O(N^2)은 만약 데이터의 개수가 100배로 늘어나면, 수행 시간은 10,000배로 늘어나므로 상당히 느린 편입니다.