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.
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.