Page 1 of 1

Understanding Bubblesort

#1 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10387
  • View blog
  • Posts: 38,440
  • Joined: 27-December 08

Posted 10 June 2010 - 06:40 AM

Bubblesort is probably the most basic and inefficient sorting algorithm, and something no one would probably do in real life. Basically, the algorithm iterates through the collection, examining two consecutive elements at a time starting at array[0] and array[1], swapping them if necessary. It then proceeds to elements 1 and 2 in the array, all the way to array[length-2] and array[length-1]. The algorithm then starts all over at the beggining. So when does the algorithm stop? The termination condition is when an entire iteration is made without swapping any elements. When it comes down to the efficiency, Bubblesort has a time complexity of O(n^2), and takes way more time than its quadratic counterparts Insertion and Selection Sorts.

So now that we understand how Bubblesort works, let's take a look at some pseudo-code.
bubblesort(array x){
    boolean sorted <-- true
    do{
        for i <-- 0 to x.length, incrementing i = i+1
            if(x[i] > x[i+1]){
                swap(x[i], x[i+1])
                sorted <-- false
            }
        end FOR
    }while(NOT sorted)
}



One thing I notice right off the bat is that on every swap, we also modify the value of a boolean. So if we make 1000 swaps, we take another 1000 steps to deal with our boolean. On top of that, our inner for loop takes linear time, and the outer loop takes approximately linear time as well. So n*n --> O(n^2).

Is This A Good Question/Topic? 0
  • +

Replies To: Understanding Bubblesort

#2 AdamSpeight2008  Icon User is offline

  • MrCupOfT
  • member icon


Reputation: 2241
  • View blog
  • Posts: 9,412
  • Joined: 29-May 08

Posted 10 June 2010 - 06:49 AM

Bubble Sort isn't n^2 but n * (n Log 2)

For example
For Outer = 0 To n-2
 For Inner = Outer + 1 To n-1
  If Element(Outer) > Element(Inner) Then Swap Elements
 Next Inner
Next Outer

Was This Post Helpful? 1
  • +
  • -

#3 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10387
  • View blog
  • Posts: 38,440
  • Joined: 27-December 08

Posted 10 June 2010 - 06:54 AM

Log(2) is a constant, so for the purposes of Big-O, I drop the constant. However, for all practicality, that would explain the drastic difference in runtime for Bubblesort vs. other sorting algorithms.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1