자바의 기본적인 정렬 알고리즘: 버블, 선택, 삽입 정렬

정렬 알고리즘은 컴퓨터 과학의 핵심적인 부분으로, 데이터를 특정 순서에 따라 배열하는 방법을 다룹니다. 효율적인 정렬은 데이터 검색 및 처리 속도에 큰 영향을 미치므로, 다양한 정렬 기법을 이해하는 것이 중요합니다.

이 글에서는 기본적인 정렬 알고리즘 중 세 가지인 버블 정렬(Bubble Sort), 선택 정렬(Selection Sort), 그리고 삽입 정렬(Insertion Sort)의 원리를 살펴보고, 각 알고리즘의 자바(Java) 구현 방법과 성능 특성을 분석합니다.

버블 정렬 (Bubble Sort)

원리

버블 정렬은 인접한 두 요소를 비교하여 정렬하는 가장 간단한 정렬 알고리즘 중 하나입니다. 이 알고리즘은 배열의 시작부터 끝까지 순회하며, 인접한 두 요소의 순서가 잘못되어 있다면 서로 위치를 교환합니다. 이 과정을 한 번의 '패스(Pass)'라고 하는데, 각 패스마다 가장 큰(또는 가장 작은) 요소가 배열의 끝으로 '버블처럼' 이동하는 것이 특징입니다.

  1. 첫 번째 요소부터 시작하여 바로 다음 요소와 비교합니다.
  2. 만약 앞의 요소가 뒤의 요소보다 크다면, 두 요소의 위치를 교환합니다.
  3. 이 과정을 배열의 끝까지 반복하면, 가장 큰 요소가 배열의 맨 끝으로 이동하게 됩니다.
  4. 가장 큰 요소가 제 위치를 찾으면, 해당 요소를 제외한 나머지 배열에 대해 위 과정을 반복합니다.
  5. 총 N개의 요소가 있을 때, N-1번의 패스를 수행하면 정렬이 완료됩니다.

예시

다음 배열 [7, 6, 9, 8, 5, 1]을 오름차순으로 정렬하는 과정을 살펴보겠습니다.

  • 초기 상태: [7, 6, 9, 8, 5, 1]
  • 첫 번째 패스: 가장 큰 숫자가 오른쪽 끝으로 이동합니다.
    • (7, 6) 비교 및 교환 → [6, 7, 9, 8, 5, 1]
    • (7, 9) 비교, 교환 없음 → [6, 7, 9, 8, 5, 1]
    • (9, 8) 비교 및 교환 → [6, 7, 8, 9, 5, 1]
    • (9, 5) 비교 및 교환 → [6, 7, 8, 5, 9, 1]
    • (9, 1) 비교 및 교환 → [6, 7, 8, 5, 1, 9] (9가 최종 위치)
  • 두 번째 패스: [6, 7, 8, 5, 1, 9] (9 제외)
    • (6, 7) 비교, 교환 없음 → [6, 7, 8, 5, 1, 9]
    • (7, 8) 비교, 교환 없음 → [6, 7, 8, 5, 1, 9]
    • (8, 5) 비교 및 교환 → [6, 7, 5, 8, 1, 9]
    • (8, 1) 비교 및 교환 → [6, 7, 5, 1, 8, 9] (8이 최종 위치)
  • 세 번째 패스: [6, 7, 5, 1, 8, 9] (8, 9 제외)
    • (6, 7) 비교, 교환 없음 → [6, 7, 5, 1, 8, 9]
    • (7, 5) 비교 및 교환 → [6, 5, 7, 1, 8, 9]
    • (7, 1) 비교 및 교환 → [6, 5, 1, 7, 8, 9] (7이 최종 위치)
  • 네 번째 패스: [6, 5, 1, 7, 8, 9] (7, 8, 9 제외)
    • (6, 5) 비교 및 교환 → [5, 6, 1, 7, 8, 9]
    • (6, 1) 비교 및 교환 → [5, 1, 6, 7, 8, 9] (6이 최종 위치)
  • 다섯 번째 패스: [5, 1, 6, 7, 8, 9] (6, 7, 8, 9 제외)
    • (5, 1) 비교 및 교환 → [1, 5, 6, 7, 8, 9] (5가 최종 위치)
  • 최종 정렬 결과: [1, 5, 6, 7, 8, 9]

