
Sorting Algorithm

This is a sorting algorithm.   It may be applied to a set of data in order to sort it.    
For comparing various sorts, see compare sorts.  
For other sorting algorithms,   see sorting algorithms,   or:

O(n logn) sorts
Heap sort |
Merge sort |
Patience sort |
Quick sort
O(n log2n) sorts
Shell Sort
O(n2) sorts
Bubble sort |
Cocktail sort |
Cocktail sort with shifting bounds |
Comb sort |
Cycle sort |
Gnome sort |
Insertion sort |
Selection sort |
Strand sort
other sorts
Bead sort |
Bogo sort |
Common sorted list |
Composite structures sort |
Custom comparator sort |
Counting sort |
Disjoint sublist sort |
External sort |
Jort sort |
Lexicographical sort |
Natural sorting |
Order by pair comparisons |
Order disjoint list items |
Order two numerical lists |
Object identifier (OID) sort |
Pancake sort |
Quickselect |
Permutation sort |
Radix sort |
Ranking methods |
Remove duplicate elements |
Sleep sort |
Stooge sort |
[Sort letters of a string] |
Three variable sort |
Topological sort |
Tree sort


Measure a relative performance of sorting algorithms implementations.

Plot execution time vs. input sequence length dependencies for various implementation of sorting algorithm and different input sequence types (example figures).

Consider three type of input sequences:

   ones: sequence of all 1's.   Example: {1, 1, 1, 1, 1}
   range: ascending sequence, i.e. already sorted.   Example: {1, 2, 3, 10, 15}
   shuffled range: sequence with elements randomly distributed.   Example: {5, 3, 9, 6, 8}


Consider at least two different sorting functions (different algorithms or/and different implementation of the same algorithm).

For example, consider Bubble Sort, Insertion sort, Quicksort or/and implementations of Quicksort with different pivot selection mechanisms.   Where possible, use existing implementations.

Preliminary subtask:

   Bubble Sort, Insertion sort, Quicksort, Radix sort, Shell sort
   Query Performance
   Write float arrays to a text file
   Plot x, y arrays
   Polynomial Fitting


General steps:

   Define sorting routines to be considered.
   Define appropriate sequence generators and write timings.
   Plot timings.
   What conclusions about relative performance of the sorting routines could be made based on the plots?


import algorithm
import random
import sequtils
import times
 
 
####################################################################################################
# Data.
 
proc oneSeq(n: int): seq[int] = repeat(1, n)
 
#---------------------------------------------------------------------------------------------------
 
proc shuffledSeq(n: int): seq[int] =
  result.setLen(n)
  for item in result.mitems: item = rand(1..(10 * n))
 
#---------------------------------------------------------------------------------------------------
 
proc ascendingSeq(n: int): seq[int] = sorted(shuffledSeq(n))
 
 
####################################################################################################
# Algorithms.
 
func bubbleSort(a: var openArray[int]) {.locks: "unknown".} =
  var n = a.len
  while true:
    var n2 = 0
    for i in 1..<n:
      if a[i - 1] > a[i]:
        swap a[i], a[i - 1]
        n2 = i
    n = n2
    if n == 0: break
 
#---------------------------------------------------------------------------------------------------
 
func insertionSort(a: var openArray[int]) {.locks: "unknown".} =
  for index in 1..a.high:
    let value = a[index]
    var subIndex = index - 1
    while subIndex >= 0 and a[subIndex] > value:
      a[subIndex + 1] = a[subIndex]
      dec subIndex
    a[subIndex + 1] = value
 
#---------------------------------------------------------------------------------------------------
 
func quickSort(a: var openArray[int]) {.locks: "unknown".} =
 
  func sorter(a: var openArray[int]; first, last: int) =
    if last - first < 1: return
    let pivot = a[first + (last - first) div 2]
    var left = first
    var right = last
    while left <= right:
      while a[left] < pivot: inc left
      while a[right] > pivot: dec right
      if left <= right:
        swap a[left], a[right]
        inc left
        dec right
    if first < right: a.sorter(first, right)
    if left < last: a.sorter(left, last)
 
  a.sorter(0, a.high)
 
#---------------------------------------------------------------------------------------------------
 
func radixSort(a: var openArray[int]) {.locks: "unknown".} =
 
  var tmp = newSeq[int](a.len)
 
  for shift in countdown(63, 0):
    for item in tmp.mitems: item = 0
    var j = 0
    for i in 0..a.high:
      let move = a[i] shl shift >= 0
      let toBeMoved = if shift == 0: not move else: move
      if toBeMoved:
        tmp[j] = a[i]
        inc j
      else:
        a[i - j] = a[i]
    for i in j..tmp.high: tmp[i] = a[i - j]
    for i in 0..a.high: a[i] = tmp[i]
 
#---------------------------------------------------------------------------------------------------
 
func shellSort(a: var openArray[int]) {.locks: "unknown".} =
 
  const Gaps = [701, 301, 132, 57, 23, 10, 4, 1]
 
  for gap in Gaps:
    for i in gap..a.high:
      let temp = a[i]
      var j = i
      while j >= gap and a[j - gap] > temp:
        a[j] = a[j - gap]
        dec j, gap
      a[j] = temp
 
#---------------------------------------------------------------------------------------------------
 
func standardSort(a: var openArray[int]) =
  a.sort()
 
 
####################################################################################################
# Main code.
 
import strformat
 
const
 
  Runs = 10
  Lengths = [1, 10, 100, 1_000, 10_000, 100_000]
 
  Sorts = [bubbleSort, insertionSort, quickSort, radixSort, shellSort, standardSort]
 
const
  SortTitles = ["Bubble", "Insert", "Quick ", "Radix ", "Shell ", "Standard"]
  SeqTitles = ["All Ones", "Ascending", "Shuffled"]
 
var totals: array[SeqTitles.len, array[Sorts.len, array[Lengths.len, Duration]]]
 
randomize()
 
for k, n in Lengths:
  let seqs = [oneSeq(n), ascendingSeq(n), shuffledSeq(n)]
  for _ in 1..Runs:
    for i, s in seqs:
      for j, sort in Sorts:
        var s = s
        let t0 = getTime()
        s.sort()
        totals[i][j][k] += getTime() - t0
 
echo "All timings in microseconds\n"
stdout.write "Sequence length  "
for length in Lengths:
  stdout.write &"{length:6d}     "
echo '\n'
for i in 0..SeqTitles.high:
  echo &"  {SeqTitles[i]}:"
  for j in 0..Sorts.high:
    stdout.write &"  {SortTitles[j]:8s}     "
    for k in 0..Lengths.high:
      let time = totals[i][j][k].inMicroseconds div Runs
      stdout.write &"{time:8d}   "
    echo ""
  echo '\n'