정렬 알고리즘

Q1. 선택 정렬 알고리즘은 어떻게 구현하는가?

 

import java.util.*;


public class SelectionSort{ 

    public void swapElements(int[] array, int i, int j){
           int temp = array[i];
           array[i] = array[j];
           array[j] = temp;
    }

    public int findLowest(int[] array, int start){
           
           int lowIndex = start;
           
           for(int i=start; i<array.length; i++){
                if(array[i] < array[lowIndex]){
                     lowIndex = i;     
                }
           }
           return lowIndex;
    }
    
    
    public void selectionSort(int[] array){
           
           for(int i=0; i<array.length; i++){
                int j = findLowest(array, i);
                swapElements(array, i, j);
           }
    }
    
  }

 

Q2. 선택 정렬의 총 연산 횟수는 무엇에 비례하는가?

- O(n2)에 비례한다. 

 

Q3. Arrays.sort()는 어떤 정렬 알고리즘을 사용하는가? 그것의 시간복잡도는 무엇인가?

- 퀵소트를 사용한다. 퀵소트의 시간 복잡도는 O(nlogn)이다. 

 

참고

Q1~Q2 자바로 배우는 핵심 자료구조와 알고리즘 5/21

Q3 6/9

A1~A2 5/24