[자료구조][정렬 알고리즘]선택 정렬(Selection Sort)

선택 정렬은 가장 간단한 정렬 알고리즘입니다. 

선택 정렬은 우리가 실생활에서 가장 많이 사용하는 알고리즘 이기도 하며,

기준 위치에 맞는 원소를 선택해 정렬하는 방식입니다.

 

 

출처 : https://youtu.be/Ns4TPTC8whw

 

 

위 동영상은 선택 정렬을 포크로 표현한 동영상으로 한번 보시면 어느 정도 감이 잡히실 겁니다.

선택 정렬을 Java 코드로 구현해 보았습니다.

 

 

 

 

코드를 간략히 설명드리면 우선 위의 함수는 숫자형 배열 arr과 배열의 크기인 max를 인자로 받는 함수입니다.

 

위의 함수에 배열 arr 이 {20, 1, 35, 23, 5, 6}

max값이 6이 들어왔을 경우

 

첫 번째 for문이 시작되고

초기 minIndex는 0

min은 20이 들어가게 됩니다. (40,41 라인)

 

그리고 기준값은 min과 그다음 열들을 비교하기 위한

for문이 작동하게 됩니다. 

두 번째 for문을 보시면 j = i+1 즉 minIndex의 다음 인덱스를

가리키고 있습니다.

따라서 if 문을 통해 min값인 20과 arr [j] 값인 1을 비교하여

min값이 arr [j]보다 크면 min값에 arr [j]을 넣어주고 인덱스 또한 변경해줍니다.

동일하게 그 뒤에 값들도 비교를 해준 후 두 번째 for문이 끝나면

arr [i] 즉 arr [0] 번째에 가장 작은 값인 min을 넣어주고 

가장 작은 값이 원래 있던 위치에 arr [0]의 값을 넣어줍니다.(51,52라인)

 

위와 동일한 방법으로 다시 arr [0]~ arr [5]까지 비교하여 정렬하게 되는 로직입니다.

 

 

위의 로그를 보시면 정렬되기 전 {20, 1, 35, 23, 5, 6}에서 최종적으로 {1, 5, 6, 20, 23, 35}가 되어 있는 것을 확인할 수 있습니다.

 

선택 정렬은 실행 시간이 max의 제곱에 비례하기 때문에 큰 자료에 대해서는 적용이 힘들지만 알고리즘이 간단하고 교환 횟수가 적어 큰 레코드의 직접 정렬에는 효용이 있지만,

같은 키의 상대적 순서가 정렬 후에도 변함이 없음을 뜻하는 안정성은 없습니다.

 

※ 필자는 아직 배울 것이 많은 초보 개발자입니다. 잘못된 부분이나 고쳤으면 하는 부분은 댓글을 통해 알려주시면 감사하겠습니다.
도움이 되셨다면 밑에 공감 버튼 부탁드리겠습니다.