선택 정렬(Selection sort) - goorm-6th-Als/for_study_Algorithm GitHub Wiki
선택 정렬 알고리즘 개념 요약
- 제자리 정렬(in-place sorting) 알고리즘의 하나
입력 배열(정렬되지 않은 값들) 이외에 다른 추가 메모리를 요구하지 않는 정렬 방법
- 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘
첫 번째 순서에는 첫 번째 위치에 가장 최솟값을 넣는다. 두 번째 순서에는 두 번째 위치에 남은 값 중에서의 최솟값을 넣는다.
- 과정
- 어진 배열 중에서 최솟값을 찾는다.
- 그 값을 맨 앞에 위치한 값과 교체한다(패스(pass)).
- 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.
- 하나의 원소만 남을 때까지 위의 1~3 과정을 반복한다.
- 1회전:
첫 번째 자료 9를 두 번째 자료부터 마지막 자료까지와 비교하여 가장 작은 값을 첫 번째 위치에 옮겨 놓는다. 이 과정에서 자료를 4번 비교한다.
- 2회전:
두 번째 자료 6을 세 번째 자료부터 마지막 자료까지와 비교하여 가장 작은 값을 두 번째 위치에 옮겨 놓는다. 이 과정에서 자료를 3번 비교한다.
- 3회전:
세 번째 자료 7을 네 번째 자료부터 마지막 자료까지와 비교하여 가장 작은 값을 세 번째 위치에 옮겨 놓는다. 이 과정에서 자료를 2번 비교한다.
- 4회전:
네 번째 자료 9와 마지막에 있는 7을 비교하여 서로 교환한다.
알고리즘 특징
- 장점
자료 이동 횟수가 미리 결정된다
- 단점
안정성을 만족하지 않는다. 즉, 값이 같은 레코드가 있는 경우에 상대적인 위치가 변경될 수 있다.