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

버블정렬 / 삽입정렬 / 선택정렬 구현하기

import java.util.Arrays;

public class Main {
    // 오름차순 기준 정렬 알고리즘

    // 버블 정렬
    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;
                }
            }
        }

    }
    
    // 삽입 정렬
    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;
                } else {
                    break;
                }
            }
        }
    }

    // 선택 정렬
    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;
        }
    }

    public static void main(String[] args) {
        // Test code
        int[] arr = {3, 5, 2, 7, 1, 4};
        bubbleSort(arr);
        System.out.println("버블 정렬: " + Arrays.toString(arr));

        arr = new int[]{3, 5, 2, 7, 1, 4};
        insertionSort(arr);
        System.out.println("삽입 정렬: " + Arrays.toString(arr));

        arr = new int[]{3, 5, 2, 7, 1, 4};
        selectionSort(arr);
        System.out.println("선택 정렬: " + Arrays.toString(arr));

    }
}

1. 버블정렬 (Bubble Sort)
   -동작원리 : 배열을 반복적으로 순회하면서 인접한 두 원소를 비교하고, 순서가 잘못된 경우 교환. 각 반복(iteration) 마다 가장 큰 원소가 끝으로 이동.

-시간복잡도 : O(n^2)
-두 개의 반복문을 사용하여, 내부 반복문에서 인접한 원소를 비교하고 교체

2. 삽입정렬 (Insertion Sort)
   -동작원리 : 배열을 순차적으로 탐색하며, 현재 원소를 적절한 위치에 삽입하여 정렬된 부분 배열을 유지
   -시간복잡도 : O(n^2)
   -외부 반복문은 배열을 순차적으로 탐색하고, 내부 반복문은 현재 원소의 정렬된 부분 배열의 올바른 위치에 삽입

3. 선택정렬 (Selection Sort)
   -동작원리 : 배열을 순차적으로 탐색하며, 현재 위치에 대해 가장 작은 원소를 찾아 교환. 이를 통해 배열을 정렬
   -시간복잡도 : O(n^2)
   -두 개의 반복문을 사용하여, 내부 반복문에서 현재 위치에 대해 가장 작은 원소를 찾아 교환

버블정렬을 배열 끝에서부터 거꾸로 순회하여 정렬하기

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;
                }
            }
        }

선택정렬을 배열 끝에서부터 거꾸로 순회하여 정렬하기

for (int i = arr.length - 1; i > 0; i--) {
            int max = i;
            for (int j = i - 1; j >= 0; j--) {
                if (arr[j] > arr[max]) {
                    max = j;
                }
            }
            int tmp = arr[i];
            arr[i] = arr[max];
            arr[max] = tmp;
        }