Bubble Sort

오랜만에 다시 알고리즘 책을 폈다. 한 2주만에 펴본것 같다?

빨리 목표한 부분까지는 다 이해를 해야지 라고 마음을 다잡지만 집중은 잘 안되고 스스로 부족한 부분만 보인다.

그럴때일수록 정신 차리고 집중해야 하니까 다시 집중을 해봐야겠다.

여튼 이번에는 못다한 정렬 알고리즘 중 Bubble Sort 거품 정렬을 정리해보려고 한다.

일단 Bubble Sort는 정렬 알고리즘을 구현할때 사실상 잘 사용하지 않는 알고리즘이다.

왜나하면 성능이 너무 구리다, 일단 시간 복잡도는 O(N^2)이기도 하거니와, 비교와 교환의 횟수가 너무 많다.

정렬해야할 데이터의 사이즈가 작으면서 갯수가 100개 미만이라면, 또 동시에 정렬 메소드가 제공되지 않는다면 고려해봄직 하겠으나 성능면에서 만족스러운 알고리즘은 아니다.

다만, 이전에 다뤄봤던 삽입정렬 그리고 선택정렬과 같이 비교적 수월하게 구현이 가능한 정렬 알고리즘이기에 알아볼 필요는 있다.

거품 정렬의 전략

거품 정렬은 인접한 배열의 요소를 비교 및 교환하면서 전체적으로는 대충 정렬을 하면서 가장 큰 값을 배열의 제일 뒤로 보내는걸 반복한다.

따라서 바깥쪽의 for문 loop가 다 돌아갈때마다 배열의 뒷쪽에는 큰값이 차례대로 정렬이 된다는 소리다.

또한 안정성도 보장이 되는데, 안정성이 뭐냐면 T(1) T(2) T(3) 이렇게 같은 값이 3개 있다고 할때 정렬이 완료된 후 T가 정렬전과 동일하게 순서대로 유지되는걸 말한다.

만약 정렬이 끝난 후 T(2) T(1) T(3) 이런식이라면, 이는 안정성이 없다는 의미다.

코드

void bubble_sort(int arr[], int length) {
    int t;
    
    for(int i = 0; i < length - 1; i++) {
        for(int j = 1; j < length - i; j++) {
            if(arr[j - 1] > arr[j]) {
                t = arr[j - 1];
                arr[j - 1] = arr[j];
                arr[j] = t;
            }
        }
    }
}

추가적으로 위 코드를 개선하려고 한다면, 이미 정렬이 완료가 된 상태인지를 확인한 다음 break를 통해서 loop를 탈출 시키면 된다.

이미 정렬이 다 되었는지는 어떻게 확인하느냐? 간단한데 바로 교환을 한번도 하지 않았다면 이미 정렬이 완료가 되었다는 소리다.

전체 코드

//
//  main.c
//  BubbleSort
//
//  Created by 박재현 on 2024/06/25.
//

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void print_array(int arr[], int length) {
    for(int i = 0; i < length; i++) {
        printf("%c ", arr[i]);
    }
    printf("\n\n");
}

void bubble_sort(int arr[], int length) {
    int t;
    
    for(int i = 0; i < length - 1; i++) {
        for(int j = 1; j < length - i; j++) {
            if(arr[j - 1] > arr[j]) {
                t = arr[j - 1];
                arr[j - 1] = arr[j];
                arr[j] = t;
            }
        }
    }
}

int main(int argc, const char * argv[]) {
    int *arr;
    int str_length;
    char *str = "TOLEARNSORTALGORITHM";
    
    str_length = (int)strlen(str);
    arr = (int *)malloc(sizeof(int) * str_length);
    
    for(int i = 0; i < str_length; i++) {
        arr[i] = str[i];
    }
    
    printf("Before Bubble Sorting.\n");
    print_array(arr, str_length);
    
    bubble_sort(arr, str_length);
    printf("After Bubble Sorting.\n");
    print_array(arr, str_length);
    
    return 0;
}

실행 결과