선택 정렬

 

Q1. 선택 정렬에서 데이터 원소가 N개일 때, 최대 단계수는 몇인가?

       이것을 시간 복잡도로 나타내면 어떠한가?

 

 

Q2. 왜 최대 단계수와 시간 복잡도로 나타내는 것에 차이가 발생하는가?

       그것을 빅오의 규칙과 연관해서 어떻게 설명할 수 있는가?

- 

 

 

Q3. '빅오의 본질'에 따르면 데이터가 늘어날 때, 

       알고리즘 단계 수가 '어떤'지가 중요한가?

- 

 

 

Q4. O(N)은 무슨 성장인가? 그리고 O(N2)은 무슨 성장인가?

- 

 

 

Q5. 버블 정렬과 선택 정렬을 비교하면 무엇이 무엇보다 몇 배 빠른가?

- 

 

 

Q6. 선택 정렬을 구현해보시오.

public class Main{


   public void selection_sort(int[] a){
   
      int len = a.length;
   
      for(int i=0; i<len-1; i++){
        int minIndex = i;
        
        for(int j=i+1; j<len; j++){
           if(a[minIndex] > a[j]){
              j = minIndex;
           }
        }
      
        swap(a, i, minIndex);
      }
   
   }
   
   public void swap(int[] a, int i, int minIndex){
        int tmp = a[i];
        a[i] = a[minIndex];
        a[minIndex] = tmp;
   }
   
 }

 

 

참고

Q1~Q5 누구나 자료구조와 알고리즘 6/24