[java] 정렬 알고리즘 규칙

12 Dec 2023

java

정렬 알고리즘은 데이터를 특정한 순서로 나열하는 알고리즘이며, 자바에서는 배열이나 리스트와 같은 자료구조를 정렬하는 데에 사용됩니다. 정렬 알고리즘은 선택 정렬, 버블 정렬, 삽입 정렬, 퀵 정렬, 병합 정렬, 힙 정렬 등이 있습니다.

선택 정렬 (Selection Sort)

선택 정렬은 배열을 반복하면서 가장 작은 요소를 선택하여 정렬하는 간단한 알고리즘입니다. 시간 복잡도는 O(n^2) 로 비교적 느린 편이지만 배열의 길이가 작을 때는 효율적입니다.

public class SelectionSort {
    public void sort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            int temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }
    }
}

버블 정렬 (Bubble Sort)

버블 정렬은 서로 인접한 두 요소를 비교하여 순서가 잘못된 경우에 서로 교환하는 정렬 알고리즘입니다. 시간 복잡도는 선택 정렬과 마찬가지로 O(n^2) 입니다.

public class BubbleSort {
    public void sort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }
}

삽입 정렬 (Insertion Sort)

삽입 정렬은 요소를 하나씩 골라 해당 요소를 적절한 위치에 삽입하는 정렬 알고리즘입니다. 시간 복잡도는 최선의 경우 O(n) 이며, 평균적으로 O(n^2) 입니다.

public class InsertionSort {
    public void sort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            int key = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }
}

정렬 알고리즘은 애플리케이션의 성능에 큰 영향을 미치므로 알맞게 선택하는 것이 중요합니다.

자세한 내용은 아래 참고 자료를 참고하세요.