선택 정렬은 간단한 정렬 알고리즘입니다. 이 정렬 알고리즘은 목록이 왼쪽 끝에 정렬 된 부분과 오른쪽 끝에 정렬되지 않은 부분의 두 부분으로 나뉘는 내부 비교 기반 알고리즘입니다. 처음에는 정렬 된 부분이 비어 있고 정렬되지 않은 부분이 전체 목록입니다.
정렬되지 않은 배열에서 가장 작은 요소가 선택되고 가장 왼쪽 요소와 교환되며 이 요소는 정렬된 배열의 일부가 됩니다. 이 프로세스는 정렬되지 않은 배열 경계를 하나의 요소로 오른쪽으로 계속 이동합니다.
이 알고리즘은 평균 및 최악의 경우 복잡성이 다음과 같이 큰 데이터 집합에는 적합하지 않습니다.
선택 정렬은 어떻게 작동합니까?
다음 배열을 예로 들어 보겠습니다.
정렬된 목록의 첫 번째 위치에 대해 전체 목록이 순차적으로 스캔됩니다. 현재 14 가 저장된 첫 번째 위치는 전체 목록을 검색하고 10 이 가장 낮은 값이라는 것을 알게됩니다.
그래서 우리는 14 를 10 으로 바꿉니다. 목록의 최소값이 되는 반복 10 이 정렬된 목록의 첫 번째 위치에 나타납니다.
33 이 상주하는 두 번째 위치의 경우 나머지 목록을 선형 방식으로 스캔하기 시작합니다.
14 는 목록에서 두 번째로 낮은 값이며 두 번째 위치에 나타납니다. 이 값을 바꿉니다.
두 번의 반복 후에 두 개의 최소 값이 정렬된 방식으로 시작 부분에 배치됩니다.
배열의 나머지 항목에도 동일한 프로세스가 적용됩니다.
다음은 전체 정렬 과정의 그림 묘사입니다-
이제 선택 정렬의 프로그래밍 측면을 알아 보겠습니다.
알고리즘
Step 1 − Set MIN to location 0Step 2 − Search the minimum element in the listStep 3 − Swap with value at location MINStep 4 − Increment MIN to point to next elementStep 5 − Repeat until list is sorted
의사 코드
procedure selection sort list : array of items n : size of list for i = 1 to n - 1 /* set current element as minimum*/ min = i /* check the element to be minimum */ for j = i+1 to n if list < list then min = j; end if end for /* swap the minimum element with the current element*/ if indexMin != i then swap list and list end if end forend procedure
프로그래밍 언어의 선택 정렬 구현에 대해 알고 싶다면 여기를 클릭하십시오.