배열의 최소값을 원하는 위치의 값과 교환하는 정렬방식
int [] arr = {5,2,9,1,7}
위의 배열을 선택정렬하면 다음과 같다.
1회 : arr[]의 최소값 과 arr[0] 의 자리를 교환한다. 1,2,9,5,7
2회 : arr[0]을 제외한 값 중 최소값을 arr[1] 과 교환한다. 1,2,9,5,7
3회 : arr[0], arr[1]을 제외한 최소값과 arr[2]의 값을 교환한다. 1,2,5,9,7
4회 : 남은 최소값과 arr[3]의 값을 교환한다. 1,2,5,7,9
우선 1회 교환할 코드를 만든다.
public static void main(String[] args) { int[] arr = {5, 2, 9, 1, 7}; int i, min, temp; min = 0; for (i = 1; i < arr.length; i++) { if (arr[i] < arr[min]) { min = i; } } temp = arr[min]; arr[min] = arr[0]; arr[0] = temp; for (i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } }
교환 전 반복문으로 각 값들의 크기를 비교한다.
arr[1] < arr[0] 을 우선 비교해서 arr[0] 이 작다면 arr[2]<arr[0] 과 비교하고,
arr[1] 가 더 작다면 arr[2] <arr[1] 을 비교한다.
변수 min 을 활용해서 최소값의 인덱스를 파악한 후 반복문 종료 후 값을 변환한다.
첫 번째 교환이 일어났다.
이제 남은 교환도 진행한다.
public static void main(String[] args) { int[] arr = {5, 2, 9, 1, 7}; int i, min, temp; min = 0; for (i = 1; i < arr.length; i++) { if (arr[i] < arr[min]) { min = i; } } temp = arr[min]; arr[min] = arr[0]; arr[0] = temp; min = 1; for (i = 2; i < arr.length; i++) { if (arr[i] < arr[min]) { min = i; } } temp = arr[min]; arr[min] = arr[1]; arr[1] = temp; min = 2; for (i = 3; i < arr.length; i++) { if (arr[i] < arr[min]) { min = i; } } temp = arr[min]; arr[min] = arr[2]; arr[2] = temp; min = 3; for (i = 4; i < arr.length; i++) { if (arr[i] < arr[min]) { min = i; } } temp = arr[min]; arr[min] = arr[3]; arr[3] = temp; for (i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } }
이제 반복되는 코드를 하나로 합쳐보자
public static void main(String[] args) { int[] arr = {9, 5, 1, 3, 2}; int i, temp; for (int k = 0; k < arr.length - 1; k++) { int min = k; for (i = k + 1; i < arr.length; i++) { if (arr[i] < arr[min]) { min = i; } } temp = arr[min]; arr[min] = arr[k]; arr[k] = temp; } for (i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } }
이중 반복문으로 완성했다.
Share article