[Algorithm] 정렬 - Selection Sort (선택 정렬)

[Algorithm] 정렬 - Selection Sort (선택 정렬)

Selection Sort

처음 index부터 마지막 index까지의 이동하며 최대값을 찾은 후 저장하는 방식

k-index에 들어갈 원소를 찾기위해서 k-1번 최대값을 찾는 비교를 해야하므로 O(n^2)이다.

https://en.wikipedia.org/wiki/Selection_sort

동작

Step1

Step2

Step3

Step4

Step5

Step6

코드 (Java)

public class Sort { public void swap(arr, index1, index2) { int temp = arr[index1]; arr[index1] = arr[index2]; arr[index2] = temp; } public void selectionSort(arr) { for(int i = arr.length-1; i >= 0; i--) { int maxIndex = i; int j; for(j = 0; j < i; j++) { if(arr[j] > arr[maxIndex]) { maxIndex = j; } } swap(arr, i, maxIndex); } } }

from http://jino-dev-diary.tistory.com/31 by ccl(A) rewrite - 2021-09-13 18:01:22