728x90
선택정렬(Selection Sort)은 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 그 위치에 어떤 원소를 넣을지 선택하는 알고리즘이다.
오름차순 정렬은
첫 번째 순서에는 첫 번째 위치에 가장 최소값을 넣는다.
두 번째 순서에는 두 번째 위치에 남은 값 중에서의 최소값을 넣는다.
세 번째 순서에는 세 번째 위치에 남은 값 중에서의 최소값을 넣는다.
......
1. 주어진 배열 중에서 최소값을 찾는다.
2. 그 값을 맨 앞에 위치한 값과 교환한다.
3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교환한다.
하나의 원소만 남을 때까지 위의 1~3 과정을 반복한다.
|
public class SelectionSort {
public static void printArray(int[] a){
for(int i = 0; i < a.length; i++){
System.out.print("[" + a[i] + "]");
}
System.out.print("\n");
}
public static void main(String[] args) {
int[] a = {95, 24, 68, 16, 53, 81};
// 정렬 전의 배열 내용을 표시
System.out.print("정렬 전 배열\n");
printArray(a);
System.out.print("\n");
int[] aa = arr(a);
// 정렬 후의 배열 내용 표시
System.out.print("정렬 후 배열(오름차순)\n");
printArray(aa);
System.out.println("************************");
int[] b = {95, 24, 68, 16, 53, 81};
int[] bb = brr(b);
// 정렬 후의 배열 내용 표시
System.out.print("정렬 후 배열(내림차순)\n");
printArray(bb);
}
private static int[] arr(int[] a) {
// 선택 정렬(오름차순)
int i, var, min, temp;
for (i = 0; i < a.length -1 ; i++) {
min = i;
for (var = i + 1; var < a.length; var++) {
// 맨 앞의 수를 하나씩 증가시키면서 값 비교하여 조건 비교 및 값 맞바꿈
System.out.printf("i=%d, var=%d :: ",i, var);
if (a[var] < a[i]) {
// 기준 값(i index)과 변동값(var index)을 비교하여
// 기준값(a[i])이 더 크면 맞바꿈 ==> 기준값 자리에 최소값을 넣음
min = var;
temp = a[i];
a[i] = a[min];
a[min] = temp;
System.out.printf(
"min=%d, temp=%d, a[%d]=%d, a[%d]=%d",
min,temp, i, a[i], min, a[min]
);
}
System.out.print("\n");
printArray(a);
}
}
return a;
}
private static int[] brr(int[] a) {
// 선택 정렬(내림차순)
int i, var, max, temp;
for (i = 0; i < a.length -1 ; i++) {
max = i;
for (var = i + 1; var < a.length; var++) {
// 맨 앞의 수를 하나씩 증가시키면서 값 비교하여 조건 비교 및 값 맞바꿈
System.out.printf("i=%d, var=%d :: ",i, var);
if (a[var] > a[i]) { // 배열 앞의 값이 더 크면
max = var;
temp = a[i];
a[i] = a[max];
a[max] = temp;
System.out.printf(
"max=%d, temp=%d, a[%d]=%d, a[%d]=%d",
max,temp, i, a[i], max, a[max]
);
}
System.out.print("\n");
printArray(a);
}
}
return a;
}
}
|
'안드로이드 > Java 알고리즘' 카테고리의 다른 글
| Java 삽입정렬(Insertion Sort) (0) | 2022.01.10 |
|---|---|
| Java 버블정렬(Bubble Sort) (0) | 2022.01.10 |
Link2Me