1. 선택정렬이란?
배열을 돌면서 가장 작은 값부터 하나씩 앞으로 옮기는 것. 그러기 위해선 우선 가장 작은 값을 찾는다.
2. 선택정렬
n = [ 3, 5, 4, 2, 1 ]
- 배열을 돌면서 찾아낸 가장 작은 값을 저장할 변수를 선언
- 현재로썬 가장 작은 값이 뭔지 모르니 시작 값(0번 인덱스)을 시작 값으로 초기화
[ min = 3; ]
- 이제 배열 방을 n번 돌면서 가장 작은 값을 찾는다.
3과 5를 비교 - 변화 없음
3과 4를 비교 - 변화 없음
3과 2를 비교 - 변화 있음! > 작은 값을 2로 조정 [ min = 2; ]
2와 1을 비교 - 변화 있음! > 작은 값을 [ min = 1; ]로 다시 조정
- 처음부터 배열의 끝까지 검색을 해봤으니, 1이 제일 작은 숫자란 걸 알 수 있다.
1을 가장 왼쪽 자리에 있는 데이터와 스왑한다. [ 1, 5, 4, 2, 3 ] 첫번째 값은 정렬 완료!
- 다시 여정을 떠난다… 작은 값을 시작값 (5)로 초기화 [ min = 5; ]
5와 4를 비교 - 변화 있음! > [ min = 4; ]
4와 2를 비교 - 변화 있음! > [ min = 2; ]
2와 3을 비교 - 변화 없음!
2를 첫번째 데이터와 교체한다. [ 1, 2, 4, 5, 3 ] (5는 제일 뒤로 가는게 아닌, 원래 2가 있던 자리에 위치함)
- 다시 간다… 시작 값을 작은 값으로 초기화 [ min = 4; ]
4와 5를 비교 - 변화 없음
4와 3을 비교 - 변화 있음! > [ min = 3; ]
3을 첫번째 데이터와 교체한다. [ 1, 2, 3, 5, 4 ] - 원래 3이 있던 자리에 위치
- 다시 간다… 시작 값을 작은 값으로 초기화 [ min = 5; ]
5와 4를 비교 - 변화 있음! > [ min = 4; ]
4를 첫번째 데이터와 교체한다. [ 1, 2, 3, 4, 5 ] 정렬 완료!
선택 정렬은 앞에서부터 한 칸씩 가면서, 갈 때마다 전체 배열 방을 한번씩 다시 돌기때문에 n의 제곱만큼 시간이 든다.
한 번 돌 때마다, 제일 작은 숫자가 왼쪽 자리에 위치
* 버블 정렬은 한 번 돌 때마다 제일 큰 숫자가 오른쪽 자리에 위치
회전수 : N - 1
1회전 비교 횟수 : N - 1
2회전 비교 횟수 : N - 2
3회전 비교 횟수 : N - 3
4회전 비교 횟수 : N - 4
* 비교할 데이터가 5개 있으면 4개만 비교
for (i = 0; i < n-1; i++) { min = i
3. 선택정렬 코드
(완성) 코드 보기
package test; public class Test01 { public static void main(String[] args) { int[] arr = {3, 5, 1, 10, 8}; int min, temp; int n = arr.length; for (int i = 0; i < n - 1; i++) { min = i; //i번 인덱스에 있는 값을 모두 한번씩 최소값으로 설정 //현재 루프 시작점을 알려줌 for (int j = i + 1; j < n; j++) { //i번 인덱스 이후를 기준으로 나머지 값을 비교 해야하니까! if (arr[j] < arr[min]) //실질적으로 가장 작은값을 찾는 역할. j++이 있으니까 i+1, i+2, i+3하면서 j < n까지 진행 min = j; } } temp = arr[min]; arr[min] = arr[i]; arr[i] = temp; } for (int v : arr) { System.out.print(v + " "); } } }
for (int j = i + 1; j < n; j++) {
최소값으로 잡힌건 현재 0번 인덱스니, 비교하는 값은 1번 인덱스여야 해서 i+1
또한, 비교하는건 항상 최소값으로 맨 앞자리에 후송된 값의 다음 번지에 존재하는 애와 비교해야 하기 때문. 모든 값들이랑 다 비교해야 하기 때문에 총 n번 돌아야 한다.
if (arr[j] < arr[min])
현재 최소값으로 설정되어 있는 것(arr[min]) 보다 비교하려는 값(arr[j])가 작을 경우에, 최소값을 i(min)에서 j로 스왑
선택 정렬의 핵심은 내부 루프에서 진정한 최소값을 찾고, 외부 루프에서 해당 최소값과 현재 위치의 원소를 교환하는 것
외부 루프 > n - 1
내부 루프 > i + 1
* 외부 루프가 한 번 돌 때마다 가장 작은 숫자가 왼쪽에 위치하게 된다.
1회전 코드
1회전 코드 간략화 과정 1
package ex03.test; 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 final int rep = 0; int min = rep; if(arr[0] > arr[1]) { // 5, 8, 2, 4, 3 min = 1; } if(arr[0] > arr[2]) { // 5, 8, 2, 4, 3 -> min = 2 min = 2; } if(arr[2] > arr[3]) { // 5, 8, 2, 4, 3 -> min = 2 min = 3; } if(arr[2] > arr[4]) { // 5, 8, 2, 4, 3 -> min = 2 min = 4; } if(rep != min) { int temp = arr[rep]; arr[rep] = arr[min]; arr[min] = temp; } } }
1회전 코드 간략화 과정 2
package ex03.test; 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 final int rep = 0; int i = rep; int min = rep; //min이 변경되니까 i = i+1; //1 if(arr[min] > arr[i]) { // 5, 8, 2, 4, 3 min = i; } i = i+1; //2 if(arr[min] > arr[i]) { // 5, 8, 2, 4, 3 -> min = 2 min = i; //2 } i = i+1; //3 if(arr[min] > arr[i]) { // 5, 8, 2, 4, 3 -> min = 2 min = i; } i = i+1; //4 if(arr[min] > arr[i]) { // 5, 8, 2, 4, 3 -> min = 2 min = i; } if(rep != min) { int temp = arr[rep]; arr[rep] = arr[min]; arr[min] = temp; } } }
1회전 코드 간략화 과정 3
package ex03.test; 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 final int rep = 0; int i = rep; int min = rep; //min이 변경되니까 for (int j = 0; j < 4; j++) { i = i+1; //1 if(arr[min] > arr[i]) { // 5, 8, 2, 4, 3 min = i; } } if(rep != min) { int temp = arr[rep]; arr[rep] = arr[min]; arr[min] = temp; } } }
1회전 코드 간략화 과정 4 = 완성
package ex03.test; 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 final int rep = 0; int min = rep; //min이 변경되니까 for (int i = rep+1; i < 5; i++) { if(arr[min] > arr[i]) { // 5, 8, 2, 4, 3 min = i; } } if(rep != min) { int temp = arr[rep]; arr[rep] = arr[min]; arr[min] = temp; } } }
package ex03.test; 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 final int rep = 0; int min = rep; //min이 변경되니까 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]; arr[rep] = arr[min]; arr[min] = temp; } } }
회전 코드
package ex03.test; 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]) { // 5, 8, 2, 4, 3 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]) { // 2, 8, 5, 4, 3 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]) { // 2, 8, 5, 4, 3 min = i; } } if(rep != min) { int temp = arr[rep]; arr[rep] = arr[min]; arr[min] = temp; } } }
회전 코드 간략화
package ex03.test; 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; for (int j = 0; j < N-1; j++) { rep = j; min = rep; 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]; arr[rep] = arr[min]; arr[min] = temp; } } for(int v : arr){ //전체를 순회해서 출력 (for each문). arr이 한바퀴 돌때마다 v에 저장됨 그래서 v를 출력하면 됨. System.out.print(v + " "); } } }
for each문
전체를 순회해서 출력할 때 사용.
ex) arr이 한바퀴 돌때마다 v에 저장됨. 그래서 v를 출력하면 됨.
내가 한 거
<잘못된 코드>
package ex04; public class Select02 { public static void main(String[] args) { int[] arr1 = {5, 8, 2, 10, 3, 6, 80, 0, 12, 100, 77, 32, 11}; final int N = arr1.length; int min, temp; for (int j = 0; j < N - 1; j++) { min = j; for (int i = 0; i < N; i++) { if (arr1[min] > arr1[i + 1]) { min = arr1[i + 1]; } } temp = arr1[min]; arr1[min] = arr1[j]; arr1[j] = temp; } } }
<오류 1> if (arr1[min] > arr1[i + 1]) { min = arr1[i + 1]; 라고 해버리면, 배열값이 arr1[10]이 되어버리는 사태가.. 배열 범위를 넘어가버림! <오류 2> for (int i = j + 1; i < N; i++) >> 이미 첫번째 값은 최솟값으로 설정이 되어있으니 내부 루프에선 서치할 필요가 없고, 그 다음에 있는 애부터 (j+1) ~ 끝까지 서치를 시작하는 것. 그래서 j+1을 해줘야함
>> 그러니까 이 말은, 선택 정렬이 {5, 8, 2, 10, 3} 라고 있을때, 최솟값 2를 찾으면, 그 2를 들고 10이랑, 3을 비교를 해야하잖아? 애는 그걸 해. n회전을 돌면서 이미 정렬된 앞자리 최솟값들은 제외한 상태로 돈다고.
근데 int i = 1; 이라고 하면, 최솟값 2를 찾았어! 첫 1회전은 정상이야! 근데 2회전부터 다시.. 처음 숫자 5부터 비교를 시작해… 이후랑 비교를 해야하는데…
<오류 3> min = arr1[i + 1]; > x min = i; > o 다음 코드를 보면 arr1[min];이라고 되어있는데 이렇게 넣어버리면... arr1[arr1[i+1]]; 라는 괴랄한 코드가 되잖아.. 생각을 좀 하고 코딩하자^^
Share article