[알고리즘 - 정렬] Java 삽입, 선택, 버블 정렬

 

 

 

import java.util.ArrayList;

public class Main {

    private void swap(int[] arr, int idx1, int idx2) {
        int tmp = arr[idx1];
        arr[idx1] = arr[idx2];
        arr[idx2] = tmp;
    }

    // 삽입 정렬
    private int[] sortByInsertionSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int tmp = arr[i];
            int j = i - 1;
            while (j >= 0 && tmp < arr[j]) {
                arr[j+1] = arr[j];
                j--;
            }
            arr[j+1] = tmp;
        }
        return arr;
    }

    // 선택정렬
    private int[] sortBySelectionSort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            int minIdx = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[minIdx]) {
                    minIdx = j;
                }
            }
            swap(arr, minIdx, i);
        }
        return arr;
    }

    // 버블정렬
    private int[] sortByBubbleSort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length - 1; j++) {
                if(arr[j] > arr[j+1]){
                    swap(arr, j, j + 1);
                }
            }
        }

        return arr;
    }

    // 셸 정렬
    private int[] sortByShellSort(int[] arr) {
        for (int h = arr.length / 2; h > 0; h /= 2) {
            for (int i = h; i < arr.length; i++) {
                int tmp = arr[i];
                int j = i - h;
                while (j >= 0 && tmp < arr[j]) {
                    arr[j+h] = arr[j];
                    j = j - h;
                }
                arr[j + h] = tmp;
            }
        }

        return arr;
    }

    public static void main(String[] args) {

        int[] array = {5, 4, 1, 2, 3, 6, 8, 7, 9, 10};

        Main T = new Main();

        // 삽입정렬 N, N^2, N^2
        System.out.print("삽입 정렬 : ");
        for (int x : T.sortByInsertionSort(array)) {
            System.out.print(x + " ");
        }

        // 선택정렬 N^2, N^2, N^2
        System.out.print("\n" + "선택 정렬 : ");
        for (int x : T.sortBySelectionSort(array)) {
            System.out.print(x + " ");
        }

        // 버블 정렬 N^2, N^2, N^2
        System.out.print("\n" + "버블 정렬 : ");
        for (int x : T.sortByBubbleSort(array)) {
            System.out.print(x + " ");
        }


        // 버블 정렬 N^2, N^2, N^2
        System.out.print("\n" + "버블 정렬 : ");
        for (int x : T.sortByBubbleSort(array)) {
            System.out.print(x + " ");
        }

        // 셸 정렬 N, N^1.5, N^2
        System.out.print("\n" + "셸 정렬 : ");
        for (int x : T.sortByShellSort(array)) {
            System.out.print(x + " ");
        }
    }




}

---

레퍼런스

 

https://velog.io/@pppp0722/%EC%A0%95%EB%A0%AC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-7%EA%B0%9C-%EC%A0%95%EB%A6%AC-Java#%ED%80%B5-%EC%A0%95%EB%A0%ACquick-sort

정렬 알고리즘 7개 정리 (Java)