[PS] 인프런 강의 - Sorting and Searching 1. 선택 정렬

문제

N개의 숫자가 입력되면 오름차순으로 정렬하여 출력하는 프로그램을 작성하세요.
정렬하는 방법은 선택정렬입니다.

 

▣ 입력설명
첫 번째 줄에 자연수 N(1<=N<=100)이 주어집니다.
두 번째 줄에 N개의 자연수가 공백을 사이에 두고 입력됩니다. 각 자연수는 정수형 범위 안에 있습니다.

 

▣ 출력설명
오름차순으로 정렬된 수열을 출력합니다.

 

▣ 입력예제 1
6
13 5 11 7 23 15

 

▣ 출력예제 1
5 7 11 13 15 23

 

풀이

 

❗ 정렬의 회전 횟수 및 비교횟수

정렬은 기본적으로 1번의 회전이 끝나고 찾은 배열의 최소값이나 최대값을, 맨앞이나 맨뒤의 값과 교체하는 것이다.

한 번의 회전 당 하나의 값이 정렬되는 꼴인데,

n개의 값을 정렬한다고 할 때, n-1개를 정렬하면 나머지 하나는 저절로 정렬되기 때문에 n-1번의 회전이 필요하게 된다.

그리고 n개의 값이 있다고 할 때, 맨 마지막 값은 비교할 필요가 없기 때문에 두 값을 비교하는 횟수는 n-1번이면된다.

 

 

선택정렬 부터 알아보도록 하자~!

 

 

선택정렬(Selection Sort): 최소값을 찾아 ‘이미 정렬된 값들’ 의 바로 뒤 값과 비교 후 자리를 바꾸는 방식의 정렬.

• 찾은 최소값의 위치를 저장해둘 변수가 필요하다.
• 1회전 시 맨 앞부터 → 방향으로 정렬된 값이 쌓인다.
• 시간 복잡도 O(n²)

gif 출처

코드

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int n = in.nextInt();
        int[] arr = new int[n];
        for(int i=0; i<n; i++) {
            arr[i] = in.nextInt();
        }
        //선택 정렬 오름차순
        for(int i=0; i<n-1; i++) { //맨마지막 값은 비교할 필요X
            int idx = i; //주의!!! i는 앞에 정렬되어 쌓인 마지막 인덱스
            //j: i의 뒤부터 가장 작은 값을 찾아서 위치를 idx에 저장
            for(int j=i+1; j<n; j++) {
                if(arr[j] < arr[idx]) idx = j;
            }
            //다 돌면 swap 
            int tmp = arr[i];
            arr[i] = arr[idx];
            arr[idx] = tmp;
        }

        for(int x : arr) {
            System.out.print(x+" ");
        }
    }
}

 

다시 풀었을 때:

package ps;

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		
		int n = in.nextInt();
		int[] arr = new int[n];
		
		for(int i=0; i<n; i++) { //1~100
			arr[i] = in.nextInt();
		}
		
		in.close();
		
		//오름차순 선택정렬
		for(int i=0; i<n-1; i++) {
			
			//1. i보다 작은 값 찾을 때까지 돈다
			for(int j=i+1; j<n; j++) {
				if(arr[i] > arr[j]) { //2. 찾으면
					//3. swap
					int temp = arr[i];
					arr[i] = arr[j];
					arr[j] = temp;
				}
			}
		}
		
		for(int a : arr) {
			System.out.print(a + " ");
		}
		
	}
}