정렬 알고리즘

 

1. 선택 정렬

- 선택 정렬은 시간 복잡도가 O(N^2), 공간 복잡도가 O(N)인 정렬 알고리즘입니다. 

- 선택 정렬의 구현은 다음과 같습니다. 

public void selectionSort(int[] arr){
    
    	 int N = arr.length;
         
         for(int i=0; i<N; i++){
             
             int minIndex = i; 
             
             for(int j=i+1; j<N; j++){
                if(arr[j] < arr[minIndex]){
                    minIndex = j; 
                }
             }
            
             if(i != minIndex){
                int tmp = arr[i];
                arr[i] = arr[minIndex];
                arr[minIndex] = tmp;
             }
         }
 }

 

2. 삽입 정렬

- 삽입 정렬은 시간 복잡도가 O(N^2), 공간 복잡도가 O(N)인 알고리즘입니다. 

- 삽입 정렬의 구현은 다음과 같습니다. 

public void insertionSort(int[] arr){
    
    	 int N = arr.length;
         
         for(int i=1; i<N; i++){
             
             int target = arr[i];
             int j = i-1;
             
             while(j>=0 && arr[j] > target){
                 arr[j+1] = arr[j];
                 j--;
             }
             
             arr[j+1] = target;
             
         }
}

 

3. 버블 정렬

- 버블 정렬은 시간 복잡도가 O(N^2), 공간 복잡도가 O(N)인 알고리즘입니다.

- 버블 정렬의 구현은 다음과 같습니다. 

public void bubbleSort(int[] arr){
    
    	 int N = arr.length;
         
         for(int i=0; i<N-1; i++){
            for(int j=0; j<N-i-1; j++){
                if(arr[j] > arr[j+1]){
                    int tmp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = tmp;
                }
            }
         }
}