선택 정렬

[Java] 선택 정렬 알고리즘 작성

Dec 18, 2023

Contents

선택 정렬(selected sort)

목표 : 어떠한 값을 선택한 후 그 값을 제외한 나머지 값과 비교 후 가장 작은 값을 맨 앞에 정렬

⚡

원본 데이터 (5, 8, 2, 4, 3) N

알고리즘 작성해보기

1회전(4바퀴)

교환 인덱스 p = 0, final i = 0 (해당 위치 변경)

(1) 5, 8 비교 (0, 1) —> (p, for문 증가값)

(2) 5, 2 비교 (0, 2) p = 2

(3) 2, 4 비교 (2, 3)

(4) 2, 3 비교 (2, 4)

if (i≠p) 5와 2비교 후 교환 (i, p 교환) (2, 8, 5, 4, 3)

1회전을 수행하면 정렬이 완료되지는 않았지만 제일 작은 수가 맨 첫 자리로 감

2회전(3바퀴)

교환 인덱스 p = 1, final i = 1 (해당 위치 변경)

(1) 8, 5 비교 (1, 2) p = 2

(2) 5, 4 비교 (2, 3) p = 3

(3) 4, 3 비교 (3, 4) p = 4

if(i≠p) 8과 3 비교 후 교환 (2, 3, 5, 4, 8)

3회전(2바퀴)

교환 인덱스 p = 2, final i = 2 (해당 위치 변경)

(1) 5, 4 비교 (2, 3) p = 3

(2) 4, 8 비교 (3, 4)

if(i≠p) 5와 4 비교 후 교환 (2, 3, 4, 5, 8)

4회전(1바퀴)

교환 인덱스 p = 3, final i = 3 (해당 위치 변경)

(1) 5, 8 비교 (3, 4)

if(i≠p) 5와 8 비교 후 arr[p] = arr[i] 이므로 교환 x

회전수 : N-1 n회전 비교 횟수 : N-n

자리 바꾸는 스왑 코드도 버블 정렬에서 했으므로 참고

최솟값 찾는 코드 작성 해보기


int min = arr[0];
for(i = 0; i< N; i++){
		if(arr[i] < min){
				min = arr[i];
		}
}

1회전 코드 작성 해보기


package ex03.test;
// 1회전
public class SelectedTest03 {
    public static void main(String[] args) {
        int[] arr = {5,8,2,4,3};
        final int N = arr.length;
        int temp;
        final int rep = 0;
        int min = rep;

        for (int i = rep+1; i < N; i++) {
            if (arr[min] > arr[i]) {
                min = i;
            }
        }
        if (rep != min) {
            temp = arr[min];
            arr[min] = arr[rep];
            arr[rep] = temp;
        }
        }
    }
}

여러번 코드 작성


package ex03.test;

import java.util.Arrays;

public class SelectedTest04 {
    public static void main(String[] args) {
        int[] arr = {5,8,2,4,3};
        final int N = arr.length;
        int temp;

        for (int rep = 0; rep < N-1 ; rep++) {
            int min = rep;
            for (int i = rep + 1; i < N; i++) {
                if (arr[min] > arr[i]) {
                    min = i;
                }
            }
            if (rep != min) {
                temp = arr[min];
                arr[min] = arr[rep];
                arr[rep] = temp;
            }
        }
        for(int v : arr){
            System.out.print(v+" ");
        } // for each 문
    }
}