Sorting algorithm implementation and switch-case alternative in Python
26 October 2013By Bhavyanshu Parasher
In this i am going to show you sorting algorithms ported to python. If you have done them in c/c++/java then you must be aware of these basic sorting algos.
The first step is to create a menu with options like selection sort, bubble sort, insertion sort, merge sort, quick sort etc.
The second step would be to take user input as an option and the control would pass to that particular chosen sort based on the input & call the appropriate sorting function.
Before calling we should request some array input from the user which he/she would like to sort and pass them as arguments to the sorting function during function call.
Since python does not have switch statement (Yeah! you might be thinking that sucks but wait, read ahead!).
It was proposed and rejected in PEP 3103. Basicallly some people believe that having switch statement is just bad design and we should always try to replace switch cases.
Why bad design?
Because having switch statements lead to duplicacy of code. It is often known as “SwitchSmell”. Typically, similar switch statements are scattered throughout a program. If you add or remove a clause in one switch, you often have to find and repair the others too.
Polymorphism gives you many advantages. The biggest gain occurs when the same set of conditions appears in many places in the program. If you want to add a new type, you have to find and update all of the conditionals. But with subclasses, you just create a new subclass and provide the appropriate methods. Clients of the class don’t need to know about the subclasses, which reduces the dependencies in your system and makes it easier to update.
Anyway, in python either we can implement polymorphism or we can use associative arrays also known as dictionaries. These provide one-to-one matching of a key-value pair. In this particular example we will be using dictionaries instead of polymorphism. Then we will port this code to use the concept of polymorphism. That’s it for the theory of python. Let’s begin some coding.
In this we will be looking at the following sorting algos :
First thing to do would be to define main and create a function that builds array/list
Basic idea behind bubble sort : easy to implement but cannot be used for large or medium sized datasets. Now we will apply it on a small array of integers
Theory: The bubble sort works by passing sequentially over a list, comparing each value to the one immediately after it. If the first value is greater than the second, their positions are switched. Over a number of passes, at most equal to the number of elements in the list, all of the values drift into their correct positions (large values “bubble” rapidly toward the end, pushing others down around them). Because each pass finds the maximum item and puts it at the end, the portion of the list to be sorted can be reduced at each pass. A boolean variable is used to track whether any changes have been made in the current pass; when a pass completes without changing anything, the algorithm exits.
In this we first find the smallest element in the array and exchange it with the element in the first position. In simple terms we shift the smallest element to first positions, then find the second smallest element and exchange with the element on the second position and so on.
This is also inefficient for large arrays.
Application: Its primary purpose is for when writing data is very expensive (slow) when compared to reading, eg writing to flash memory or EEPROM. No other sorting algorithm has less data movement.
The basic idea is to split the collection into smaller groups by halving it until the groups only have one element or no elements (which are both entirely sorted groups). Then merge the groups back together so that their elements are in order. This is how the algorithm gets its “divide and conquer” description.
1.Choose any element of the array to be the pivot.
2.Divide all other elements (except the pivot) into two partitions.
All elements less than the pivot must be in the first partition.
All elements greater than the pivot must be in the second partition.
3.Use recursion to sort both partitions.
4.Join the first sorted partition, the pivot, and the second sorted partition.
It involves moving one element at a time into the previous sorted part of the array. Its simplicity, low overhead, good locality of reference and efficiency make it a good choice in two cases (i) small n (where n is the total number of elements in the list), (ii) as the final finishing-off algorithm for O(n logn) algorithms such as mergesort and quicksort.