[알고리즘/선택정렬] #Selection Sort / in Python

선택 정렬

숫자를 오름차순으로 정렬하는 프로그램

---

arr = [3, 4, 5, 1, 2]이라는 리스트가 있을 때 이것을 어떻게 오름차순으로 정렬할까? 

가장 작은 숫자를 선택해서 앞으로 보내는 방법을 가장 먼저 떠올릴 수 있다.

#1 [1, 4, 5, 3, 2] #1과 3을 자리 바꾸기
#2 [1, 2, 5, 3, 4] #2와 4 자리 바꾸기
#3 [1, 2, 3, 5, 4] #3과 5 자리 바꾸기
#4 [1, 2, 3, 4, 5] #4와 5 자리 바꾸기

순서로 진행된다.

---

코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

''' #반복문 사용 i, j >>> 배열에 있는 원소 반복적으로 탐색 min_index >>> 최솟값 원소 "위치" ''' def selection_sort(arr):     for i in range(len(arr) - 1):         min_index = i #0123         for j in range(i + 1, len(arr)): #1234             if arr[min_index] > arr[j]: #가장작은 값 인덱스 찾기                 min_index = j #최소값 인덱스         arr[i], arr[min_index] = arr[min_index], arr[i]     return print(arr)   if __name__ == '__main__':     arr = [3, 4, 5, 1, 2]     selection_sort(arr)

처음 코드를 보고 이해하는데 쉽지 않다.

 if문 안쪽이 이해하기 어려웠는데, 쉽게 말해서 
i = 0 일 때, 그 뒤 숫자 중 최솟값의 번호를 찾아 스왑을 한다.
가장 최솟값일 때 min_index의 안에 j값을 넣어 저장 변수를 선언해준다.
선택 정렬의 핵심은 한 개를 선택하고 나머지 전체를 보는 방식이다.

 이를 통해 시간 복잡도를 알 수 있다.
O()를 시간 복잡도의 기호로 나타낸다.

#빅오(Big O) 표기법
선택 정렬의 시간 복잡도는 (N * (N + 1)) / 2 가 된다.

 풀면 (N^2 + N) / 2 가 되는데, N을 데이터라고 생각하고, 이 데이터의 양이 엄청난 숫자로 많아진다면,
일반적인 N을 더하는 것(상수)과 2로 나누는 것은 의미 없는 것으로 생각하여

선택 정렬의 시간 복잡도는 O(N^2)가 된다.

N^2은 수학 시간에 배웠던 2차 그래프로 시각화하여 생각해 볼 수 있다.
X축이 증가함에 따라 Y축은 기하급수적으로 증가하게 된다.
데이터 양이 1억 개, 10억 개 를 넘어가게 되면 여기서 오는 시간 소모는 엄청나다.