[자료구조] 선택 정렬 concept, 분석

Sorting은 순서없이 배열된 자료를 오름차순/내림차순 순서로 재배열 하는 것으로, sorting상에서 key는 자료를 정렬하는데 사용하는 기준이 되는 특정 값을 뜻한다.

 

내부정렬 중 선택정렬은, 전체 원소들 중에서 기준 위치에 맞는 원소를 선택하여 자리를 교환하는 방식으로 정렬하는 sorting방법으로서, 전체 원소들 중 가장 작은 원소를 찾아 첫번째에 위치 > 두번째로 작은 원소를 찾아 두번째에 위치 를 마지막 원소까지 진행하는 방식이다.

 

선택정렬의 경우 시간복잡도는 O(n^2)가 된다. (비교 횟수는 첫번째 원소는 n개, 두번째는 n-1개 ...1개까지 비교하므로 전체 합은 n^2). 어느 경우에나 비교 횟수가 같은 것이 특징이다.

 

[python 코드] 

def selection_sort(arr):
    n = len(arr)

    for i in range(n - 1):
        # 현재 인덱스를 최소값으로 가정
        min_index = i

        # 나머지 요소들과 비교하여 최소값 찾기
        for j in range(i + 1, n):
            if arr[j] < arr[min_index]:
                min_index = j

        # 현재 인덱스와 최소값을 교환
        arr[i], arr[min_index] = arr[min_index], arr[i]

# 예시
my_array = [64, 25, 12, 22, 11]
selection_sort(my_array)

print("정렬된 배열:", my_array)