정렬

[정렬]

1. 버블 정렬
   • 두 인접한 데이터를 비교해 앞에 있는 데이터가 뒤에 있는 데이터보다 크면, 자리를 바꾸는 정렬 알고리즘
   • 총 라운드 = **배열크기 - 1**
   • 각 라운드별 비교 횟수 = **배열 크기 - 라운드 횟수**
   • 

     

https://en.wikipedia.org/wiki/Bubble_sort

public class Bubble_Sort{
    public static void bubble_sort(int[] a){
        bubble_sort(a, a.length);
    }
    
    private static void bubble_sort(int[] a, int size){
        for(int i=1; i<size; i++){ //총 라운드 = 배열크기 - 1
            for(int j=0; j < size-i; j++){ //각 라운드별 비교 횟수 = 배열크기 - 라운드 횟수
                if(a[j] > a[j+1]){
                    swap(a, j, j+1);
                }
            }
        }
    }
    
    private static void swap(int[] a, int i, int j){
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

 

1. 삽입 정렬
   • 두번째 인덱스부터 시작(첫번째 원소는 타겟이 되어도 비교할 원소가 없기 때문에 두번째 원소부터)
   • 앞에서부터 해당 원소가 위차할 곳을 탐색하고 해당 위치에 삽입
   • 거의 정렬된 배열에서 좋은 성능을 보임https://en.wikipedia.org/wiki/Insertion_sort
   • 

     

   public class Insertion_sort{
       public static void insertion_sort(int[] a){
           insertion_sort(a, a.length);
       }
       
       public static void insertion_sort(int[] a, int size){
           for(int i=1; i<size; i++){ //첫번째 원소는 타겟이 되어도 비교할 원소 x => 두번째부터
               int target = a[i]; 
               
               int j = i-1;
               
               while(j >= 0 && target < a[j]){ //타겟이 이전 원소보다 크기 전까지 반복
                   a[j+1] = a[j]; //이전 원소를 한칸씩 미룸
                   j--;
               }
               //위 반복문에서 탈출하는 경우 -> 앞의 원소가 타겟보다 작다는 뜻
               //타겟 원소는 j번째 원소의 뒤에 위치하여야 한다 -> 타겟 = j+1
               a[j+1] = target; 
           }
       }
   }

1. 선택 정렬
   • 순서
     1. 주어진 데이터 중 최소값을 찾음
     2. 해당 최소값을 데이터 맨 앞에 위치한 값과 교체
     3. 맨 앞 위치를 뺀 나머지 데이터를 동일한 방법으로 반복


public class Selection_sort{
    public static void selection_sort(int[] a){
        selection_sort(a, a.length);
    }
    
    private static void selection_sort(int[] a, int size){
        for(int i=0; i <size-1; i++) { 
            min_index = i;
            for(int j=i+1; j<size; j++){
                if(a[j] < a[min_index]){
                    min_index = j;
                }
            }
            swap(a, min_index, i);
        }
    }
    
    private static void swap(int[] a, int i, int j){
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

 

 

 

https://st-lab.tistory.com/195