1. 선택 정렬
1-1. 선택 정렬이란?
1-2. 움짤로 보는 예시
1-3. 글로 보는 예시
1-4. 소스코드
1-5. 선택 정렬의 시간 복잡도
1. 선택 정렬
1-1. 선택 정렬이란?
정렬 방법 중 가장 느린 것은 버블 정렬.
그리고 그다음으로 느린 방법이 바로 선택 정렬이다.
버블 정렬과 마찬가지로 구현이 단순하며 메모리 공간을 추가로 필요로 하지 않는다.
버블 정렬은 자리 바꿈(swap)이 자주 일어나지만 선택 정렬은 평균적으로 그 횟수가 더 적기 때문에
버블 정렬보다 선택 정렬이 항상 더 나은 효율을 보여준다.
움짤을 통해 어떻게 하는 정렬 방법인지 알아보도록 하자.
1-2. 움짤로 보는 예시
숫자들 중 가장 작은 값을 선택해서 맨 왼쪽에 있는 값과 교환하는 것이 기본적인 개념이다.
가장 작은 값을 왼쪽에 둠으로써 그 숫자는 정렬이 완료된 것이다. (위 움짤에서는 회색으로 변함)
1-3. 글로 보는 예시
- 첫 번째 바퀴
5, 7, 8, 2, 4 중 가장 작은 값을 선택해서 0번째 인덱스의 값과 자리를 바꾼다.
짠! 이제 0번째 인덱스는 정렬이 완료되었으므로 검사할 필요가 없다.
- 두 번째 바퀴
이번엔 7, 8, 5, 4 중에 가장 작은 값을 찾아 1번째 인덱스의 값과 자리를 바꾼다.
7과 4의 자리를 바꾸었다.
- 세 번째 바퀴
이번엔 8, 5, 7 중에 가장 작은 값을 찾아 2번째 인덱스의 값과 자리를 바꾼다.
8과 5의 자리를 바꾸었다.
- 네 번째 바퀴
이번엔 8, 7 중에 가장 작은 값을 찾아 3번째 인덱스의 값과 자리를 바꾼다.
8과 7의 자리를 바꾸었다.
마지막 값은 더 이상 검사할 필요가 없으므로 이것으로 정렬이 완료되었다.
1-4. 소스 코드
public static void selectionSort(int[] arr) {
for(int i=0; i<arr.length-1; i++) {
// 가장 작은 값의 인덱스, 처음에는 맨 앞의 인덱스(i)를 넣어준다.
int indexMin = i;
// 값을 비교해가며 가장 작은 값의 인덱스를 찾는다.
for(int j=i+1; j<arr.length; j++) {
if(arr[j] < arr[indexMin]) {
indexMin = j;
}
}
// 자리 바꿈
int temp = arr[i];
arr[i] = arr[indexMin];
arr[indexMin] = temp;
}
}앞서 [목차 1-3]에서 가장 작은 값을 찾는 과정을 생략하고 설명하였는데
실제로는 일일이 값을 2개씩 비교해가며 찾아야 한다.
1-5. 선택 정렬의 시간 복잡도
주어진 숫자가 총 n개 일때 선택 정렬은 n-1, n-2, ... 1번 비교 연산을 하게 되며 이걸 식으로 바꾸면 n(n-1)/2번이 된다.
즉 O(n²)의 시간 복잡도를 가진다.
저번 포스팅에서 가장 느린 정렬 방법인 버블 정렬도 O(n²)의 시간 복잡도를 가진다고 했었는데
시간 복잡도가 비슷하니 둘의 실행 속도는 비슷할까?
[목차 1-1]에서 말했듯이 선택 정렬이 조금 더 효율이 좋으니 조금 빠를까?
이를 알아보기 위하여 난수 데이터 100,000개를 정렬하는데 걸리는 시간을 측정해보았다.
세... 세상에... 😲
생각보다 차이가 많이 나서 한 번 놀랐고
버블 정렬이 이렇게 쓰레기였다는 거에 두 번 놀랐다.
물론 이 실험 한 번으로 둘의 차이를 단정지을순 없겠지만
확실한 건 버블 정렬보다 선택 정렬이 빠르다는 것이다.
import java.util.*;
public class Sort {
public static final int DATASIZE = 100000;
public static void main(String[] args) {
int[] arr = makeRandomNumbers();
int[] copiedArr;
long startTime = System.currentTimeMillis();
copiedArr = arr.clone();
bubbleSort(copiedArr);
long endTime = System.currentTimeMillis();
System.out.println("버블 정렬: " + (endTime - startTime) / 1000.0 + "초");
startTime = System.currentTimeMillis();
copiedArr = arr.clone();
selectionSort(copiedArr);
endTime = System.currentTimeMillis();
System.out.println("선택 정렬: " + (endTime - startTime) / 1000.0 + "초");
}
public static int[] makeRandomNumbers() {
Random random = new Random();
HashSet<Integer> hs = new HashSet<>();
int[] arr = new int[DATASIZE];
for(int i=0; i<DATASIZE; i++) {
int number = random.nextInt(DATASIZE);
if(hs.contains(number)) {
i--;
continue;
} else {
hs.add(number);
arr[i] = number;
}
}
System.out.println("[데이터 개수: " + DATASIZE + "]\n");
return arr;
}
public static void bubbleSort(int[] arr) {
for(int i=0; i<arr.length-1; i++) {
for(int j=1; j<arr.length-i; j++) {
if(arr[j-1] > arr[j]) {
int temp = arr[j-1];
arr[j-1]= arr[j];
arr[j] = temp;
}
}
}
}
public static void selectionSort(int[] arr) {
for(int i=0; i<arr.length-1; i++) {
int indexMin = i;
for(int j=i+1; j<arr.length; j++) {
if(arr[j] < arr[indexMin]) {
indexMin = j;
}
}
int temp = arr[i];
arr[i] = arr[indexMin];
arr[indexMin] = temp;
}
}
}직접 실험을 해보고 싶다면 위의 소스를 실행해보면 된다.
💡 느낀 점
- 어제에 이어 버블 정렬은 써먹을 게 못된다는 걸 또또 다시 느낌..
📘 참고한 자료
댓글