🥭Selection Sort

orders

★ 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꿈 (오름차순 정렬 가정) ★

 

① 정렬할 데이터 준비

 

(7 5 9 0 3 1 6 2 4 8)

 

② 처리되지 않은 데이터(7부터 8 전체) 중 가장 작은 0을 선택해 맨 앞의 7과 바꾼다.

 

7 5 9 0 3 1 6 2 4 8

(0과 7을 바꾼다)

 

0 (5 9 7 3 1 6 2 4 8)

 

③ 처리되지 않은 데이터(위 괄호 5부터 8) 중 가장 작은 1을 선택해 가장 앞의 5와 바꾼다.

 

0 5 9 7 3 1 6 2 4 8

(1과 5를 바꾼다)

 

0 1 (9 7 3 5 6 2 4 8)

 

④ 처리되지 않은 데이터가 맨 오른쪽 1개가 있을 때까지 반복한다(맨 마지막 1개의 데이터는 자동 정렬됨)

 

0 1 2 3 4 5 6 7 8 9 (최종 결과)

 

★ 매번 선형탐색을 수행하는 것이므로 이중 반복문을 이용해서 선택 정렬 구현 ★

about selection sort

★ selection sort algorithm sorts an array by repeatedely finding the minimum element(considering ascending order) from the unsorted part and putting it at the beginning, the algorithm maintains two subarrays (sorted subarray & unsorted remaining subarray).

 

★ in every iteration of the selection sort, the minimum element(considering ascending order) from the unsorted subarray is picked and moved to the sorted subarray

 

★ 《sorted subarray + unsorted subarray structure》 is repeated until the length of the unsorted subarray equals to 1

 

★ repeatedly searches remaining items to find the smallest element and moves it to the correct location.

 

★ (아래 python code) 첫 for문에서 i가 0일 경우 N-1번 반복, i가 1일 경우 N-2번 ... 이렇게 진행되어 마지막으로 i가 len(array)-1일 경우 1번 돌아감. 따라서 (N-1) + (N-2) + .... 1 = (N*(N-1))/2로 Big-O Notation에 의해 O(N^2) 시간 복잡도

selection sort code / image

array = [7,5,9,0,3,1,6,2,4,8]
for i in range(len(array)):
    min_index = i #the smallest element's index
    for j in range(i+1, len(array)):
        if array[min_index] > array[j]:
            min_index = j
        #find the smallest element's index in given range - and put it in min_index
    #after finding the smallest min_index, swap it.
    array[i], array[min_index] = array[min_index], array[i] #swap
print(array)

 

※ 그림 참고 ※

 

examples

🥭 <BOJ B1 23881 알고리즘 수업 - 선택 정렬 1>

Q. 지정 swap번째의 두 원소 출력. 이 때, 위와 다르게 오른쪽부터 진행해 subarray의 최댓값이 i 위치의 element와 다르다면 swap 진행(index 정석대로 이중 for문하면 시간 초과 발생. 따라서 max()로 값 비교한 뒤 index 구하고 swap)

 

🥭 <BOJ B1 23882 알고리즘 수업 - 선택 정렬 2>

Q. 위 문제와 완전히 동일. 다만 지정 swap진행 뒤의 array 출력

 

🥭 <BOJ G4 23883 알고리즘 수업 - 선택 정렬 3>

Q. 현재 arr의 index를 저장한 sorted_dict 딕셔너리에서 cur_max index와 cur_order가 다를 경우 서로 swap. (1~N까지의 자연수가 있는 특수 정렬)(

ex) arr = [3, 1, 2, 5, 4]라면 sorted_dict는 {1:1, 2:2, 3:0, 4:4, 5:3}. 그리고 cur_max는 5 / cur_order는 4 / cur_max_index는 3 : cur_order와 cur_max_index가 다르므로 swap 진행

 

🥭 <BOJ G4 23884 알고리즘 수업 - 선택 정렬 4>

Q. 위 23883과 동일. swap번째일 때 배열 내용 출력

 

🥭 <BOJ B1 23899 알고리즘 수업 - 선택 정렬 5>

Q. 위 문제와 마찬가지로 똑같고, 도중의 배열이 B 배열과 같은 지의 여부 출력. 나 자신을 포함한 subarray에서 최댓값을 구하고, 나 자신과 최댓값이 다르다면 swap 진행. swap 진행의 기준이 약간 다르다는 점만 고려하면 OK

 

🥭 <BOJ G3 23900 알고리즘 수업 - 선택 정렬 6>

Q. 23883 / 23884 와 동일. swap하는 과정에서 두번째 배열과 동일할 때 출력

 

🥭 <BOJ S3 28116 선택 정렬의 이동 거리>

Q. 주어진 정렬이 1~N까지의 자연수가 있는 정렬. 따라서 idx dictionary 활용해서 idx 간의 거리로 선택 정렬에서 element를 이동하는 거리로 설정하는 특수한 문제.

---

내용 일부

내용 일부 이코테 2021