[java] 소트 알고리즘

04 Dec 2023

java

소트 알고리즘은 정렬된 데이터를 얻기 위해 사용되는 알고리즘입니다. 배열이나 리스트에 포함된 요소들을 순서대로 재배열하여 정렬된 결과를 얻을 수 있습니다. 여러 가지 소트 알고리즘이 존재하며, 각각의 알고리즘은 다양한 시간 복잡도와 성능 특성을 가지고 있습니다.

버블 소트 (Bubble Sort)

버블 소트는 인접한 두 개의 요소를 비교하고 필요한 경우 위치를 교환하는 과정을 반복하여 정렬을 수행합니다. 가장 큰 요소가 배열의 마지막으로 이동할 때까지 반복 작업을 수행하며, 각 패스마다 가장 큰 요소가 정렬의 마지막으로 이동합니다.

public void bubbleSort(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;
            }
        }
    }
}

선택 소트 (Selection Sort)

선택 소트는 정렬되지 않은 부분에서 가장 작은 요소를 찾아 첫 번째 요소와 교환하는 과정을 반복하여 정렬을 수행합니다. 첫 번째 요소를 고정한 후, 나머지 요소들 중 가장 작은 값을 찾아 첫 번째 요소와 교환합니다. 이러한 과정을 모든 요소에 대해 반복하면서 정렬을 완성합니다.

public void selectionSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n-1; i++) {
        int minIdx = i;
        for (int j = i+1; j < n; j++) {
            if (arr[j] < arr[minIdx]) {
                minIdx = j;
            }
        }
        // 가장 작은 요소와 첫 번째 요소 교환
        int temp = arr[minIdx];
        arr[minIdx] = arr[i];
        arr[i] = temp;
    }
}

위의 예시는 자바로 구현된 버블 소트와 선택 소트의 예시입니다. 이 외에도 삽입 소트, 퀵 소트, 병합 소트 등 다양한 소트 알고리즘이 있습니다.

더 많은 소트 알고리즘에 대해서는 이곳에서 참조할 수 있습니다.