Sorting Algorithms in Python

Below are some popular sorting algorithms implemented in Python.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189

#!/usr/bin/env python   class BubbleSort(object):     @staticmethod     def sort(l):         new_list = list(l)         while True:             swapped = False             for i in xrange(0, len(new_list)-1):                 if new_list[i] > new_list[i+1]:                     new_list[i], new_list[i+1] = new_list[i+1], new_list[i]                     swapped = True             if not swapped: break         return new_list   class SelectionSort(object):     @staticmethod     def sort(l):         new_list = list(l)         for i in xrange(0, len(new_list)):             min_index = i             for j in xrange(i, len(new_list)):                 if new_list[j] < new_list[min_index]:                     min_index = j             new_list[i], new_list[min_index] = new_list[min_index], new_list[i]         return new_list   class InsertionSort(object):     @staticmethod     def sort(l):         new_list = list(l)         for i in xrange(1, len(new_list)):             j = i             while j > 0 and new_list[j] < new_list[j-1]:                 new_list[j-1], new_list[j] = new_list[j], new_list[j-1]                 j -= 1         return new_list   class ShellSort(object):     @staticmethod     def sort(l):         new_list = list(l)         n = len(l)         h = 1         while h < (n/3): h = (3*h) + 1         while h >= 1:             for i in xrange(h, n):                 j = i                 while j >=h and new_list[j] < new_list[j-h]:                     new_list[j], new_list[j-h] = new_list[j-h], new_list[j]                     j -= h             h /= 3         return new_list   class MergeSort(object):     @staticmethod     def sort(l):         new_list = list(l)         MergeSort.msort(new_list, 0, len(new_list)-1)         return new_list           @staticmethod     def msort(l, lo, hi):         if lo == hi: return         mi = (lo + hi) / 2         MergeSort.msort(l, lo, mi)         MergeSort.msort(l, mi + 1, hi)         MergeSort.merge(l, lo, mi, hi)           @staticmethod     def merge(a, lo, mi, hi):         i = lo         j = mi + 1         tmp = list(a)         hi = hi + 1         for x in xrange(lo, hi):             if i > mi:                 a[x] = tmp[j]                 j += 1             elif j >= hi:                 a[x] = tmp[i]                 i += 1             elif tmp[i] < tmp[j]:                 a[x] = tmp[i]                 i += 1             else:                 a[x] = tmp[j]                 j += 1   class QuickSort(object):     @staticmethod     def sort(l):         new_list = list(l)         import random         random.shuffle(new_list)         QuickSort.qsort(new_list, 0, len(new_list)-1)         return new_list           @staticmethod     def qsort(l, lo, hi):         if hi <= lo: return         j = QuickSort.partition(l, lo, hi)         QuickSort.qsort(l, lo, j-1)         QuickSort.qsort(l, j+1, hi)           @staticmethod     def partition(l, lo, hi):         i = lo         j = hi + 1         v = l[lo]         while True:             i += 1             while l[i] < v:                 if i == hi: break                 i += 1             j -= 1             while v < l[j]:                 if j == lo: break                 j -= 1             if i >= j: break             l[i], l[j] = l[j], l[i]         l[lo], l[j] = l[j], l[lo]         return j   class HeapSort(object):     @staticmethod     def sort(l):         new_list = list(l)         n = len(new_list)         # construct a binary heap         for i in xrange(n/2, 0, -1):             HeapSort.sink(new_list, i, n)         # sort down the heap         for i in xrange(n, 0, -1):             new_list[i-1], new_list[0] = new_list[0], new_list[i-1]             HeapSort.sink(new_list, 1, i-1)         return new_list           @staticmethod     def sink(l, current_pos, n):         child_pos = HeapSort.get_child_position(l, current_pos, n)         if child_pos == -1: return                       while l[child_pos-1] > l[current_pos-1]:             l[child_pos-1], l[current_pos-1] = l[current_pos-1], l[child_pos-1]             current_pos = child_pos             child_pos = HeapSort.get_child_position(l, current_pos, n)             if child_pos == -1: break                   @staticmethod     def get_child_position(l, current_pos, n):         first_child_pos = 2 * current_pos         second_child_pos = (2 * current_pos) + 1         child_pos = -1 # no child         # no child         if first_child_pos > n: return child_pos         # there's only one child         if second_child_pos > n: child_pos = first_child_pos         else: # there are two children             if l[first_child_pos-1] > l[second_child_pos-1]:                 child_pos = first_child_pos             else:                 child_pos = second_child_pos         return child_pos       if __name__ == "__main__":    expected_list = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]    input_list = [9, 3, 6, 5, 7, 1, 8, 10, 2, 4]      sorted_list = BubbleSort.sort(input_list)    assert sorted_list == expected_list      sorted_list = SelectionSort.sort(input_list)    assert sorted_list == expected_list      sorted_list = InsertionSort.sort(input_list)    assert sorted_list == expected_list      sorted_list = ShellSort.sort(input_list)    assert sorted_list == expected_list         sorted_list = MergeSort.sort(input_list)    assert sorted_list == expected_list      sorted_list = QuickSort.sort(input_list)    assert sorted_list == expected_list         sorted_list = HeapSort.sort(input_list)    assert sorted_list == expected_list