Contents
선택 정렬은 알고리즘에 속한다!
알고리즘이란?
컴퓨터가 따라 할 수 있도록 문제를 해결하는 절차나 방법을 자세히 설명하는 과정 따라서
함수를 절차적으로 만들면 ‘알고리즘’이다.
선택 정렬
- 가장 작은 데이터를 찾아서 그 데이터를 리스트의 가장 앞에 위치한 데이터와 교환하는 방식을 반복하여 정렬하는 알고리즘이다.
- 정렬되지 않은 데이터 중 최솟값을 찾아 정렬된 부분의 가장 앞에 위치 시키고, 그 다음으로 작은 값을 찾아 두 번째로 앞에 위치 시키는 과정을 반복하여 전체 데이터를 정렬한다.
- 데이터의 개수가 적을 때 유리하며, 반복문을 통해 최솟값을 찾고 이동하는 과정을 수행하므로 시간 복잡도는 항상 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
