-
알고리즘 - selection sort (선택정렬)컴퓨터 기초/알고리즘&자료구조 2020. 6. 26. 03:45
선택정렬(selection sort)이란?
배열 안의 자료 중 가장 작은 수(혹은 가장 큰 수를 찾아) 첫 번째 위치 (혹은 가장 마지막 위치)의 수와 교환해주는 방식의 정렬을 말한다.
선택은 교환 횟수를 최소화하지만, 반면에 각 자료를 비교하는 횟수는 증가한다.
간단히 말하면 1~10까지의 숫자가 뒤섞여 있으면, 가장 작은 숫자인 1을 찾아서 가장 왼쪽에 배열하고, 그 다음에는 1을 제외한 2~10이 뒤섞인 숫자에서 2를 찾아서 1 다음 배치하는 식으로 반복하여 정렬하는 방식을 말한다.
list a = [3, 2, 5, 4, 1] 첫번째 리스트 a내의 n개의 숫자 중 가장 작은 숫자를 찾는다. 가장 작은 숫자 1을 가장 왼쪽에 놓는다. list a = [1, 3, 2, 5, 4] 이제 1을 제외한 n-1개의 숫자 중에서 가장 작은 숫자를 찾는다. 가장 작은 숫자 2를 1을 제외한 가장 왼쪽에 놓는다. list a = [1, 2, 3, 5, 4] 이제 1, 2를 제외한 n-2개의 숫자 중에서 가장 작은 숫자를 찾는다. 가장 작은 숫자 3은 1, 2 다음 제 위치에 있으니 그냥 둔다. list a = [1, 2, 3, 5, 4] 이제 1, 2, 3,을 제외한 n-3개의 숫자 중에서 가장 작은 숫자를 찾는다. 가장 작은 숫자 4는 1, 2, 3 다음 가장 왼쪽에 둔다. list a = [1, 2, 3, 4, 5] 정렬이 완료되었다.
버블 정렬에 비해 교환 횟수는 적지만, 더 많은 비교가 필요해서 자원소모가 크다.
선택 정렬은 결국 버블 정렬에 비해 이득인 것 같지만 실제로는 교환보다 비교를 위한 탐색에 대한 자원 소모가 크다.
선택이나 버블 정렬이나 큰 관점에서는 큰 차이를 만들지 못한다.
식으로 따지면 n(n+1)/2을 진행해야 정렬이 완료된다.
'컴퓨터 기초 > 알고리즘&자료구조' 카테고리의 다른 글
알고리즘의 시간을 표현하기(시간복잡도 / Time Complexity) (0) 2020.07.21 알고리즘 - merge sort (합병정렬) (0) 2020.07.21 알고리즘 - bubble sort(버블 정렬) (0) 2020.06.26 알고리즘 - 선형탐색, 이진탐색 (0) 2020.06.26 알고리즘의 이해 (0) 2020.06.26