반응형
목표
- 선택 정렬 알고리즘을 이해한다.
- 선택 정렬 알고리즘을 구현한다
- 선택 정렬 알고리즘의 특징
- 선택 정렬 알고리즘의 시간복잡도를 이해한다.
오름차순을 기준으로 정렬한다.
선택정렬(selection sort) 알고리즘 개념 요약
- 제자리 정렬(in-place sorting)알고리즘의 하나
입력 배열(정렬되지 않은 값들) 이외에 다른 추가 메모리를 요구하지 않는 정렬 방법 - 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤원소를 넣을지 선택하는 알고리즘
첫 번째 순서에는 첫 번째 위치에 가장 최솟값을 넣는다.
두 번째 순서에는 두 번째 위치에 남은 값 중에서의 최솟값을 넣는다. - 과정 설명
주어진 배열 중에서 최솟값을 찾는다.
그 값을 맨 앞에 위치한 값과 교체한다(패스(pass)).
맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.
하나의 원소만 남을 때 까지 위의 1~3과정을 반복한다.
선택 정렬(selection sort) 알고리즘의 구체적인 개념
선택 정렬은 첫 번째 자료를 두 번째 자료부터 마지막 자료까지 차례대로 비교하여 가장 작은 값을 찾아 첫 번째에 놓고, 두 번째 자료를 세 번째 자료부터 마지막 자료까지와 차례대로 비교하여 그 중 가장 작은 값을 찾아 두 번재 위치에 놓는 과정을 반복하며 정렬을 수행한다.
1회전을 수행하고 나면 가장 작은 값의 자료가 맨 앞에 오게 되므로 그 다음 회전에서는 두 번 째 자료를 가지고 비교 한다. 마찬가지로 3회전에서는 세 번째 자료를 정렬한다.
선택 정렬(selection sort) 알고리즘의 예제
배열에 9,6,7,3,5가 저장 되어 있다고 가정하고 자료를 오름차순으로 정렬해보자.
- 1회전:
첫 번째 자료 9 를 두 번째 자료부터 마지막 자료 까지와 비교하여 가장 작은 값을 첫 번째 위치에 옮겨 놓는다. 이 과정에서 자료를 4번 비교한다. - 2회전:
두 번째 자료 6을 세 번째 자료부터 마지막 자료까지와 비교하여 가장 작은 값을 두 번째 위치에 옮겨 놓는다. 이 과정에서 자료를 3번 비교한다. - 3회전:
세 번째 자료 7을 네 번째 자료부터 마지막 자료까지와 비교하여 가장 작은 값을 세 번째 위치에 옮겨 놓는다. 이 과정에서 자료를 2번 비교한다 - 4회전:
네 번째 자료 9와 마지막에 있는 7을 비교하여 서로 교환한다.
선택 정렬의 장점
-자료 이동 횟수가 미리 결정된다.
-데이터양이 적을 때 좋은 성능을 나타냄
-작은 값을 선택하기 위해서 비교는 여러번 수행 되지만 교환 횟수가 적다.
선택 정렬의 단점
-안정성을 만족하지 않는다.
-즉, 값이 같은 레코드가 있는 경우에 상대적인 위치가 변경될 수 있다.
-100개 이상의 자료에 대해서는 속도가 급격히 떨어져 적절히 사용되기 힘들다.
java 코드
public class Selection {
public void sort(int[] data) {
int size = data.length;
int min; //최소값을 가진 데이터의 인덱스 저장 변수
int temp;
for(int i = 0; i < size-1; i++) {
min =i;
for(int j=i+1; j<size; j++) {
if(data[min] > data[j]) {
min = j;
}
}
temp = data[min];
data[min]=data[i];
data[i] = temp;
}
}
public static void main(String[] args) {
Selection selection = new Selection();
int data[] = {66, 10, 1, 99, 5};
selection.sort(data);
for(int i =0; i<data.length; i++) {
System.out.println("data["+i+"] : "+data[i]);
}
}
}
참고사이트
https://gmlwjd9405.github.io/2018/05/06/algorithm-selection-sort.html
반응형