선택 정렬은 알고리즘에 속한다!
알고리즘이란?
컴퓨터가 따라 할 수 있도록 문제를 해결하는 절차나 방법을 자세히 설명하는 과정 따라서
함수를 절차적으로 만들면 ‘알고리즘’이다.
선택 정렬
- 가장 작은 데이터를 찾아서 그 데이터를 리스트의 가장 앞에 위치한 데이터와 교환하는 방식을 반복하여 정렬하는 알고리즘이다.
- 정렬되지 않은 데이터 중 최솟값을 찾아 정렬된 부분의 가장 앞에 위치 시키고, 그 다음으로 작은 값을 찾아 두 번째로 앞에 위치 시키는 과정을 반복하여 전체 데이터를 정렬한다.
- 데이터의 개수가 적을 때 유리하며, 반복문을 통해 최솟값을 찾고 이동하는 과정을 수행하므로 시간 복잡도는 항상 O(n^2)이다.
선택 정렬의 흐름 보기
5, 8, 2, 4, 3 수를 선택 정렬 하면?
선택 정렬의 회전 수는 N회 돈다! 이때 N은 배열의 크기이다.
처음 자기 자신의 위치도 확인하기 때문에 총 N회 이다.
아래의 표는 i = 0 (해당 위치 변경), p = 0 (교환 인덱스)로 계산한다.
ㅤ | 1 회전 (i = 0 , p = 0) | 2 회전 (i = 1, p = 1) | 3 회전 (i = 2, p = 2) | 4 회전 (i = 3, p = 3) |
1 | 5, 8 (0, 1) 비교 | 8, 5 (1, 2) 비교 p = 2 | 5, 4 (2, 3) 비교 p = 3 | 5, 8 (3, 4) 비교 |
2 | 5, 2 (0, 2) 비교 p = 2 | 5, 4 (2, 3) 비교 p = 3 | 4, 8 (3, 4) 비교 | ㅤ |
3 | 2, 4 (2, 3) 비교 | 4, 3 (3, 4) 비교 p = 4 | ㅤ | ㅤ |
4 | 2, 3 (2, 4) 비교 | ㅤ | ㅤ | ㅤ |
결과 (i와 p 교환) | f(i != p) 2, 8, 5, 4, 3 | if(i != p) 2, 3, 5, 4, 8 | if(i != p) 2, 3, 4, 5, 8 | if(i != p) 2, 3, 4, 5, 8 |
선택 정렬 알고리즘 이해를 위한 1 회전 만들기 코드
진행도 1
package ex03;
public class SelectedEx01 {
public static void main(String[] args) {
int[] arr = {5, 8, 2, 4, 3};
final int N = arr.length;
// 변경해야될 위치 5 replace -> rep
// 변경해야될 위치 8 min -> min
final int rep = 0; // 0
int i = rep; // 0
int min = rep; // 0
i++; // 1
if (arr[min] > arr[i]) { // 5, 8, 2, 4, 3
min = i;
}
i++; // 2
if (arr[min] > arr[i]) { // 5, 8, 2, 4, 3 -> min = 2
min = i; // 2
}
i++; // 3
if (arr[min] > arr[i]) { // 5, 8, 2, 4, 3 -> min = 2
min = i;
}
i++; // 4
if (arr[min] > arr[i]) { // 5, 8, 2, 4, 3 -> min = 2
min = i;
}
if (rep != min) {
int temp = arr[rep]; // temp = 5
arr[rep] = arr[min];
arr[min] = temp;
}
}
}진행도 2
package ex03;
public class SelectedEx01 {
public static void main(String[] args) {
int[] arr = {5, 8, 2, 4, 3};
final int N = arr.length;
// 변경해야될 위치 5 replace -> rep
// 변경해야될 위치 8 min -> min
final int rep = 0; // 0
int i = rep; // 0
int min = rep; // 0
for (int j = 0; j < 4; j++) {
i++; // 1
if (arr[min] > arr[i]) { // 5, 8, 2, 4, 3
min = i;
}
}
if (rep != min) {
int temp = arr[rep]; // temp = 5
arr[rep] = arr[min];
arr[min] = temp;
}
}
}진행도 3
package ex03;
public class SelectedEx01 {
public static void main(String[] args) {
int[] arr = {5, 8, 2, 4, 3};
final int N = arr.length;
// 변경해야될 위치 5 replace -> rep
// 변경해야될 위치 8 min -> min
final int rep = 0; // 0
int min = rep; // 0
for (int i = rep + 1; i < N; i++) {
if (arr[min] > arr[i]) { // 5, 8, 2, 4, 3
min = i;
}
}
if (rep != min) {
int temp = arr[rep]; // temp = 5
arr[rep] = arr[min];
arr[min] = temp;
}
for (int i = 0; i < N; i++) {
System.out.print(arr[i] + " ");
}
}
}1 회전 만들기를 완성하여 반복하게 되면 원하는 모습의 선택 정렬이 완성 된다!
선택 정렬 합치기
진행도 1
package ex03;
public class SelectedEx01 {
public static void main(String[] args) {
int[] arr = {5, 8, 2, 4, 3};
final int N = arr.length;
int rep;
int min;
// 1회전
rep = 0;
min = rep;
for (int i = rep + 1; i < N; i++) {
if (arr[min] > arr[i]) {
min = i;
}
}
if (rep != min) {
int temp = arr[rep];
arr[rep] = arr[min];
arr[min] = temp;
}
// 2회전
rep = 1;
min = rep;
for (int i = rep + 1; i < N; i++) {
if (arr[min] > arr[i]) {
min = i;
}
}
if (rep != min) {
int temp = arr[rep];
arr[rep] = arr[min];
arr[min] = temp;
}
// 3회전
rep = 2;
min = rep;
for (int i = rep + 1; i < N; i++) {
if (arr[min] > arr[i]) {
min = i;
}
}
if (rep != min) {
int temp = arr[rep];
arr[rep] = arr[min];
arr[min] = temp;
}
}
}진행도 2
package ex03;
public class SelectedEx01 {
public static void main(String[] args) {
int[] arr = {5, 8, 2, 4, 3};
final int N = arr.length;
int min;
int rep;
for (int i = 0; i < N - 1; i++) {
rep = i;
min = rep;
for (int j = rep + 1; j < N; j++) {
if (arr[min] > arr[j]) {
min = j;
}
}
if (rep != min) {
int temp = arr[rep];
arr[rep] = arr[min];
arr[min] = temp;
}
}
for (int v : arr) {
System.out.print(v + " ");
}
}
}선택 정렬 예제
package ex03;
public class SelectedEx01 {
public static void main(String[] args) {
int[] arr = {5, 8, 2, 4, 3};
final int N = arr.length;
int min;
int rep;
for (int i = 0; i < N - 1; i++) {
rep = i;
min = rep;
for (int j = rep + 1; j < N; j++) {
if (arr[min] > arr[j]) {
min = j;
}
}
if (rep != min) {
int temp = arr[rep];
arr[rep] = arr[min];
arr[min] = temp;
}
}
for (int v : arr) {
System.out.print(v + " ");
}
}
}출력 결과
Share article