정렬-선택 정렬(selection sort)

*정렬-선택 정렬(selection sort)

-수열 중에서 최솟값을 검색해 왼쪽 끝 숫자와 교체하는 작업 반복하여 정렬

-수열 중 최솟값을 찾을 때는 선형 탐색 사용

-1라운드에서 n-1회, 2라운드에서 n-2회가되며 비교횟수는 버블정렬과 같은  n²/2 가 됨

-숫자 교체는 각 라운드에서 최대 1회

-입력 데이터가 작은 순으로 나열되어 있다면 교체는 한 번도 발생하지 않음

 

*선택 정렬의 예

-1부터 9까지의 숫자 정렬(6-1-7-8-9-3-5-4-2)

-수열을 선형 탐색하여 최솟값(1) 찾고 왼쪽 끝 숫자와 교체(1-6-7-8-9-3-5-4-2)

-정렬 반복

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

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

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

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

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

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

-정렬 완료

 

 

 

 

---

이 포스팅에 작성한 내용은 이시다 모리테루, 미야자키 쇼이치, ⌜알고리즘 도감⌟, 김완섭 옮김, (주)제이펍, 2020 에서 발췌하였습니다.