선택 정렬(Selection Sort)는 배열의 원소 중에서 원하는 위치에 놓을 데이터를 찾아 선택하는 것
어떤 배열을 오름차순으로 정렬하고 싶다고 가정하고 설명하도록 한다.
int[] array = {5, 9, 1, 7, 2}; 인 배열 array가 있다고 하자.
정렬을 할 때마다 배열의 맨 앞부터의 위치들에 최솟값들이 하나씩 이동하게 되므로
이미 최솟값을 이동시킨 위치는 고려하지 않고, 그 다음 위치들 중에서 최솟값을 찾는다.
즉, 전체적인 과정을 설명하면,
1. 배열의 각 원소 중에서 최솟값을 찾고, 이를 array[0]과 자리를 바꾼다. (swap)
2. array[0]을 제외한 나머지 원소들 중에서 최솟값을 찾아 array[1]과 자리를 바꾼다.
3. array[2], array[3]....도 위의 방법대로 반복한다.
이때, (배열의 길이 - 1)만큼만 최솟값을 찾는 cycle을 진행하면 되는데,
위의 예시에서 총 5개의 데이터 중에서 4개의 데이터를 정렬했다는 것은 이미 마지막 데이터는 정렬이 되었다는 의미이기 때문이다. (최솟값을 찾고 나머지 값들과 비교하여 정렬했으므로 2개씩 비교가 되었기 때문)
이를 코드를 작성하여 비교해보자.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
import java.util.Arrays;
public class Selection_Sort {
public static void main(String[] args) {
// 선택정렬을 통해 오름차순으로 정렬
int[] array = { 5, 9, 1, 7, 2 };
// 최솟값을 갖는 index를 찾아 그 index 자리의 값과 array[i]값을 바꿔준다.
for (int i = 0; i < array.length - 1; i++) {
int minIdx = i;
for (int j = i + 1; j < array.length; j++) {
if (array[minIdx] > array[j]) {
minIdx = j;
}
}
int tmp = array[i];
array[i] = array[minIdx];
array[minIdx] = tmp;
}
System.out.println(Arrays.toString(array));
}
}
|
cs |
내림차순도 같은 논의로 진행해보면, (부등호의 방향만 반대)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
import java.util.Arrays;
public class Selection_Sort {
public static void main(String[] args) {
// 선택정렬을 통해 내림차순으로 정렬
int[] array = { 5, 9, 1, 7, 2 };
// 최댓값을 갖는 index를 찾아 그 index 자리의 값과 array[i]값을 바꿔준다.
for (int i = 0; i < array.length - 1; i++) {
int maxIdx = i;
for (int j = i + 1; j < array.length; j++) {
if (array[maxIdx] < array[j]) {
maxIdx = j;
}
}
int tmp = array[i];
array[i] = array[maxIdx];
array[maxIdx] = tmp;
}
System.out.println(Arrays.toString(array));
}
}
|
cs |
그 결과, {9, 7, 5, 2, 1}로 내림차순 정렬이 됨을 확인할 수 있다.
'알고리즘 및 코테' 카테고리의 다른 글
| 배열에 정수를 입력할 때마다 정렬하여 출력하기 (0) | 2023.01.27 |
|---|---|
| 이진(이분) 탐색 - Binary Search - Java (0) | 2023.01.10 |
| 정렬 - Bubble Sort (0) | 2023.01.09 |
