2020-09-10
선택 정렬(選擇整列, selection sort)은 제자리 정렬 알고리즘의 하나로,
다음과 같은 순서로 이루어진다.
주어진 리스트 중에 최솟값을 찾는다.
그 값을 맨 앞에 위치한 값과 교체한다(패스(pass)).
맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.
비교하는 것이 상수 시간에 이루어진다는 가정 아래,
n개의 주어진 리스트를 이와 같은 방법으로
정렬하는 데에는 Θ(n2) 만큼의 시간이 걸린다.
선택 정렬은 알고리즘이 단순하며
사용할 수 있는 메모리가 제한적인 경우에 사용 시 성능 상의 이점이 있습니다.
출처 : 위키피디아
말은 어려워 보일 수 있지만
무작이로 정렬되어 있는 배열
4 8 9 10 2 1 3 5 6 7을
1 2 3 4 5 6 7 8 9 10처럼
최솟값을 맨 앞으로 옮기는 정렬이다.
코드를 살펴보자!
소스코드 ( do ~ while 문)
예제 입력 : 4 8 9 10 2 1 3 5 6 7
Scanner scan = new Scanner(System.in);
int temp = 0;
//배열의 임시값을 받아줄 변수
//큰 수가 잠시동안 들어갈 예정
int number = -1;
int [] data = new int [10];
do {
number++;
data[number] = scan.nextInt();
}while(number < 9);
//10자리 배열에 원하는 정수 입력;
int i = -1;
//배열의 회전수를 지정할 변수
//do 문을 사용하기 때문에 -1로 입력
do {
i++;
int j = i;
do {
j++;
if(data[i] > data[j]) {
temp = data[i];
data[i] = data[j];
data[j] = temp;
}
}while(j < 9);
}while(i < 8);
for(int k = 0; k <= 9; k++) {
System.out.print(data[k]);
}
출력값 : 1 2 3 4 5 6 7 8 9 10
do while 문을 사용하여 구현하였다.
하지만 do while 보다는 변수 사용이 적은
이중 for 문으로 추가적인 구현을 해보도록 하겠다.
소스코드( 이중 for 문)
예제 입력 : 4 8 9 10 2 1 3 5 6 7
Scanner scan = new Scanner(System.in);
int [] data = new int [10];
int temp = 0;
for(int i = 0; i <data.length; i++) {
data[i] = scan.nextInt();
}
//10자리 배열에 원하는 정수 입력;
for(int i = 0; i < data.length - 1; i++) {
for(int j = i + 1; j < data.length; j++) {
if(data[i] > data[j]) {
temp = data[i];
data[i] = data[j];
data[j] = temp;
}
}
}
//이중 for 문을 사용하여 i의 위치에 따라.
//j의 값을 지속적으로 증가시키며 비교해준다.
for(int i = 0; i <data.length; i++) {
System.out.print(data[i]);
}출력값 : 1 2 3 4 5 6 7 8 9 10
코드가 훨씬 깔끔해진 것을 확인할 수 있다.
두 코드 중 어떠한 코드를 사용해도
같은 출력 값이 나오니 본인 성향이 맞게
사용하는 것이 좋을 것 같다.