[자바 기초] 선택정렬

2023.05.06.토

선택정렬(selection sort)

선택 정렬이란 정렬 방식 중의 하나로 '최솟값' 혹은 '최대값'을 선택하여 정렬하는 방식이다.

임시변수 tmp만 추가적으로 사용하나 전체적으로 매우 적은 용량이기 때문에 "제자리 정렬"이라고도 불린다.

 

 

오름차순으로 선택정렬을 한다고 쳤을때

1. 모든 인덱스 중에 최소값을 찾는다.

2. 맨앞 인덱스와 교환한다.

3. 맨 앞 인덱스를 제외한 나머지 인덱스 중에 최소값을 찾는다.

4. 맨 앞에서 두번째 인덱스와 교환한다.

5. 위의 과정을 정렬이 완성될 때까지 (배열의 길이 -1 만큼)반복 한다.

 

 

장점

자료 이동의 횟수가 정해져 있다.

추가적인 메모리 소비가 작다.
구현이 매우 쉽다.

 

단점

 다른 정렬 알고리즘에 비해 교환 과정이 많아 많은 시간을 소비한다.

안정성을 만족하지 않는다.

(중복인 여러 값들이 있을때 해당 값들의 인덱스가 고정되지 않는다)

 

 

 

선택 정렬을 활용하여 문제를 풀이해보자

자료 이동의 횟수가 정해져 있기 때문에 for문을 사용하며 교환 알고리즘을 사용한다

 

 

문제1)

다음 숫자들을
선택정렬을 이용하여 오름차순으로 출력하여라
5 4 2 1 3

Console
정렬 전: 5 4 2 1 3
정렬 후: 1 2 3 4 5

 

public class Test01 {
    public static void main(String[] args) {
    	
    	//int 배열에 정렬할 숫자 대입
        int[] arr = {5, 4, 2, 1, 3};
        
        //정렬전 배열 출력
        System.out.print("정렬 전: ");
        for(int i =0; i<arr.length;i++){
            System.out.print(arr[i]+" ");
        }
        System.out.println();

        //정렬을 시행할 횟수 == int 배열의 길이
        for(int i=0; i<arr.length; i++){
        	//i만큼은 이미 정렬되어 있기 때문에 i+1부터 시작
            for(int j =i+1; j<arr.length; j++) {
            	
            	//최소값을 찾아 교환
                if(arr[i] > arr[j]){
                    int temp = arr[i];
                    arr[i]= arr[j];
                    arr[j]=temp;
                }
            }
        }
        //정렬된 배열 출력
        System.out.print("정렬 후: ");
        for(int i =0; i<arr.length;i++) {
            System.out.print(arr[i]+" ");
        }
    }
}

 

문제2)

랜덤으로 5개 숫자 오름차순으로 출력하여라
단, 숫자 범위(1~5)이다

Console
정렬 전:
정렬 후:

public class Test {
	public static void main(String[] args) {
		//int 배열에 정렬할 숫자 대입

		int[] arr=new int[5];	//배열의 크기를 안다
		for(int i =0; i<arr.length; i++) {
			Random rand=new Random();
			arr[i]=rand.nextInt(3)+3;	//1~5
		}
        
        //정렬전 배열 출력
        System.out.print("정렬 전: ");
        for(int i =0; i<arr.length;i++) {
            System.out.print(arr[i]+" ");
        }
        System.out.println();

        //정렬을 시행할 횟수 == int 배열의 길이
        for(int i=0; i<arr.length; i++){
        	//i만큼은 이미 정렬되어 있기 때문에 i+1부터 시작
            for(int j =i+1; j<arr.length; j++) {
            	
            	//최소값을 찾아 교환
                if(arr[i] > arr[j]){
                    int temp = arr[i];
                    arr[i]= arr[j];
                    arr[j]=temp;
                }
            }
        }
        //정렬된 배열 출력
        System.out.print("정렬 후: ");
        for(int i =0; i<arr.length;i++) {
            System.out.print(arr[i]+" ");
        }
    }

}

문제3)

랜덤으로 n(1~10)개 숫자를 선택정렬을 통해 내림차순으로 출력
단, 숫자 범위(1~5)이다.

Console

정렬된 숫자의 수: 
정렬 전:
정렬 후:

public class Test3 {

