Sorting Notes

Posted on | In , |

Sorting Notes

Sorting puts elements of a list in a certain order, which is critical in computer science algorithms in terms of efficiency.
It is easier and faster to locate items in a sorted list than unsorted.
There are many sorting algorithms I encountered since I started teaching myself to code. Here are a little reference notes of common sorting algorithms.

Quick Sort

O(N Log N)

1
2
3
4
5
6
7
8
9
10
11
def quicksort(seq):
    if len(seq) <= 1:
        return seq
    lo, pi, hi = partition(seq)
    return quicksort(lo) + [pi] + quicksort(hi)
def partition(seq):
    pi, seq = seq[0], seq[1:]
    lo = [x for x in seq if x <= pi]
    hi = [x for x in seq if x > pi]
    return lo, pi, hi

Quick Select

O (K Log N)
Quick select is a modification of quick sort.

Merge Sort

O(N Log N)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def merge_sort(arr):
    if len(arr)<=1:  #important
        return arr
    mid = len(arr)/2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left,right)
def merge(left,right):
    if not left:
        return right
    if not right:
        return left
    if left[0]<right[0]:
        return [left[0]] + merge(left[1:],right)
    else:
        return [right[0]] + merge(left,right[1:])
arr = [1,4,5,6,33,3,2,5,6,0,15]
print merge_sort(arr)

Bucket Sort

O(N + k)

  • bucketSort(arr[], n)
    1. Create n empty buckets (Or lists).
    2. Do following for every array element arr[i].
      • Insert arr[i] into bucket[n*array[i]]
    3. Sort individual buckets using insertion sort.
    4. Concatenate all sorted buckets. 
1
2
3
4
5
6
7
8
9
10
11
12
13
def bucket_sort(seq,bucket_size = 5):
    biggest = 0
    for number in seq:
        if number > biggest:
            biggest = number
    buckets = [[] for _ in xrange(biggest / bucket_size + 1)]
    for number in seq:
        buckets[number / bucket_size].append(number)
    for index, bucket in enumerate(buckets):
        #Using quicksort to sort individual buckets
        buckets[index] = sorted(bucket)
    new_list = [num for bucket in buckets for num in bucket]
    return new_list

Radix Sort

O(N * k)

There more challenging sorting puzzles in LeetCode:

Questions

Reference