BubbleSort (버블정렬)

버블정렬은 많은 사람들이 알 것이라 생각한다.

 

배열이 주어졌을 때, 앞에서부터 하나하나 비교해서 정렬하는 방식이다.

 

하나하나 비교해야하기 때문에 시간이 오래 걸린다는 단점이 있지만, (O(n^2))

 

정렬해야 할 것이 별로 없을 때는 빠르다는 특징이 있다.

 

 

코드)

#include <iostream>


void BubbleSort(int* arr, int size);
void PrintArr(int* arr, int size);

int main(void) {
    {
      int arr[] = {5, 1, 4, 2, 3};
      int size = sizeof(arr) / sizeof(int);

      BubbleSort(arr, size);
    }
  return 0;
}

void BubbleSort(int* arr, int size) {
  for (int i = 0; i < size - 1; i++) {
    for (int j = i + 1; j < size; j++) {
      if (arr[i] > arr[j]) {
        std::swap(arr[i], arr[j]);
      }
    }
    PrintArr(arr, size);
  }
}

void PrintArr(int* arr, int size) {
  for (int i = 0; i < size; i++) {
    std::cout << arr[i] << " ";
  }
  std::cout << '\n';
}

 

코드도 간단하다. 이중 for문을 이용하여 앞에서부터 하나하나 정렬해주면 된다.

 

 

 

 

안정성)

앞의 선택정렬에서도 살펴본 것처럼, 버블정렬의 안정성에 대해서도 알아보자.

 

#include <iostream>

 struct Element {
   int key;
   char value;
 };
 
void E_BubbleSort(Element* arr, int size);
void E_PrintArr(Element* arr, int size);

 
 int main(void){

    Element Earr[] = {{3, 'a'}, {2, 'a'}, {2, 'c'}, {3, 'c'}, {4, 'd'}};
    int size = sizeof(Earr) / sizeof(Earr[0]);
    E_BubbleSort(Earr, size);
    
    return 0;

 }
 
 void E_BubbleSort(Element* arr, int size) {
  for (int i = 0; i < size - 1; i++) {
    for (int j = i + 1; j < size; j++) {
      if (arr[i].key > arr[j].key) {
        std::swap(arr[i], arr[j]);
      }
    }
    E_PrintArr(arr, size);
  }
}

void E_PrintArr(Element* arr, int size) {
  for (int i = 0; i < size; i++) {
    std::cout << arr[i].key << " , " << arr[i].value << "\n";
  }
}

 

 

위 코드를 실행시켰을 때 나오는 결과이다.

 

key 값이 정렬되면서 value 값도 따라갔는데,

 

처음 설정해준 배열에서의 value 값의 순서와 정렬이 완료되었을 때 value 값의 순서가 같다.

 

버블 정렬은 앞에서부터 하나하나 key 값을 비교하기 때문에, key 값이 같을 경우 순서를 바꾸지 않는 안정적인 정렬이라고 볼 수 있다.