[정렬] 삽입 정렬 .java

설명

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

정렬하는 방법은 삽입정렬입니다.

입력

첫 번째 줄에 자연수 N(1 <=N <=100)이 주어집니다.

두 번째 줄에 N개의 자연수가 공백을 사이에 두고 입력됩니다. 각 자연수는 정수형 범위 안에 있습니다.

출력

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

예시 입력 1 

6
11 7 5 6 10 9

예시 출력 1

5 6 7 9 10 11

 

 

내 풀이

1. 외부 for문: 열의 모든 요소를 차례대로 정렬

- cnt에 현재 정렬할 값을 저장, j는 정렬된 부분의 마지막 인덱스

 

2. 내부 while문 : 정렬된 부분에서 cnt보다 큰 값들을 오른쪽으로 이동

=> 이후 j를 감소시켜 이전 요소로 이동

 

3. while문 이후: nums[j + 1] = cnt;를 통해 cnt 값을 정렬된 부분의 적절한 위치에 삽입

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        int[] nums = new int[n];
        for(int i = 0; i < n; i++){
            nums[i] = sc.nextInt();
        }
        //최솟값을 찾고 이를 현재 위치한 값과 바꾸기
        for(int i = 0; i < n; i++){
           int cnt = nums[i];//현재 정렬할 값
           int j = i - 1;
           //정렬된 부분에서 현재 값보다 큰 값들을 오른쪽으로 이동
           while(j >= 0 && nums[j] > cnt) {
               nums[j + 1] = nums[j];//큰 값을 오른쪽으로
               j--;//이전 인덱스로 이동
           }
           nums[j + 1] = cnt;//현재 값(cnt)을 정렬된 위치에 삽입
        }

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


    }
}

 

 

다른 풀이

• 외부 for문 - i : 1부터 n까지, tmp = arr [i];
• 내부 for문 - j : i-1부터 0 이상까지 j -- 
• -> arr [j] > tmp 면(크면 뒤로 밀기) -> arr [j+1] = arr [j];
• 이후 j--로 내부 for문이 멈춤 -> 멈춘 j 지점 뒤에다 tmp 넣기 arr [j+1] = tmp

항상 for문 j가 멈춘 그 j 바로 뒤 인덱스에 tmp삽입이 포인트

=> 내부 for문에서 사용한 j를 for문 이후에도 사용하기 위해 j를 내부  for문전에서 선언함

 

import java.util.Scanner;

public class Main {
    public int[] solution(int n , int[] arr){

        for(int i = 1 ; i < n; i++){
            int tmp = arr[i];
            int j;
            for(j = i-1; j >=0 ; j--){
                if(arr[j] > tmp){
                    arr[j+1] = arr[j];//오른쪽으로 밀기
                } else break;
            }
            arr[j+1] = tmp;
        }
        return arr;
    }
    public static void main(String[] args) {
        Main T = new Main();
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        int[] arr = new int[n];
        for(int i = 0; i < n; i++){
            arr[i] = sc.nextInt();
        }

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

    }
}

 

 

💡💡

여러 정렬 중에 삽입 정렬이 이해하는데 제일 시간이 걸렸다... 미는 것과 미는 것이 끝난 후 j의 위치 바로 뒤가 현재 tmp의 자리이다!

삽입 정렬은 배열에서 각 요소를 선택하여 정렬된 부분에 적절한 위치에 삽입하는 방식으로 배열을 정렬하는 알고리즘이다