배열을 사용한 선택정렬을 사용해보자
1. 선택정렬 (오름차순)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public static void main(String[] args) {
/*
* 5개 정수를 {95, 75, 85, 100, 50} 로 초기화하고
* 오름차순으로 정렬하는 프로그램
* 출력예) 50 75 85 95 100
* */
Scanner scn=new Scanner(System.in);
int[] a = new int[] {95, 75, 85, 100, 50};
int i, j, tmp;
for(i=0; i<4; i++) //기준값
{
for(j=i+1; j<5; j++) //비교할값 : i+1 표현해준것을 잘봐야한다.
{
if(a[i] > a[j]) //이 방법은 교환횟수가 적지않다.
{
tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
}
System.out.println();
for(j=0; j<5; j++)
{
System.out.printf("%d ", a[j]);
}
}
System.out.println();
for(i=0; i<5; i++)
{
System.out.printf("%d ", a[i]);
}
}
이방법은
- 기준값을정한다.
- 그옆값이랑 비교하여 계속 swap해준다.
그래서 더 효율적인 swap 방법을 생각해본다.
- 기준값을 정한다.
- 그옆값이랑 비교하여 비교값중 최소인값을 정한다.
- 기준값 <-> 최소인값이랑 바꾼다.
2. 선택정렬 (오름차순)
우선 잘못된예를 들자고한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public static void main(String[] args) {
//선택정렬 더쉽게 해보기
int[] a = new int[] {95, 75, 85, 100, 50};
int i, j, tmp, idx = 0;
int min = 0;
for(i=0; i<4; i++)
{
for(j=i+1; j<5; j++)
{
if(a[i] > a[j])
{
min= a[j];
idx = j;
}
}
if(min < a[i])
{
tmp = a[i];
a[i] = min;
a[idx] = tmp;
System.out.printf("min :%d", min);
}
//출력
System.out.println();
for(j=0; j<5; j++)
{
System.out.printf("%d ", a[j]);
}
System.out.println();
} // end
}
1
2
3
4
5
6
7
8
min :50
50 75 85 100 95
min :50
50 50 85 100 75
min :75
50 50 75 100 85
min :85
50 50 75 85 100
최소값이기준이 언제나 i열이되야하는데 5개의 값중 가장 작은값이 min값에 저장되어버리므로 오류가난다.
따라서 이렇게
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public static void main(String[] args) {
int[] a = new int[] {95, 75, 85, 100, 50};
int i, j, tmp, idx = 0;
int min = 0;
for(i=0; i<4; i++)
{
min = a[i]; // 비교할 기준을 잡아줘야한다.
for(j=i+1; j<5; j++)
{
if(a[i] > a[j])
{
min= a[j];
idx = j;
}
}
if(min != a[i])
{
tmp = a[i];
a[i] = a[idx];
a[idx] = tmp;
}
System.out.println();
for(j=0; j<5; j++)
{
System.out.printf("%d ", a[j]);
}
}
System.out.println();
for(i=0; i<5; i++)
{
System.out.printf("%d ", a[i]);
}
}
이렇게하면 교환을 최소화한 선택정렬을 만들수있다.
더 간편하게 하자면?
자바에서 제공하는 선택정렬 함수인 Arrays.sort(배열) 함수를 사용하면된다.
Arrays.sort 함수
1
2
3
4
5
6
7
8
9
public static void main(String[] args) {
int[] arr = new int[] {5, 4, 3, 2, 1};
int i;
Arrays.sort(arr); // java.util.Arrays클래스의 sort() 메소드
for(i =0; i<arr.length; i++)
{
System.out.printf("%d",arr[i]);
}
}
이렇게하면 완성이 빠르게 선택정렬을 구현할수있다.
그렇다면 내림차순을 구현하려면?