정렬 알고리즘 - 버블 정렬, 선택 정렬, 삽입 정렬

정렬 알고리즘은 데이터를 정렬하는 가장 기초적인 알고리즘 중 하나로, 프로그래밍 입문자부터 고급 개발자까지 모두에게 중요한 주제입니다. 오늘은 대표적인 세 가지 정렬 알고리즘인 버블 정렬, 선택 정렬, 삽입 정렬을 살펴보고 각 알고리즘의 Java와 C 예제를 함께 제공하겠습니다.

1. 버블 정렬 (Bubble Sort)

버블 정렬은 두 인접한 원소를 비교하여 정렬하는 방식으로, 가장 큰 원소가 배열의 끝으로 이동하는 것을 반복합니다. 이름처럼 거품이 위로 올라가는 것과 유사한 방식으로 작동합니다.

알고리즘 설명

• 인접한 두 원소를 비교하여 정렬되지 않은 경우 위치를 바꿉니다.
• 각 패스를 반복할 때마다 가장 큰 원소가 배열의 끝으로 이동합니다.
• 배열이 정렬될 때까지 이러한 과정을 반복합니다.

Java 예제 코드

public class BubbleSort {
    public static 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]) {
                    // Swap arr[j] and arr[j+1]
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        bubbleSort(arr);
        System.out.println("Sorted array: ");
        for (int value : arr) {
            System.out.print(value + " ");
        }
    }
}

C 예제 코드

#include <stdio.h>

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // Swap arr[j] and arr[j+1]
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);
    bubbleSort(arr, n);
    printf("Sorted array: \n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

2. 선택 정렬 (Selection Sort)

선택 정렬은 배열에서 가장 작은 원소를 선택하여 맨 앞의 원소와 교환하는 과정을 반복합니다. 이러한 방식을 통해 배열의 앞쪽부터 정렬이 완료됩니다.

알고리즘 설명

• 배열에서 가장 작은 원소를 찾고, 첫 번째 위치의 원소와 교환합니다.
• 다음으로 두 번째 위치부터 반복하여 정렬을 완료합니다.
• 시간 복잡도는 O(n^2)입니다.

Java 예제 코드

public class SelectionSort {
    public static void selectionSort(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;
                }
            }
            // Swap arr[minIndex] and arr[i]
            int temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 25, 12, 22, 11};
        selectionSort(arr);
        System.out.println("Sorted array: ");
        for (int value : arr) {
            System.out.print(value + " ");
        }
    }
}

C 예제 코드

#include <stdio.h>

void selectionSort(int arr[], int n) {
    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;
            }
        }
        // Swap arr[minIndex] and arr[i]
        int temp = arr[minIndex];
        arr[minIndex] = arr[i];
        arr[i] = temp;
    }
}

int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr[0]);
    selectionSort(arr, n);
    printf("Sorted array: \n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

3. 삽입 정렬 (Insertion Sort)

삽입 정렬은 정렬된 부분과 정렬되지 않은 부분으로 배열을 나누어, 정렬되지 않은 원소를 정렬된 부분에 삽입하는 방식으로 동작합니다. 카드를 정렬하는 방식과 유사합니다.

알고리즘 설명

• 배열의 첫 번째 원소는 이미 정렬된 것으로 간주합니다.
• 두 번째 원소부터 시작하여 정렬된 부분에 적절한 위치에 삽입합니다.
• 이러한 과정을 반복하여 배열 전체가 정렬될 때까지 진행합니다.

Java 예제 코드

public class InsertionSort {
    public static void insertionSort(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 = j - 1;
            }
            arr[j + 1] = key;
        }
    }

    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6};
        insertionSort(arr);
        System.out.println("Sorted array: ");
        for (int value : arr) {
            System.out.print(value + " ");
        }
    }
}

C 예제 코드

#include <stdio.h>

void insertionSort(int arr[], int n) {
    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 = j - 1;
        }
        arr[j + 1] = key;
    }
}

int main() {
    int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);
    insertionSort(arr, n);
    printf("Sorted array: \n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

결론

이번 글에서는 버블 정렬, 선택 정렬, 삽입 정렬에 대해 알아보았습니다. 이 세 가지 정렬 알고리즘은 이해하기 쉽고 구현이 간단하여 정렬 알고리즘의 기초를 다지는 데 매우 유용합니다. 각 알고리즘은 시간 복잡도가 O(n^2)로, 데이터 양이 많아질수록 비효율적이지만, 데이터가 적거나 정렬이 거의 된 경우에는 효과적으로 사용할 수 있습니다.