Bubble and Straight Insertion Sort in Python

Thu 18 January 2007 by Thejaswi Puthraya

Bubble and Straight Insertion Sort in Python

Recently I got my hand on the book Introduction to the Design and Analysis of Algorithms (http://worldcat.org/oclc/2463560) by S.E.Goodman and S.T.Hedetniemi published by the Mc-Graw Hill Company. The book is out of print now and I found it in a library. The book had never been lent and I was the lucky first person to borrow it (20 years after it had been bought). This highlights the negligience of libraries and reading habits in Hyderabad (India). Half way through the book (after having read the various sorting algorithms) I decided to give my programming skills in Python a test. I first started out writing the bubble sort program. This was probably the easiest sorting algorithm to code. Then I wrote the straight insertion sort, a better performer than the bubble sort. Though the quick sort algorithm is the most efficient algorithm, I haven't been able to code it (as of now). I am presently working on it and the program might be out soon.

Bubble Sort

for i in xrange(len(a)):
    for j in xrange(i+1,len(a)):
        if a[i]>a[j]:
           tmp = a[i]
           a[i] = a[j]
           a[j] = tmp

Here "a" is the list of integers to be sorted. I used the random module to generate the random data for the list.The funda of the bubble sort is to compare a particular element with all the other elements in the list. Whenever it finds a number lower than it, it swaps places with the number and the comparison goes on. Since every element (say for a N-length array) must be compared with N-1 elements and this comparison goes on for all the N elements, this algorithm is usually not preferred. It is taught in colleges and schools because it is the easiest to realise.

Straight Insertion Sort

for j in xrange(1,len(a)):
  k=a[j]
  l=j-1
  while k <>=0:
    a[l+1]=a[l]
    l=l-1
    a[l+1]=k

We move along a fixed direction of the unsorted list and try to locate the correct location of the number ie until all the sorted numbers with smaller values come before it and all those with larger values come after it:

Unsorted List --> 27 412 71 81 59 13
Iteration 0: Unsorted 412 71 81 59 13    Sorted 27
Iteration 1: Unsorted 71 81 59 13        Sorted 27 412
Iteration 2: Unsorted 81 59 13           Sorted 27 71 412
Iteration 3: Unsorted 59 13              Sorted 27 71 81
Iteration 4: Unsorted 13                 Sorted 27 59 71 81 412
Iteration 5: Unsorted                    Sorted 13 27 59 71 81 412

Then I wrote the main program ie generation of random data, sorting and verifying which is better of the two algorithms.

Generation of Random Data

import random
a = []
matdim = input('Enter the number of elements for the array: ')
for i in xrange(matdim):
   a.append(random.randint(1,10000))

Next we check which sorting program is the best (amongst the two)

Results of Bubble Sort and Straight Insertion Sort:

Number of Elements          10          50           100            200               500            1000         5000
Bubble Sort                 0.0548      0.951        4.0509         13.540            127.595        379.938      8212.631
Straight Insertion Sort     0.0381      0.725        2.723          10.940            111.083        303.351      6697.399
All times in milliseconds

The data has been rounded off to the third place of decimal. Note: The data has been obtained using Python 2.4.4 on an AMD Athlon XP Machine 2.4GHz running Fedora Core 6 with kernel 2.6.18-1.2798.fc6. The mileage may vary for tests on other machines.

Checking: The execution profile of the sorting program has been checked using the time module. There is a better way of determining the execution profile using the timeit module. I decided not to use it since I just wanted an approximate time of execution. The primary objective was to show that Straight Insertion Sort is better than Bubble Sort.

Last Note: As we can see from the table Straight Insertion Sort is faster compared to Bubble Sort. Quick Sort is a lot faster than either of the two sorts but it is comparitively more complex to code. I am presently breaking my head over how to code the Quick Sort Algorithm in Python (without using stacks). Hopefully should be out with it in a couple of weeks.