[java] 컬렉션 프레임워크의 검색과 정렬 알고리즘

05 Dec 2023

java

컬렉션 프레임워크는 자바에서 데이터를 저장하고 관리하는 데 사용되는 다양한 자료 구조와 알고리즘을 제공합니다. 이 중에서도 검색과 정렬 알고리즘은 많은 개발자들이 자주 사용하는 기능 중 하나입니다. 이번 글에서는 컬렉션 프레임워크에서 사용되는 검색과 정렬 알고리즘에 대해 알아보겠습니다.

검색 알고리즘

선형 검색 (Linear Search)

선형 검색은 가장 간단한 검색 알고리즘으로, 리스트나 배열을 처음부터 끝까지 순차적으로 탐색하여 원하는 값을 찾는 방법입니다. 시간 복잡도는 O(n)으로, 최악의 경우에는 모든 요소를 확인해야 합니다.

public int linearSearch(int[] arr, int target) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == target) {
            return i;
        }
    }
    return -1; // 값을 찾지 못한 경우 -1 반환
}

이진 검색 (Binary Search)

이진 검색은 정렬된 리스트나 배열에서 효율적으로 값을 찾는 알고리즘입니다. 중간에 있는 요소와 비교하여 탐색 범위를 반씩 줄여나가는 방식으로 동작합니다. 이 알고리즘은 시간 복잡도가 O(log n)으로, 검색 대상의 개수에 비례하지 않습니다. 하지만 이진 검색을 사용하기 위해서는 미리 정렬되어 있어야 한다는 제약이 있습니다.

public int binarySearch(int[] arr, int target) {
    int start = 0;
    int end = arr.length - 1;
    
    while (start <= end) {
        int mid = (start + end) / 2;
        
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            start = mid + 1;
        } else {
            end = mid - 1;
        }
    }
    
    return -1; // 값을 찾지 못한 경우 -1 반환
}

정렬 알고리즘

버블 정렬 (Bubble Sort)

버블 정렬은 인접한 두 요소를 비교하여 크기 순으로 정렬하는 알고리즘입니다. 각 패스마다 가장 큰 요소가 맨 뒤로 이동하므로, 정렬 범위를 하나씩 줄여가며 반복적으로 수행합니다. 시간 복잡도는 O(n^2)으로, 비교적 간단하지만 큰 데이터에는 비효율적입니다.

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

퀵 정렬 (Quick Sort)

퀵 정렬은 분할 정복 알고리즘을 사용하여 리스트를 정렬하는 알고리즘입니다. 리스트를 기준 값보다 작은 값들과 큰 값들로 분할하여 재귀적으로 정렬하는 방식으로 동작합니다. 평균적으로 O(n log n)의 시간 복잡도를 가지지만, 최악의 경우에는 O(n^2)까지 증가할 수 있습니다.

public void quickSort(int[] arr, int low, int high) {
    if (low < high) {
        int pivot = partition(arr, low, high);
        
        quickSort(arr, low, pivot - 1);
        quickSort(arr, pivot + 1, high);
    }
}

public int partition(int[] arr, int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;
    
    return i + 1;
}

결론

컬렉션 프레임워크에서 제공하는 검색과 정렬 알고리즘은 데이터의 처리와 관리에 매우 유용한 기능입니다. 이번 글에서는 선형 검색, 이진 검색, 버블 정렬, 퀵 정렬에 대해 간단하게 알아보았습니다. 이 외에도 많은 알고리즘이 있으며, 각각의 알고리즘에는 장단점과 적합한 상황이 있습니다. 개발자는 활용할 데이터의 특성과 성능 요건에 맞는 알고리즘을 선택하여 적절히 사용해야 합니다.