선택정렬 (selectionSort) Java로 구현하기

선택정렬이란?

선택 정렬(選擇整列, selection sort)은 제자리 정렬 알고리즘의 하나로, 다음과 같은 순서로 이루어진다.

1. 주어진 리스트 중에 최솟값을 찾는다.
2. 그 값을 맨 앞에 위치한 값과 교체한다(패스(pass)).
3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.

비교하는 것이 상수 시간에 이루어진다는 가정 아래, n개의 주어진 리스트를 이와 같은 방법으로 정렬하는 데에는 Θ(n²) 만큼의 시간이 걸린다.

출처 - 위키

출처는 위키가 최고다.

그럼 이제 자바로 구현해보자

public static void main(String[] arg){

int[] arr = {3,1,2,10,3,99, 19};

selectionSort(arr);

System.out.println(Arrays.toString(arr));

  }

public static void selectionSort(int[] arr) {

for(int i=0; i<arr.length; i++ ) {

int minIdx = i;

for(int j=i; j<arr.length;j++ ) {

if( arr[j] < arr[minIdx] ) {

minIdx = j;

}

}

// 제일 작은 인덱스와 i의 자리를 교체한다.

int temp = arr[i];

arr[i] = arr[minIdx ];

arr[minIdx] = temp;

}

}