	public static void main(String[] args) {
		
		//int 배열에 정렬할 숫자 대입
		Random randNum = new Random();
		int n = randNum.nextInt(10)+1;	//1~10 사이의 숫자
		
		System.out.println("정렬될 숫자의 갯수: "+n);

		//배열의 크기==n
		int[] arr=new int[n];
		for(int i =0; i<arr.length; i++) {
			Random rand=new Random();
			arr[i]=rand.nextInt(3)+3;
		}
        
        //정렬전 배열 출력
        System.out.print("정렬 전: ");
        for(int i =0; i<arr.length;i++) {
            System.out.print(arr[i]+" ");
        }
        System.out.println();

        //정렬을 시행할 횟수 == int 배열의 길이
        for(int i=0; i<arr.length; i++){
        	//i만큼은 이미 정렬되어 있기 때문에 i+1부터 시작
            for(int j =i+1; j<arr.length; j++) {
            	
            	//최소값을 찾아 교환
                if(arr[i] > arr[j]){
                    int temp = arr[i];
                    arr[i]= arr[j];
                    arr[j]=temp;
                }
            }
        }
        //정렬된 배열 출력
        System.out.print("정렬 후: ");
        for(int i =0; i<arr.length;i++) {
            System.out.print(arr[i]+" ");
        }

	}

}

 

문제4)

랜덤으로 n(1~10)개 숫자를 선택정렬을 통해 내림차순으로 출력
단, 숫자 범위(1~5)이다며 중복이 없어야 한다

Console

정렬된 숫자의 수: 
정렬 전:
정렬 후:

public class Test04 {

	public static void main(String[] args) {

		// int 배열에 정렬할 숫자 수
		Random randNum = new Random();
		int n = randNum.nextInt(10) + 1; // 1~10 사이의 숫자

		System.out.println("정렬될 숫자의 갯수: " + n);

		// 배열의 크기==n
		int[] arr = new int[n];
		Random rand = new Random();

		int index = 0; // 배열 내에서 현재위치
		while (true) {

			// 배열이 완성될시 무한루프문을 종료한다
			if (index == arr.length) {
				break;
			}

			arr[index] = rand.nextInt(10) + 1; // 1~10
			boolean flag = false;

			//중복 검사 후 중복이면 flag==true
			for (int k = 0; k < index; k++) {	// 비교해야 할 횟수가 정해져 있으므로 for
				if (arr[index] == arr[k]) {		// 특별한 일 : 중복발생
					flag = true;
				}
			}

			//중복이면 index++ 하지 못하고 continue를 통해 다시 한다
			if (flag == true) {
				continue;
			}

			index++;
		}

		// 정렬전 배열 출력
		System.out.print("정렬 전: ");
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
		System.out.println();

		// 정렬을 시행할 횟수 == int 배열의 길이
		for (int i = 0; i < arr.length; i++) {
			// i만큼은 이미 정렬되어 있기 때문에 i+1부터 시작
			for (int j = i + 1; j < arr.length; j++) {

				// 최소값을 찾아 교환
				if (arr[i] > arr[j]) {
					int temp = arr[i];
					arr[i] = arr[j];
					arr[j] = temp;
				}
			}
		}
		
		// 정렬된 배열 출력
		System.out.print("정렬 후: ");
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}

	}

}

 

문제5)

4팀에는 6명의 학생이 있다.

해당 학생들의 점수를 입력받아 선택 정렬로 내림차순 정렬하라

Console

1등: 

2등:

3등:

4등:

5등:

6등:

import java.util.Scanner;

public class Test05 {

	public static void main(String[] args) {

		int[] score = new int[6];
		Scanner sc=new Scanner(System.in);
		
		//6명 입력받기
		for(int i=0; i<score.length; i++) {
			System.out.print((i+1)+"번째 학생의 점수를 입력해주세요: ");
			score[i] =sc.nextInt();	
		}
		
		
		
		//정렬
		for(int i=0; i<score.length; i++) {
			//이미 정렬된 인덱스의 다음부터 비교시작
			for(int k=i+1; k<score.length; k++) {
				//교환 알고리즘
				if(score[k]>score[i]) {
					int tmp = score[k];
					score[k] = score[i];
					score[i] = tmp;
				}
			}
		}
		
		//출력
		for(int i=0; i<score.length; i++) {
			System.out.println((i+1)+"등: "+score[i]);
		}
	}

}