Sorting Algorithms - Python Implementations
Well, I have to admit, I don’t know how to begin 1/2 the posts on topics like these. Let me just point out that I was trying to arrange a list of words in dictionary order without using the sort() method available for lists in Python and since I am a lazy what-not, I only wrote a small bubblesort implementation the crux of which was:
alphas = string.uppercase
alpha_dict = {}
for i in range (1, 27):
alpha_dict[alphas[i-1]] = i
So, I created a dictionary which went like:
{”A”: 1, “B”: 2, “C”: 3 ………, “Z”: 26}
One of the words in the list which had to be sorted was “BABELFISH”. Using the dictionary, I created a list consisting of numbers corresponding to the letters which composed the word.
for char in word:
nums_list.append(str(alpha_dict[char]))
num = int(("").join(nums_list))
Then comes the actual bubblesort implementation. And when OpenBySource dissed me for sticking to something so inefficient, I decided I would go and read as much about sorting as I could and well, here is what I have learned.
First, the sorting algorithm that I always knew, BubbleSort. The algorithm is pretty simple. Begin at the first element, if this element is greater than the next element, swap their positions and proceed to the next element. This is how it is supposed to go. Here is a Python implementation:
#Author: Shriphani Palakodety
#Bubble Sort Algorithm Implementationimport copy
def sorter(num_list):
new_num_list = copy.copy(num_list)
n = 0
for i in range(len(num_list)-1):
if num_list[i] < num_list[i+1]:
continue
else:
num_list[i+1] = new_num_list[i]
num_list[i] = new_num_list[i+1]
new_num_list = copy.copy(num_list)
n += 1
return num_list, n
num_list = [2,7,1,5,8,6]
def checker(num_list):
while True:
sacred_tuple = sorter(num_list)
if sacred_tuple[1] != 0:
num_list = sacred_tuple[0]
else:
return sacred_tuple[0]
print checker(num_list)
I can see the question coming up ( if it isn’t, please don’t bother telling me ). “What is that checker() doing there ?”. The thing is that you can always keep running the sorter function. The checker stops the sorting process run by the sorter function when no sorting is performed when sorter(list_name) is run.
The next algorithm I encountered struck me as stupid. Every single kid must have used it. I am ashamed of myself to even have written this thing. Anyway, it is called the “Selection Sort” algorithm. You pick the least valued term in a list, assign it to the first position, from the remaining elements, pick the smallest number, put it at the second position and so on. Here is what I wrote ( and what every 5 year old out there could have written ):
#Author: Shriphani Palakodety
def selSort(list_name):
sorted_list = []
while True:
least_number = min(list_name)
sorted_list.append(least_number)
list_name.remove(least_number)
if len(list_name) == 0:
return sorted_list
break
else:
continue
unsorted_list = [2, 1, 8, 10, 12, 9, 42, 21]
print selSort(unsorted_list)
Actually the code displayed above is a cross between what is known as the “Insertion Sort” algorithm and the “Selection Sort” algorithm. In the insertion sort algorithm, the sorted list is built one element at a time.
The next algorithm I am going to cover is the “Merge Sort” algorithm. This algorithm works by diving a list into a number of sublists and then merging them back to get a sorted list.
Here is the merge function:
left_index, right_index = 0, 0
result = []
while left_index < len(left) and right_index < len(right):
if left[left_index] < right[right_index]:
result.append(left[left_index])
left_index = left_index + 1
else:
result.append(right[right_index])
right_index = right_index + 1
result += left[i:]
result += right[j:]
return result
And of course, now comes the splitter() function. I am too tired to explain wtf is going on.
if len(list_name) < 2:
return list
else:
middle = len(list_name) / 2
left = splitter(list_name[:middle])
right = splitter(list_name[middle:])
return merger(left, right)
Happy Coding.
0 comments
Kick things off by filling out the form below.
Leave a Comment