[Arrays.sort없이] insertionSort

문제 

Arrays.sort()없이 sort하기.

insertion sort 방식 : 카드게임할 때, 패를 순차적으로 정리하는 느낌

I : 임의의 int [ ] arr (길이 1000이하)

O : 오름차순으로 정렬된 int [ ] output

public static void main(String[] args) {
    int[] output = insertionSort(new int[]{3, 1, 21});
    System.out.println(Arrays.toString(output));
}

 

나의 풀이

import java.util.Arrays;

public class insertionSort {
    // 조건
    public static void main(String[] args) {
        int[] output = insertionSort(new int[]{3, 1, 21});
        System.out.println(Arrays.toString(output));
    }
    
    // 코드 구현
    public static int[] insertionSort(int[] arr) {
        int[] output = new int[arr.length];

        for( int i= 0 ; i<arr.length ; i++) {
            int count= 0;
            for (int j= 0 ; j<arr.length ; j++) {
                if(arr[i]>arr[j]) count++;
            }
            output[count] = arr[i];
        }
        return output;
    }
}

 

레퍼런스

import java.util.Arrays;

public class reference {
    public static void main(String[] args) {
        int[] output = insertionSort(new int[]{3, 1, 21});
        System.out.println(Arrays.toString(output));

    }

    /*
      최적화를 적용한 코드
      : 이미 정렬된 숫자보다 큰 수를 비교하는 경우를 제거함으로써,
        불필요한 처리과정을 최소화  
    */

    public static int[] insertionSort(int[] arr) {
        for (int index = 1; index < arr.length; index++) {
            int target = index;
            while (target > 0 && arr[target - 1] > arr[target]) {
                int temp = arr[target - 1];
                arr[target - 1] = arr[target];
                arr[target] = temp;
                target--;
            }
        }
        return arr;
    }
}

깃 링크

https://github.com/PNUHCT/AlgorismStorage.git