배열의 최소값을 원하는 위치의 값과 교환하는 정렬방식
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
