삽입 정렬

Q1. 어떤 시나리오를 구분하는 능력은 기존 알고리즘을 최적화해서

       훨씬 빠르게 만드는 것만큼이나 사용자 요구에 맞는 최적의 알고리즘을 고르는

       핵심 기술인가?

- 최악, 평균, 최선의 시나리오를 구분하는 능력 

 

 

Q2. 어떤 경우를 대비하는 것도 좋지만 대부분은 어떤 경우가 일어나는가?

- 최악의 경우를 대비하는 것도 좋지만 대부분은 평균적인 경우가 일어난다. 

 

 

Q3. 삽입 정렬을 구현하라 

class InsertionSort{
    
    public int[] insertionSort(int[] arr){
    
   	    int len = arr.length; 

        for(int i=1; i<len; i++){

            int target = a[i];
            int j = i-1;

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

            arr[j+1] = value;
        }
  
    }



}

class Main{

    public int[] insertionSort(int[] a){
    
          int len = a.length;
          
          for(int i=1; i<len; i++){
          
             int tmp = a[i]; 
             int position = i-1;
             
             while(position >= 0){
                if(a[position] > tmp){
                  a[position+1] = a[position];
                  position--;
                }else{
                  break;
                }
             }
             
             a[position] = tmp;
         }
         
         return a; 
    
    }
          
}

 

참고

Q1~Q3 누구나 자료구조와 알고리즘 6/27 

A1~A3 6/28