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

구현 난이도는 쉽지만 속도는 느린 알고리즘

1. 버블 정렬

• 인접한 데이터를 비교하며 자리를 바꾸는 방식
• 알고리즘 복잡도 O(n²)

버블 정렬

1번째를 기준으로 잡고 시작합니다.

첫 사이클을 완료하면 가장 큰 수가 맨 뒤로 이동하기 때문에

다음 사이클은 그 전까지만 수행하면 됩니다.

 

방법 1)

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

방법2)

public static void bubbleSort(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 tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
            }
        }
    }
}

 

2. 삽입 정렬

• 앞의 데이터를 정렬 해가면서 삽입 위치를 찾아 정렬하는 방식
• 알고리즘 복잡도 O(n²)

삽입 정렬

Step 4에서 6부터 시작하는 경우

6이랑 7을 비교해서 바꾸고

바뀐 6이랑 5랑 비교하고 이동이 없으며

쭉 3까지 수행합니다.

 

버블정렬과 비슷하게 이루어지지만 반대로 이루어진다는 느낌

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

 

3. 선택 정렬

• 최소 또는 최대 값을 찾아서 가장 앞 또는 뒤부터 정렬하는 방식
• 알고리즘 복잡도 O(n²)

선택 정렬

1) 최솟값을 맨 앞으로

private static void selectionSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        int min = i;
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[min]) {
                min = j;
            }
        }
        int tmp = arr[i];
        arr[i] = arr[min];
        arr[min] = tmp;
    }
}

1) 최댓값을 맨 뒤로

private static void selectionSort(int[] arr) {
    for (int i = arr.length - 1; i > 0; i--) {
        int max = i;
        for (int j = i - 1; j >= 0; j--) {
            if (arr[max] < arr[j]) {
                max = j;
            }
        }

        int tmp = arr[i];
        arr[i] = arr[max];
        arr[max] = tmp;
    }
}