삽입 정렬(JAVA)

개념)

i번째 숫자보다 앞에 있는 숫자들이 더 작다면  뒤로 밀리면서 정렬

즉, i번째의 값이 자기 자리에 삽이되면서 정렬

https://en.wikipedia.org/wiki/Insertion_sort

 

 

 

Code)

public static int[] insertionSort(int[] nums){
    for(int i=1; i<nums.length; i++){
        int target = nums[i];

        int j = i-1;

        while(j>=0 && nums[j] > target){
            nums[j+1] = nums[j];
            j--;
        }
        nums[j+1] = target;
    }
    return nums;
}

 

 

 

전체 Code)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

class Test{
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

        String s = bf.readLine();
        StringTokenizer st = new StringTokenizer(s);
        int[] nums = new int[st.countTokens()];

        for(int i=0; i<nums.length; i++){
            nums[i] = Integer.parseInt(st.nextToken());
        }

        nums = insertionSort(nums);

        print(nums);
    }

    public static int[] insertionSort(int[] nums){
        for(int i=1; i<nums.length; i++){
            int target = nums[i];

            int j = i-1;

            while(j>=0 && nums[j] > target){
                nums[j+1] = nums[j];
                j--;
            }
            nums[j+1] = target;
        }
        return nums;
    }

    public static void print(int[] nums) throws IOException{
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        for(int num : nums){
            bw.write(num+ " ");
        }
        bw.flush();
        bw.close();
    }
}