알고리즘/이론

버블 정렬, 선택 정렬, 삽입 정렬

정렬 알고리즘 중 제일 처음에 공부하게 되는 세가지 정렬

1. 버블 정렬 ( Bubble Sort )

public class BubbleSort {
    static void sort(int[] arr){
        for(int i=arr.length-1; i>0; i--){
            for(int j=0; j<i; j++){
                if(arr[j] > arr[j+1]){
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
    }
}
public class SortTest {
    public static void main(String[] args) {
        int[] arr = AlgoritmUtil.makeRandomIntArray(1, 100, 10);
        System.out.println("BEFORE : "+Arrays.toString(arr));
        BubbleSort.sort(arr);
        System.out.println("AFTER : "+Arrays.toString(arr));
    }
}
/*
BEFORE : [15, 41, 2, 43, 43, 53, 94, 85, 42, 55]
AFTER : [2, 15, 41, 42, 43, 43, 53, 55, 85, 94]
*/

2. 선택 정렬 ( Selection Sort )

public class SelectionSort {
    static void sort(int[] arr){
        for(int i=0; i<arr.length-1; i++){
            int minIndex = i;
            for(int j=i+1; j<arr.length; j++){
                if(arr[minIndex] > arr[j]){
                    minIndex = j;
                }
            }
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
}
public class SortTest {
    public static void main(String[] args) {
        int[] arr = AlgoritmUtil.makeRandomIntArray(1, 10, 10);
        System.out.println("========== SELECTION ==========");
        System.out.println("BEFORE : "+Arrays.toString(arr));
        SelectionSort.sort(arr);
        System.out.println("AFTER : "+Arrays.toString(arr));
    }
}
//BEFORE : [8, 10, 8, 1, 4, 1, 9, 6, 2, 9]
//AFTER : [1, 1, 2, 4, 6, 8, 8, 9, 9, 10]

3. 삽입 정렬 ( Insertion Sort )

public class InsertionSort {
    static void sort(int[] arr){
        for(int i=1; i<arr.length; i++){
            int tempValue = arr[i];
            int j = 0;
            for(j=i-1; j>=0; j--){
                if(arr[j] > tempValue){
                    arr[j+1] = arr[j];
                }else{
                    break;
                }
            }
            arr[j+1] = tempValue;
        }
    }
}
public class SortTest {
    public static void main(String[] args) {
        int[] arr = AlgoritmUtil.makeRandomIntArray(1, 10, 10);
        System.out.println("========== INSERTION ==========");
        System.out.println("BEFORE : "+Arrays.toString(arr));
        InsertionSort.sort(arr);
        System.out.println("AFTER : "+Arrays.toString(arr));
    }
}
//BEFORE : [4, 6, 1, 9, 3, 1, 3, 5, 6, 5]
//AFTER : [1, 1, 3, 3, 4, 5, 5, 6, 6, 9]