무작위의 값을 순서대로 하는 나열하는 정렬 기능은 알고리즘을 공부할 때 자주 마주치는 과제입니다. 정렬의 종류에는 여러가지가 있지만, 이번 시간에는 쉽고 간단한 선택정렬의 이론과 Java 소스를 통한 역할과 기능을 알아보겠습니다.
선택정렬 이란?
가장 핵심이 되는 선택정렬의 기능은 각각의 수를 비교하여 가장 작은 수를 앞단으로 가져오는 역할을 수행합니다.
아래의 그림을 보겠습니다.
23, 16, 11, 6, 22의 정렬되지 않은 값이 있습니다.
선택정렬의 초기 수행시 비교 값은 1번 값 23이 되며
2~5번째 까지의 값중 가장 작은 값을 1번째 방으로 이동 시킵니다.
그럼 위와 같이 가장 작은 수 6이 최 앞단으로 위치하게 됩니다.
그리고 다음은 2번째 값 16 이후의 값중 가장 작은 값인 11을 2번에 위치시킵니다.
이런식으로 N(값의 갯수)-1번 까지 계속해서 Cycle을 반복 시킵니다.
16보다 작은 값이 없기 때문에 3번째 값은 변하지 않았습니다.
마지막 23은 22보다 크기 때문에 4번방에 22가 위치하게 됩니다.
수행을 마친 후 값이 정렬되어 있는 모습입니다.
장점
- 알고리즘이 단순하다
- 값의 교환이 적어 빠르다.
- 값의 표본이 적으면 속도가 빠르다.
단점.
- 값의 표본이 늘어나면 성능이 좋지 않다.
선택정렬 Java 소스
List list = new ArrayList();
list.add(32);
list.add(1);
list.add(21);
list.add(14);
list.add(31);
System.out.println("시작 값:"+list);
int idx = 0;
int tmp = 0;
for(int i=0; i<list.size(); i++) {
idx = i;
System.out.println("ㅡㅡㅡㅡㅡ"+(i+1)+" 번째 Cycleㅡㅡㅡㅡㅡ");
for(int j=i+1; j<list.size(); j++) {
if(list.get(idx) > list.get(j)) { //기준 값보다 작은 경우 값 교환
System.out.println(list.get(idx)+"보다 "+list.get(j)+"가 더 작음");
idx = j;
}
}
if(i != idx){
tmp = list.get(idx);
list.set(idx, list.get(i));
list.set(i, tmp);
}
System.out.println((i+1)+"번째 결과 :"+list);
}
답글 남기기