선택정렬(select sort)
선택정렬은 제자리 정렬 알고리즘의 방법중 하나로 단순하지만 범용성은 큰 알고리즘이다.
정렬이란 무엇인가? 프로그래밍에서 정렬은 흔히 청소, 정리라 할 수 있다.
예를들어 int []a= new int[5]{5,2,1,4,3};
의 배열이 있다고 하면 이를 적은 수부터 큰 수 순서대로 나열하는 것을 선택정렬을
사용해서 정리할 수 있는데 구현 방식은 프로그래밍 언어마다 조금씩 다르다.
책장의 책을 가나다 순으로 정리해본다고 하자. 첫째칸에 ㄱㄴㄷ로시작하는 책들이
섞여있다면 순서에따라 책의 위치를 서로 바꿔가며 ㄱㄴㄷ순으로 배치할 것이다. 하지만
자바는 객체지향언어중에 비교적 오래된 언어라 변수의 주소를 맞교환 할 수가 없다.
예를들어 a라는 변수와 b라는 변수의 주소에 저장된 값을 바꾸고 싶다면
a---->b
b---->a로 바꿀 수 없다.
a를 b로 값을 준 순간에 b에 저장되있던 값은 a로 대체되기 때문이다.
따라서 변수 하나가 더 필요하다.
a---->c
b---->a
c---->b
로 보내야 a와 b의 값이 맞교환 된다.
위의 방식이 선택정렬의 베이스가 된다.
다시 처음으로 돌아와서 크기가 5인 배열의 숫자를 최소값부터 정렬한다 하면
| 4 | 5 | 3 | 2 | 1 |
index 0과 index 4를 바꿔야하며
| 1 | 5 | 3 | 2 | 4 |
가 될 것이다. index 전체를 비교해서 가장 작은 수를 첫번째 열에 배치해 두었으므로 나머지 4열의 값을 비교해준다.
이때 바꿔야할 index는 5와 2의 값이다.
| 1 | 2 | 3 | 5 | 4 |
같은 방법을 반복한다. 3열과5열을 바꿔준다. 쭉 반복하면 최소값부터 순차적으로 배열됨을 알 수 있다.
코드로 한번 보면
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
public static void main(String[] args) {
// TODO Auto-generated method stub
//배열에서의 데이터 교환(swap)
int[] data = new int[] {4,5,3,2,1};
//정렬코드
for(int i=0;i<data.length;i++) {
for(int j=i+1;j<data.length;j++) {
if(data[i]>data[j]) {
int save=data[i];
data[i]=data[j];
data[j]=save;
}
}
}
|
cs |
가 될것이다. 처음 선택정렬을 구현하려면 값을 반복해서 비교하느라 햇갈리는 경우가 많은데 그럴땐
디버그를 사용해서 어느주소에 어떤 값이 저장되는지 한줄씩 실행해보면 비교적 이해가 쉽다.
디버그를 사용하는 방법은 다음 글에서 쓰겠다.