[JAVA] - 정렬 (버블, 삽입, 선택)

정렬 종류

• 출처 : https://st-lab.tistory.com/179

버블 정렬

• 두 인접한 데이터를 비교해서 앞에 있는 데이터가 뒤에 있는 데이터보다 크면, 자리를 바꾸는 알고리즘

• 오름차순 기준으로 한 회전 당 제일 큰 값을 뒤로 보낸다.

선택 정렬

• 주어진 데이터 중, 최솟값을 찾아 맨 앞에 위치한 값과 교체 하는 알고리즘
• 교체 마다 시작 인덱스를 증가 시킨다.

public class Chap01 {
    public static void main(String[] args) {
        int[] a = {20, 35, 10, 6, 94, 1};
        int[] b = {20, 35, 10, 6, 94, 1 };
        Chap01 main = new Chap01();
        System.out.println("Bubble Sort" +main.bubbleSort(a));
        System.out.println("Insert Sort" + main.selectSort(b));
    }

    private String bubbleSort(int[] a) {
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < a.length -i -1; j++) {
                if (a[j] > a[j+1]) {
                    swap(a,j,j+1);
                }
            }
            System.out.println(Arrays.toString(a));
        }
        return Arrays.toString(a);
    }

    private String selectSort(int[] a) {
        for (int i = 0; i < a.length-1; i++) {
            for (int j = i+1; j <a.length; j++) {
                if (a[i] > a[j]) {
                    swap(a, i, j);
                }
            }
            System.out.println(Arrays.toString(a));
        }

        return Arrays.toString(a);
    }

    private void swap(int a[], int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}
[출력]
1회전 : [20, 10, 6, 35, 1, 94]
2회전 : [10, 6, 20, 1, 35, 94]
3회전 : [6, 10, 1, 20, 35, 94]
4회전 : [6, 1, 10, 20, 35, 94]
5회전 : [1, 6, 10, 20, 35, 94]
6회전 : [1, 6, 10, 20, 35, 94]
Bubble Sort : [1, 6, 10, 20, 35, 94]
1회전 : [1, 35, 20, 10, 94, 6]
2회전 : [1, 6, 35, 20, 94, 10]
3회전 : [1, 6, 10, 35, 94, 20]
4회전 : [1, 6, 10, 20, 94, 35]
5회전 : [1, 6, 10, 20, 35, 94]
Select Sort : [1, 6, 10, 20, 35, 94]

삽입 정렬

• 현재 비교하고자 하는 타겟과 그 이전의 원소들과 비교하며 자리를 교환하는 알고리즘
• 데이터를 비교하면서 찾기 때문에 비교정렬, 또는 추가적인 공간이 필요없어 제자리 정렬로 부르기도 한다.

private String insertSort(int[] a) {
    for (int i = 1; i < a.length; i++) {
        int target = a[i];
        int j = i - 1;
        while (j >= 0 && target < a[j]) {
            a[j + 1] = a[j];
            j--;
        }
        a[j+1] = target;
        System.out.println(i+"회전 : "+Arrays.toString(a));
    }
    return Arrays.toString(a);
}
[출력]
1회전 : [20, 35, 10, 6, 94, 1]
2회전 : [10, 20, 35, 6, 94, 1]
3회전 : [6, 10, 20, 35, 94, 1]
4회전 : [6, 10, 20, 35, 94, 1]
5회전 : [1, 6, 10, 20, 35, 94]
Insert Sort : [1, 6, 10, 20, 35, 94]

• 버블 , 선택 정렬과는 다르게 최선의 경우 O(N)의 시간복잡도를 갖는다.
• 역순에 가까울 수록 비효율적이며 최악은 O(N^2)의 시간복잡도를 갖는다.
• 즉, O(N^2)을 갖는 버블, 선택, 삽입 정렬중에선 가장 빠른 알고리즘이다.