Egbert Lin's Blog

“Life is not a race, but a journey to be savoured each step of the way” by Brian Dyson

Data Structures - Bubble Sort

Posted on Edited on In Disqus:

Basic programming - Bubble Sort

Approach:

Compare with each elements in the range [0: n] and if vector[i] is bigger than vector[i + 1], call swap().

n is the number of elements in vector and it will descending every loop. It means the biggest element moves to the right side.
And, there are one suitation that break the loop earily than expected. If no any elements call swap(), it represented all of the elements in vector are sorted.

Time complexity:
  • Best Case：Ο(n)
  • Worst Case：Ο(n2)
  • Average Case：Ο(n2)

    • P.S. If input is sorted, it still checks once without calling swap()

    Space complexity: O(1)

    Stable/Unstable: Stable

    Source code

    Version 1

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    #include <iostream>
    #include <vector>

    using namespace std;

    void print(vector<int>& v){
        for(int i = 0; i < v.size(); ++i){
            cout << v[i] << " ";
        }
        cout << endl;
    };

    void swap(int& l, int& r){
      int temp = l;
      l = r;
      r = temp;
    };

    void bubbleSort(vector<int>& v){
      int n = v.size();
      int count = n;
      while(n > 0 && count > 0){
          count = 0;
          for(int i = 0; i < n - 1; ++i){
              if(v[i] > v[i + 1]){
                  swap(v[i], v[i + 1]);
                  count ++;
              }
          }
          --n;
          print(v);
      }
    };

    int main()
    {
        vector<int> input = {84,17,32,53,91,13,33,61,44,43};
        bubbleSort(input);
        
        cout << "Final answer:" << endl;
        print(input);
        
        return 0;
    }