Sorting Algorithms

Getting your numbers the right way!

Dennis "@the_metalgamer" Fink

30 May 2014

at "Spark-Up: Tie on!" by C3L

Overview

• Introduction
• Comparing Sort Algorithms
• Non-comparing Sort Algorithms
• Fun
• Conclusion

Introduction

• Types
• In-Place
• Stability
• Notes on performance

Types

• Comparing Algorithms
• Non-Comparing Algorithms

In-Place

• Overwrite the original datastructure

Stability

• Keep relative order of elements with the same value

Notes on performance

• Big-O Notation
• Growth rate
• n = number of elements
• Lower boundaries:
  • O(n)
  • O(n*log(n)) in worst-case (comparative algorithms)
• Important: Not seconds!

Selectionsort

• Array divided in two parts
  • Sorted items
  • Unsorted items
• Find the smallest element in the unsorted sublist
• Exchange with the left most unsorted element
• Move sublist boundaries one to the right
• Normally in-place
• Unstable
  • Can be implemented stable

Implementation

def selectionsort(list_):

    for i in range(len(list_) - 1):
        k = i
        for j in range(i, len(list_)):
            if list_[j] < list_[k]:
                k = j
        list_[i], list_[k] = list_[k], list_[i]

Out-of-place Implementation

def selectionsort_min(list_):

    new = []

    while list_:
        minimum = min(list_)
        list_.remove(minimum)
        new.append(minimum)

    return new

Performance

• Best case: O(n²)
• Average case: O(n²)
• Worst case: O(n²)

Bubblesort

• Compare each pair of adjacent items
• Swap if not in order
• Until no swaps are needed
• In-Place
• Stable

Implementation

def bubblesort(list_):

    swapped = True

    while swapped:

        swapped = False

        for i in range(0, len(list_) - 1):
            if list_[i] > list_[i + 1]:
                list_[i], list_[i + 1] = list_[i + 1], list_[i]
                swapped = True

    return list_

Performance

• Best case: O(n)
• Average case: O(n²)
• Worst case: O(n²)

Cocktailsort

• Same as bubblesort
• But go from start to end and then from end to start

Implementation

def shakersort(list_):
    start = -1
    end = len(list) - 2
    swapped = True
    while swapped:
        # go from start to end
        swapped = False
        start = start + 1
        for i in range(start, end + 1):
            if list_[i] > list_[i + 1]:
                list_[i], list_[i + 1] = list_[i + 1], list_[i]
                swapped = True
        if not swapped:
            break
        # go from end to start
        swapped = False
        end = end - 1
        for i in range(end, start + 1, -1):
            if list_[i] > list_[i + 1]:
                list_[i], list_[i + 1] = list_[i + 1], list_[i]
                swapped = True
    return list_

Performance

• Best case: O(n)
• Average case: O(n²)
• Worst case: O(n²)

Combsort

• Compare elements which are far away (step)
• Divide the gap by 1.3
• Array is sorted when the gap is 1 and one run with no swaps
• Unstable
• In-Place

Implementation

def combsort(list_):
    step = len(list_)
    while True:
        swapped = False
        if step > 1:
            step = int(step / 1.3)
        for i in range(len(list) - step):
            if list_[i] > list_[i + step]:
                list_[i], list_[i + step] = list_[i + step], list_[i]
                swapped = True
        if not swapped and step <= 1:
            break
    return list_

Performance

• Best case: O(n * log(n))
• Average case: O(n * log(n))
• Worst case: O(n²)

Insertionsort

• Take one element
• Compare it with the already sorted list
• Put it in the right place
• Most humans do that
• Stable
• In-Place

Implementation

def insertionsort(list_):

    for i in range(1, len(list_)):
        tmp = list_[i]
        k = i
        while k > 0 and tmp < list_[k - 1]:
            list_[k] = list_[k - 1]
            k -= 1
        list_[k] = tmp

Performance

• Best case: O(n)
• Average case: O(n²)
• Worst case: O(n²)

Quicksort

• Divide and Conquer
• Recursive
• Choose pivot element
• Compare other elements against the pivot
  • if less, then append to the left sublist
  • if greater, then append to the right sublist
• Do quicksort on the sublists until length is 1
• Unstable
• Out-of-place

Implementation

def quicksort(list_):

    if not list_:
        return list_
    else:
        pivot = list_[0]
        lesser = quicksort([x for x in list_[1:] if x < pivot])
        greater = quicksort([x for x in list_[1:] if x >= pivot])
        lesser.append(pivot)
        return lesser.extend(greater)

Performance

• Best case: O(n * log(n))
• Average case: O(n * log(n))
• Worst case: O(n²)
• Selected pivot matters

Mergesort

• Divide and conquer
• Divide the unsortes list into n sublists
  • each containing 1 element
• Repeatedly merge sublists to produce new sorted sublists
• Stable
• Out-of-place

Implementation

def mergesort(list_):

    if len(list_) <= 1:
        return list_

    middle = len(list_) / 2
    left = mergesort(list_[:middle])
    right = mergesort(list_[middle:])

    return list(merge(left,right))

Implementation (Cont.)

def merge(left, right):
    result = []
    left_idx, right_idx = 0, 0
    while left_idx < len(left) and right_idx < len(right):
        if left[left_idx] <= right[right_idx]:
            result.append(left[left_idx])
            left_idx += 1
        else:
            result.append(right[right_idx])
            right_idx += 1

    if left:
        result.extend(left[left_idx:])
    else:
        result.extend(right[right_idx:])

    return result

Performance

• Best case: O(n * log(n))
• Average case: O(n * log(n))
• Worst case: O(n * log(n))

Natural Mergesort

• Find already sorted sublists
• Don't split them
• Performance
  • Best case: O(n)
  • Average case: O(n * log(n))
  • Worst case: O(n * log(n))

Timsort

• Adaptive natural mergesort
• Standard in Python
• Smaller lists will use insertionsort
• Stable

Performance

• Best case: O(n)
• Average case: O(n * log(n))
• Worst case: O(n * log(n))

Radixsort

• Non-Comparing Sort
• 2 Phases
  • Partioning
  • Collect
• Put elements in the respective bucket
• Collect them
• Repeat for every digit in the number
• Until the largest number has checked all digits

Implementation

from math import log10

def radixsort(list_):
    maxlen = -1
    for number in list_:
        numlen = int(log10(number)) + 1
        if numlen > maxlen:
            maxlen = numlen
    buckets = [[] for i in range(0, 10)]
    for digit in range(0, maxlen):
        for number in list_:
            buckets[number / 10 ** digit % 10].append(number)
        del list_[:]
        for bucket in buckets:
            list_.extend(bucket)
            del list_[:]
    return list_

Performance

• O(m * n)
• m = Number of digits of biggest number

Bogosort

• Randomly mix the list
• See if the list is sorted

Implementation

from random import shuffle

def bogosort(list_):
    while list_ != sorted(list_):
        shuffle(list_)
    return list_

Performance

• Best case: O(n)
• Average case: O(n * n!)
• Worst case: Infinite

Sound of sorting

• http://panthema.net/2013/sound-of-sorting/

Conclusions

• Don't implement your own, if the language has one implemented