처음하시는 분들을 위한 C언어 기초강의 시즌2 - 36 [정렬 알고리즘(버블 정렬)]

제 36강) 정렬 알고리즘 - 버블 정렬

오늘은 정렬 알고리즘의 첫 시간으로 "버블 정렬"에 대해서 알아봅니다.

기본적으로 버블 정렬은 배열에서 사용합니다.

 

버블 정렬이란

 

(사진 출처: 위키 백과 - 거품 정렬)

버블 정렬은 구현하기가 가장 쉽지만 성능을 기대하기 어려운 정렬입니다.

(실질적으로 안쓰는 정렬 중 하나)

버블 정렬은 해당 인덱스와 그 다음 인덱스와의 크기를 비교하여 바꾸는 정렬로 결과적으로 한 사이클이 지날때 마다 가장 큰 인덱스의 값은 맨 뒤로 옮겨집니다.

위의 그림에서 첫 번째 사이클에서 이미 가장 큰 수인 11이 맨 뒤로 옮겨집니다.

그렇기 때문에 두 번째 사이클에서는 11을 제외한 4개의 숫자를 가지고 다시 정렬을 합니다.

그렇기 때문에 버블 정렬의 비교 횟수는 T(n) = n(n - 1) / 2 를 성립합니다.

그러므로 버블 정렬의 시간복잡도는 O(n(n - 1) / 2) = O(n^2) 가 됩니다.

 

 

정렬명	시간 복잡도	메모리 사용
버블 정렬	O(n^2)	n

이때 메모리는 기존의 n만큼 할당된 배열 그대로 사용하기 때문에 그대로 n만큼의 메모리를 사용합니다.

 

 

위의 영상은 버블정렬을 시각적인 춤으로 표현한 좋은 영상입니다.

꼭 보세요.

 

버블 정렬 구현

이제 버블 정렬을 구현하여 봅시다.

#include <stdio.h>
 
void bubbleSort(int* arr, int length)
{
    int temp;
    for (int i = 0; i < length; i++)
    {
        for (int j = 0; j <= length - i; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}
 
void printArray(int* arr, int length)
{
    printf("arr: ");
    for (int i = 0; i < length; i++)
    {
        printf("%d", arr[i]);
        if (i != length - 1)
            printf(", ");
    }
    printf("\n");
}
 
int main()
{
    int arr[] = { 9, 11, 8, 2, 3 };
    int size = sizeof(arr) / sizeof(int);
    
    printArray(arr, size);
    bubbleSort(arr, size);
    printArray(arr, size);
 
    return 0;
}

버블 정렬 부분은 3번 ~ 18번줄 입니다.

첫번째 for문은 배열의 크기 만큼 반복을 합니다.(인덱스의 개수만큼)

두번째 for문은 매 사이클마다 최대로 큰 수가 저장되어 정렬된 부분(i) 만큼을 제외하고 정렬을 합니다.

 

어때요 쉽죠?

 

 

다음 시간에는

다음 시간에는 선택정렬에 대해서 알아봅시다.