기본 정렬 알고리즘 알아보기

정렬(sorting)

주어진 데이터 집합을 특정 순서(오름차순, 내림차순 등)에 따라 배열하는 작업

 

정렬의 목표 = 데이터의 효율적인 관리

- 검색 속도 향상

: 정렬된 데이터에서 이진 탐색과 같은 알고리즘을 사용하면 검색 시간이 O(log n)으로 줄어듦

- 데이터 분석 용이

- 데이터 병합 효율적

-----🐢

정렬 알고리즘들을 알아보기 전에 먼저 시간 복잡도에 대해 알아볼게요!

시간 복잡도는 알고리즘이 실행되는 데 걸리는 시간을 나타내는 지표로, 입력 데이터의 크기(n)에 따른 알고리즘의 효율성을 비교하는 것을 목적으로 두고 있어요. 주 표기법은 Big-O 표기법으로 최악의 경우를 기준으로 실행 시간을 표기합니다.

----🐢-

이제 시간 복잡도에 따라 정렬 알고리즘들을 분류해볼게요

먼저 시간 복잡도가 O(n²)인 정렬 알고리즘들입니다.

 

버블 정렬(Bubble Sort)

시간 복잡도 : O(n²); 최악, 평균 / O(n); 최선

인접한 두 요소를 비교하여 정렬이 안 되어 있으면 교환하는 방식으로 리스트의 끝까지 반복

각 루프마다 가장 큰 값이 끝으로 이동

  

코드 예시:

#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]) {
                // 두 요소 교환
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr)/sizeof(arr[0]);
    printf("정렬 전 배열: \n");
    printArray(arr, n);

    bubbleSort(arr, n);
    
    printf("정렬 후 배열: \n");
    printArray(arr, n);
    return 0;
}

 

삽입 정렬(Insertion Sort)

시간 복잡도 : O(n²); 최악, 평균 / O(n); 최선

리스트의 요소를 하나씩 검사하며, 해당 요소를 올바른 위치에 삽입

코드 예시:

#include <stdio.h>

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        
        // key보다 큰 요소를 한 칸 뒤로 이동
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("정렬 전 배열: \n");
    printArray(arr, n);

    insertionSort(arr, n);

    printf("정렬 후 배열: \n");
    printArray(arr, n);

    return 0;
}

 

선택 정렬(Selection Sort)

시간 복잡도 : O(n²); 최악, 최선, 평균

리스트에서 가장 작은 값을 찾아서 첫 번째 요소와 교환하는 과정을 반복하는 방식

코드 예시:

#include <stdio.h>

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {
        int min_idx = i;
        for (int j = i+1; j < n; j++)
            if (arr[j] < arr[min_idx])
                min_idx = j;

        // 최소값을 첫 번째 요소와 교환
        int temp = arr[min_idx];
        arr[min_idx] = arr[i];
        arr[i] = temp;
    }
}

void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr)/sizeof(arr[0]);
    
    printf("정렬 전 배열: \n");
    printArray(arr, n);
   
    selectionSort(arr, n);
    
    printf("정렬 후 배열: \n");
    printArray(arr, n);
    
    return 0;
}

 

 

퀵 정렬(Quick sort)

시간 복잡도: O(n²); 최악 / O(n log n); 평균

분할 정복(Divide and Conquer) 기법을 사용하여 리스트를 정렬하는 알고리즘

 

동작 원리

1. 피벗(Pivot) 선택 

리스트에서 하나의 요소를 선택(피벗)

2. 분할(Divide)

피벗을 기준으로 리스트를 두 개의 하위 리스트로 나눔.

피벗보다 작은 값들은 피벗의 왼쪽에, 피벗보다 큰 값들은 피벗의 오른쪽에 배치

3. 정복(Conquer)

각 하위 리스트에 대해 재귀적으로 퀵 정렬을 반복

4. 결합(Combine)

재귀가 끝나면 각 하위 리스트는 정렬된 상태이며, 전체 리스트도 정렬된 상태

 

 

코드 예시:

#include <stdio.h>

// 두 요소의 값을 교환하는 함수
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 분할 함수: 피벗을 기준으로 리스트를 나누는 함수
int partition(int arr[], int low, int high) {
    int pivot = arr[high]; // 피벗을 리스트의 마지막 요소로 선택
    int i = (low - 1); // 작은 값들을 저장할 인덱스

    for (int j = low; j <= high - 1; j++) {
        if (arr[j] < pivot) { // 현재 요소가 피벗보다 작으면
            i++; // 작은 값 영역을 확장하고
            swap(&arr[i], &arr[j]); // 해당 요소를 작은 값 영역으로 이동
        }
    }
    // 피벗을 중앙으로 이동
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

// 퀵 정렬 함수
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        // 피벗을 기준으로 리스트를 나누고 피벗의 위치를 반환
        int pi = partition(arr, low, high);

        // 피벗을 기준으로 나뉜 리스트를 재귀적으로 정렬
        quickSort(arr, low, pi - 1);  // 왼쪽 부분 정렬
        quickSort(arr, pi + 1, high); // 오른쪽 부분 정렬
    }
}

// 배열 출력 함수
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

// 메인 함수
int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("정렬 전 배열: \n");
    printArray(arr, n);

    quickSort(arr, 0, n - 1);

    printf("정렬 후 배열: \n");
    printArray(arr, n);
    return 0;
}

---🐢--

다음으로 시간 복잡도가 O(n log n)인 정렬 알고리즘을 알아볼게요!

 

합병(병합) 정렬(Merge sort)

시간 복잡도: O(n log n); 최악, 최선, 평균 동일

분할 정복(divide and conquer) 기법 사용

입력 리스트를 반으로 계속 나누어, 리스트 크기가 1이 될 때까지 나누고, 그 후에 다시 병합하면서 정렬된 배열을 만듦

 

코드 예시:

#include <stdio.h>

void merge(int arr[], int l, int m, int r) {
    int i, j, k;
    int n1 = m - l + 1;
    int n2 = r - m;

    int L[n1], R[n2]; // 임시 배열을 생성하여 왼쪽과 오른쪽 배열을 저장

    // 데이터를 왼쪽과 오른쪽 배열에 복사
    for (i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];

    i = 0;
    j = 0;
    k = l;

    // 왼쪽과 오른쪽 배열에서 더 작은 값을 원래 배열로 병합
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    // 남은 데이터 병합
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

void mergeSort(int arr[], int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2;

        // 왼쪽, 오른쪽 부분 배열을 각각 재귀적으로 정렬
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);

        // 정렬된 두 부분 배열을 병합
        merge(arr, l, m, r);
    }
}

void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int arr_size = sizeof(arr) / sizeof(arr[0]);

    printf("정렬 전 배열: \n");
    printArray(arr, arr_size);

    mergeSort(arr, 0, arr_size - 1);

    printf("정렬 후 배열: \n");
    printArray(arr, arr_size);

    return 0;
}