I have developed a rabid interest in improving algorithms! Can we improve them? Will we write more code than current solutions and will they run faster? Can we look at the problem from a different angle to inspire new methods and solutions?
def bubble_sort(list) for i in range(len(items)): for j in range(len(items)-1-i): if items[j] > items[j+1]: items[j], items[j+1] = items[j+1], items[j] return list
While watching "The Secret Rules of Modern Living - Algorithms" I became inspired by their visual representation of the bubble sort. (See Video Above) The man went up an array or list of items while organizing the blocks from tallest to shortest. I thought to myself, "What if, on every iteration, the computer ascended the list with the highest value and then descended the list with the lowest value?" Applying this concept allows us to make three assumptions:
You can see how it will only require one last pass for all three of those integers to be placed in their proper place. Ascending will switch 5 and 3 while descending will switch the 3, and 4. Voila!
Original List: [7,6,4,5,3,2,1] First Full Pass: [1,6,4,5,3,2,7] Second Full Pass: [1,2,4,5,3,6,7]
While not necessarily an improvement on bubble_sort's worst case scenario: O(n^2), it does appear to improve speeds on smaller lists. Here was my original attempt at writing my own Bubble Sort:
def danny_bub(list): length = len(list) - 1 sorted = False counter = 0 while not sorted: sorted = True for i in range(counter, length - 1, 1): if list[i] > list[i + 1]: list[i], list[i+1] = list[i+1], list[i] sorted = False if(not sorted): for j in range(length, counter, -1): if list[j] < list[j - 1]: list[j], list[j-1] = list[j-1], list[j] counter += 1 length -= 1 print list
After seeing how long and complicated my original attempt was, I simply had to trim the fat and break it down to it's bare essentials:
def danny_bub2(list): for i in range((len(list))//2): for j in range(i, (len(list) - 1) - i): if list[j] > list[j + 1]: list[j], list[j + 1] = list[j + 1], list[j] for k in range((len(list) - 2) - i, i, -1): if list[k] < list[k - 1]: list[k], list[k - 1] = list[k - 1], list[k] print list
def select_sort(list): for num in range(len(list) - 1, 0, -1): maxPos = 0 for loc in range(1, num + 1): if list[loc] > list[maxPos]: maxPos = loc list[num], list[maxPos]=list[maxPos], list[num] return list
After my inspiriation with Bubble Sort I decided to tackle Select Sort because of their similarity in application. At their core, both Bubble and Select sorts ascend with one value at a time and leave room for my descending concept. Once again:
I thought it would be fun to write this algorithm with a check as to whether or not the highest or lowest value was already in the first or last index. Since this would normally result in the function not moving any indexes during an entire path, I have that value left in the index one spot below or above that one. For example when we descend the list:
By adding one digit to the loc2 variable, we can accelerate the rate at which we remove indexes and thus, avoid wasting the current index that we're storing. Of course this requires a constant checking as to whether or not we're at the beginning or end of the current state of the list, which isn't particularly ideal.
elif loc2 == beg: beg += 1 loc2 += 1
def danny_select(list): maxPos = 0 beg = 0 end = len(list) for num in range((len(list) - 1)//2): for loc in range(beg + 1, end - num): if list[loc] > list[maxPos]: if loc != end - num - 1: maxPos = loc elif loc == end - num - 1: loc -= 1 end -= 1 list[loc], list[maxPos]=list[maxPos], list[loc] minPos = loc - 1 for loc2 in range(end - 2, num - 1, -1): if list[loc2] < list[minPos]: if loc2 != beg: minPos = loc2 elif loc2 == beg: beg += 1 loc2 += 1 list[loc2], list[minPos]=list[minPos], list[loc2] maxPos = loc2 + 1 if maxPos == minPos: return list return list
That sort would be great for a list that we already know is mostly organized already. But for the simplest implementation of this idea I wrote:
def danny_shortsort_select(list): maxPos = 0 for num in range((len(list) - 1)//2): for loc in range(num + 1, len(list) - num): if list[loc] > list[maxPos]: maxPos = loc list[loc], list[maxPos]=list[maxPos], list[loc] minPos = loc - 1 for loc2 in range(loc - 2, num - 1, -1): if list[loc2] < list[minPos]: minPos = loc2 list[loc2], list[minPos]=list[minPos], list[loc2] maxPos = loc2 + 1 return list