구현 아이디어

버블 정렬은 중첩된 반복문(nested loop)을 사용하여 구현됩니다. 바깥쪽 반복문은 전체 배열에 대한 패스 횟수를 제어하며, 배열의 크기가 N일 때 N-1번 실행됩니다. 안쪽 반복문은 각 패스에서 인접한 요소들을 비교하고 필요에 따라 교환하는 역할을 합니다. 각 패스가 끝날 때마다 가장 큰 요소는 이미 올바른 위치에 있으므로, 다음 패스에서는 비교 범위를 한 칸 줄여 효율을 높일 수 있습니다.

코드 구현


class BubbleSorter {
    private int[] dataArray;
    private int arrLength;

    public BubbleSorter(int[] inputArr) {
        this.dataArray = inputArr;
        this.arrLength = inputArr.length;
    }

    public void printElements() {
        for (int element : dataArray) {
            System.out.print(element + " ");
        }
        System.out.println();
    }

    public void sortElements() {
        // 배열의 모든 요소가 정렬될 때까지 반복 (N-1번의 패스)
        for (int outerIdx = 0; outerIdx < arrLength - 1; outerIdx++) {
            // 각 패스에서 이미 정렬된 마지막 요소를 제외하고 비교
            for (int innerIdx = 0; innerIdx < arrLength - 1 - outerIdx; innerIdx++) {
                // 인접한 두 요소 비교 및 필요 시 교환
                if (dataArray[innerIdx] > dataArray[innerIdx + 1]) {
                    int tempVal = dataArray[innerIdx];
                    dataArray[innerIdx] = dataArray[innerIdx + 1];
                    dataArray[innerIdx + 1] = tempVal;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] numbers = {77, 29, 28, 36, 33, 25, 10};
        BubbleSorter sorter = new BubbleSorter(numbers);

        System.out.println("정렬 전 데이터:");
        sorter.printElements();

        sorter.sortElements();

        System.out.println("정렬 후 데이터:");
        sorter.printElements();
    }
}

요약 및 분석

버블 정렬은 구현이 매우 간단하지만, 효율성 측면에서는 비효율적인 정렬 방식입니다. N개의 요소를 가진 배열에 대해 다음과 같은 특성을 보입니다:

  • 시간 복잡도: 최악의 경우(역순 정렬된 배열)와 평균적인 경우 모두 O(N2)의 시간 복잡도를 가집니다. 이는 요소의 수가 증가할수록 정렬 시간이 제곱에 비례하여 증가함을 의미합니다.
  • 비교 횟수: 총 N*(N-1)/2 번의 비교가 발생합니다.
  • 교환 횟수: 최악의 경우 총 N*(N-1)/2 번의 교환이 발생할 수 있습니다.

이러한 특성 때문에 버블 정렬은 실제 시스템에서는 거의 사용되지 않으며, 주로 정렬 알고리즘의 개념을 이해하기 위한 교육용으로 활용됩니다.

선택 정렬 (Selection Sort)

원리

선택 정렬은 배열에서 가장 작거나(오름차순 기준) 가장 큰 요소를 찾아 적절한 위치로 옮기면서 정렬하는 알고리즘입니다. 버블 정렬과 비교했을 때, 비교 횟수는 비슷하지만 교환 횟수가 훨씬 적다는 장점이 있습니다.

  1. 배열의 첫 번째 위치(인덱스 0)에 올바른 요소를 찾기 위해, 나머지 배열 전체에서 가장 작은 요소를 찾습니다.
  2. 찾은 가장 작은 요소를 첫 번째 위치의 요소와 교환합니다.
  3. 이제 첫 번째 요소는 정렬이 완료된 상태입니다. 다음으로 두 번째 위치(인덱스 1)에 올바른 요소를 찾기 위해, 나머지 배열(두 번째 요소부터 끝까지)에서 가장 작은 요소를 찾습니다.
  4. 찾은 요소를 두 번째 위치의 요소와 교환합니다.
  5. 이 과정을 배열의 끝까지 반복하면 전체 배열이 정렬됩니다. 각 단계에서 단 한 번의 교환만 발생하므로, 교환 횟수가 적습니다.

예시

배열 [7, 6, 9, 8, 5, 1]을 오름차순으로 정렬하는 과정을 살펴보겠습니다.

  • 초기 상태: [7, 6, 9, 8, 5, 1]
  • 첫 번째 패스 (인덱스 0):
    • [7, 6, 9, 8, 5, 1]에서 가장 작은 요소는 1입니다.
    • 인덱스 0의 7과 1을 교환합니다. → [1, 6, 9, 8, 5, 7]
  • 두 번째 패스 (인덱스 1):
    • [1, 6, 9, 8, 5, 7]에서 인덱스 1부터 끝까지 (6, 9, 8, 5, 7) 중 가장 작은 요소는 5입니다.
    • 인덱스 1의 6과 5를 교환합니다. → [1, 5, 9, 8, 6, 7]
  • 세 번째 패스 (인덱스 2):
    • [1, 5, 9, 8, 6, 7]에서 인덱스 2부터 끝까지 (9, 8, 6, 7) 중 가장 작은 요소는 6입니다.
    • 인덱스 2의 9와 6을 교환합니다. → [1, 5, 6, 8, 9, 7]
  • 네 번째 패스 (인덱스 3):
    • [1, 5, 6, 8, 9, 7]에서 인덱스 3부터 끝까지 (8, 9, 7) 중 가장 작은 요소는 7입니다.
    • 인덱스 3의 8과 7을 교환합니다. → [1, 5, 6, 7, 9, 8]
  • 다섯 번째 패스 (인덱스 4):
    • [1, 5, 6, 7, 9, 8]에서 인덱스 4부터 끝까지 (9, 8) 중 가장 작은 요소는 8입니다.
    • 인덱스 4의 9와 8을 교환합니다. → [1, 5, 6, 7, 8, 9]
  • 최종 정렬 결과: [1, 5, 6, 7, 8, 9]

구현 아이디어

선택 정렬도 중첩 반복문을 사용합니다. 바깥쪽 반복문은 현재 정렬할 위치(i)를 나타내며, 배열의 시작부터 끝까지(N-1번) 진행됩니다. 각 i번째 위치에 올바른 요소를 넣기 위해, 안쪽 반복문은 i+1번째 요소부터 배열의 끝까지 탐색하여 가장 작은 요소의 인덱스(minIndex)를 찾습니다. 안쪽 반복문이 완료되면, i번째 요소와 minIndex에 해당하는 요소를 단 한 번 교환합니다. 이 과정을 통해 각 패스마다 하나의 요소가 최종 위치를 찾게 됩니다.

코드 구현


class SelectionSorter {
    private int[] dataArray;
    private int arrLength;

    public SelectionSorter(int[] inputArr) {
        this.dataArray = inputArr;
        this.arrLength = inputArr.length;
    }

    public void printElements() {
        for (int element : dataArray) {
            System.out.print(element + " ");
        }
        System.out.println();
    }

    public void sortElements() {
        // 배열의 시작부터 끝-1까지 반복 (마지막 요소는 자동으로 정렬됨)
        for (int currIdx = 0; currIdx < arrLength - 1; currIdx++) {
            int minValIdx = currIdx; // 현재 패스에서 가장 작은 요소의 인덱스

            // 현재 위치 다음부터 배열의 끝까지 가장 작은 요소를 탐색
            for (int searchIdx = currIdx + 1; searchIdx < arrLength; searchIdx++) {
                if (dataArray[searchIdx] < dataArray[minValIdx]) {
                    minValIdx = searchIdx; // 더 작은 요소가 발견되면 인덱스 업데이트
                }
            }

            // 가장 작은 요소가 현재 위치의 요소와 다르면 위치 교환
            if (minValIdx != currIdx) { // 최적화: 같은 위치일 경우 교환 불필요
                int swapTemp = dataArray[currIdx];
                dataArray[currIdx] = dataArray[minValIdx];
                dataArray[minValIdx] = swapTemp;
            }
        }
    }

    public static void main(String[] args) {
        int[] numbers = {100, 45, 36, 21, 17, 13, 7};
        SelectionSorter sorter = new SelectionSorter(numbers);

        System.out.println("정렬 전 데이터:");
        sorter.printElements();

        sorter.sortElements();

        System.out.println("정렬 후 데이터:");
        sorter.printElements();
    }
}

요약 및 분석

선택 정렬의 성능 특성은 다음과 같습니다:

  • 시간 복잡도: 버블 정렬과 마찬가지로 최악, 평균, 최선의 경우 모두 O(N2)의 시간 복잡도를 가집니다. 이는 중첩 반복문으로 인해 모든 요소 쌍을 비교해야 하기 때문입니다.
  • 비교 횟수: 총 N*(N-1)/2 번의 비교가 발생하여 버블 정렬과 동일합니다.
  • 교환 횟수: 각 패스마다 최대 한 번의 교환만 발생하므로, 총 N-1번의 교환이 발생합니다. 이는 버블 정렬에 비해 교환 횟수가 현저히 적다는 장점이 있습니다.

교환 비용이 비교 비용보다 높은 환경(예: 데이터 레코드가 크고 복잡할 경우)에서는 선택 정렬이 버블 정렬보다 더 효율적일 수 있습니다. 하지만 여전히 N2의 시간 복잡도를 가지므로 대규모 데이터셋에는 적합하지 않습니다.

삽입 정렬 (Insertion Sort)

원리

삽입 정렬은 배열의 요소를 하나씩 꺼내어 이미 정렬된 부분 배열의 올바른 위치에 '삽입'하면서 정렬하는 알고리즘입니다. 마치 손으로 카드 패를 정렬하는 방식과 유사합니다. 부분적으로 정렬된 배열을 확장해 나가는 방식으로 작동하며, 데이터가 거의 정렬되어 있을 때 매우 효율적입니다.

  1. 배열의 첫 번째 요소는 이미 정렬되어 있다고 간주합니다. (크기가 1인 정렬된 부분 배열)
  2. 두 번째 요소부터 시작하여, 각 요소를 정렬된 부분 배열에 적절한 위치에 삽입합니다.
  3. 삽입할 요소를 현재 위치에서 '빼낸' 후, 정렬된 부분 배열에서 해당 요소보다 큰 요소들을 한 칸씩 뒤로 밀어냅니다.
  4. 이동이 끝난 후 생긴 빈자리에 '빼낸' 요소를 삽입합니다.
  5. 이 과정을 배열의 모든 요소에 대해 반복하면, 전체 배열이 정렬됩니다.

예시

배열 [7, 6, 9, 8, 5, 1]을 오름차순으로 정렬하는 과정을 살펴보겠습니다.

  • 초기 상태: [7, 6, 9, 8, 5, 1] (첫 번째 요소 7은 정렬된 것으로 간주)
  • 두 번째 요소 (6) 삽입:
    • 6을 선택합니다. 정렬된 부분: [7]
    • 6 < 7 이므로 7을 한 칸 뒤로 밀고, 6을 앞자리에 삽입합니다.
    • 결과: [6, 7, 9, 8, 5, 1]
  • 세 번째 요소 (9) 삽입:
    • 9를 선택합니다. 정렬된 부분: [6, 7]
    • 9는 7보다 크므로, 제자리에 유지됩니다.
    • 결과: [6, 7, 9, 8, 5, 1]
  • 네 번째 요소 (8) 삽입:
    • 8을 선택합니다. 정렬된 부분: [6, 7, 9]
    • 8 < 9 이므로 9를 한 칸 뒤로 밀고, 8을 9의 앞자리에 삽입합니다.
    • 결과: [6, 7, 8, 9, 5, 1]
  • 다섯 번째 요소 (5) 삽입:
    • 5를 선택합니다. 정렬된 부분: [6, 7, 8, 9]
    • 5 < 9, 5 < 8, 5 < 7, 5 < 6 이므로 모든 요소를 뒤로 밀고, 5를 맨 앞에 삽입합니다.
    • 결과: [5, 6, 7, 8, 9, 1]
  • 여섯 번째 요소 (1) 삽입:
    • 1을 선택합니다. 정렬된 부분: [5, 6, 7, 8, 9]
    • 1은 5, 6, 7, 8, 9 모두보다 작으므로 모든 요소를 뒤로 밀고, 1을 맨 앞에 삽입합니다.
    • 결과: [1, 5, 6, 7, 8, 9]
  • 최종 정렬 결과: [1, 5, 6, 7, 8, 9]

구현 분석

삽입 정렬은 바깥쪽 반복문(currIndex)이 두 번째 요소부터 배열의 끝까지 순회합니다. 각 currIndex에서 현재 요소를 임시 변수(keyToInsert)에 저장하고, currIndex - 1 위치부터 시작하는 안쪽 반복문(shiftIndex)을 사용하여 정렬된 부분 배열을 역방향으로 탐색합니다. keyToInsert보다 큰 요소들은 한 칸씩 오른쪽으로 이동(시프트)시켜 빈 공간을 만듭니다. 이 과정은 keyToInsert보다 작거나 같은 요소를 만나거나 배열의 시작점에 도달할 때까지 계속됩니다. 마지막으로, 적절한 위치에 keyToInsert를 삽입합니다.

코드 구현


class InsertionSorter {
    private int[] dataArray;
    private int arrLength;

    public InsertionSorter(int[] inputArr) {
        this.dataArray = inputArr;
        this.arrLength = inputArr.length;
    }

    public void printElements() {
        for (int element : dataArray) {
            System.out.print(element + " ");
        }
        System.out.println();
    }

    public void sortElements() {
        // 두 번째 요소부터 시작하여 배열 끝까지 반복
        for (int currIndex = 1; currIndex < arrLength; currIndex++) {
            int keyToInsert = dataArray[currIndex]; // 현재 삽입할 요소
            int shiftIndex = currIndex - 1;       // 정렬된 부분 배열의 마지막 인덱스

            // keyToInsert보다 큰 요소들을 오른쪽으로 한 칸씩 이동
            while (shiftIndex >= 0 && dataArray[shiftIndex] > keyToInsert) {
                dataArray[shiftIndex + 1] = dataArray[shiftIndex];
                shiftIndex--;
            }
            // 적절한 위치에 keyToInsert 삽입
            dataArray[shiftIndex + 1] = keyToInsert;
        }
    }

    public static void main(String[] args) {
        int[] numbers = {38, 65, 97, 76, 13, 27, 49};
        InsertionSorter sorter = new InsertionSorter(numbers);

        System.out.println("정렬 전 데이터:");
        sorter.printElements();

        sorter.sortElements();

        System.out.println("정렬 후 데이터:");
        sorter.printElements();
    }
}

요약 및 분석

삽입 정렬의 성능 특성은 다음과 같습니다:

  • 시간 복잡도:
    • 최악의 경우: 배열이 역순으로 정렬되어 있을 때, 각 요소를 삽입하기 위해 모든 이전 요소와 비교하고 이동해야 하므로 O(N2)의 시간 복잡도를 가집니다.
    • 평균적인 경우: O(N2)의 시간 복잡도를 가집니다.
    • 최선의 경우: 배열이 이미 정렬되어 있을 때, 각 요소를 한 번만 비교하고 이동할 필요가 없으므로 O(N)의 시간 복잡도를 가집니다. 이는 삽입 정렬의 큰 장점 중 하나입니다.
  • 비교 횟수: 최악의 경우 N*(N-1)/2 번의 비교가 발생하지만, 최선의 경우 N-1번의 비교만 발생합니다.
  • 이동 횟수: 최악의 경우 N*(N-1)/2 번의 요소 이동이 발생할 수 있습니다. 교환(swap) 대신 이동(shift)이 발생하며, 이동은 일반적으로 교환보다 오버헤드가 적습니다.

삽입 정렬은 N2 알고리즘 중에서는 상대적으로 빠른 편에 속합니다. 특히 데이터가 거의 정렬되어 있거나, 배열의 크기가 작을 때 뛰어난 성능을 보입니다. 이러한 특성 때문에 하이브리드 정렬 알고리즘(예: 팀정렬, 인트로정렬)의 작은 부분 배열 정렬 단계에서 활용되기도 합니다.

태그: java Sorting Algorithms Bubble Sort Selection Sort Insertion Sort

9월 29일 00:30에 게시됨

인기 태그

©2026 괴물 클럽