선택 정렬

Jan 28, 2024

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]]; 라는 괴랄한 코드가 되잖아.. 
생각을 좀 하고 코딩하자^^

See more posts

선택 정렬

1. 선택정렬이란?

2. 선택정렬

3. 선택정렬 코드

More articles

객체 (Object)

객체 지향 프로그램이란?

버블 정렬

스왑코드 (손!)