Quicksort-based Sorting System

A Quicksort-based Sorting System is a sorting system (that applies a Quicksort algorithm.

• Context:
  • …
• Example(s):
  • a C++ Quicksort Algorithm: https://github.com/JuliaLang/julia/blob/master/test/perf/perf.cpp
  • a Julia Quicksort Algorithm: https://github.com/JuliaLang/julia/blob/master/test/perf/perf.jl
  • a Python Quicksort Algorithm: https://github.com/JuliaLang/julia/blob/master/test/perf/perf.py
  • a MatLab Quicksort Algorithm: https://github.com/JuliaLang/julia/blob/master/test/perf/perf.m
  • a R Quicksort Algorithm: https://github.com/JuliaLang/julia/blob/master/test/perf/perf.R
  • an JavaScript Quicksort Algorithm: https://github.com/JuliaLang/julia/blob/master/test/perf/perf.js
• Counter-Example(s):
  • Bubblesort-based System.
  • Mergesort-based System.
• See: Randomized System.

---

---

References

2017

• https://github.com/JuliaLang/julia/blob/master/test/perf/perf.jl

function qsort!(a,lo,hi)
   i, j = lo, hi
   while i < hi
       pivot = a[(lo+hi)>>>1]
       while i <= j
           while a[i] < pivot; i = i+1; end
           while a[j] > pivot; j = j-1; end
           if i <= j
               a[i], a[j] = a[j], a[i]
               i, j = i+1, j-1
           end
       end
       if lo < j; qsort!(a,lo,j); end
       lo, j = i, hi
   end
   return a
end

2017b

• http://cs231n.github.io/python-numpy-tutorial/ or https://github.com/kuleshov/cs228-material/blob/master/tutorials/python/cs228-python-tutorial.ipynb
  • … As an example, here is an implementation of the classic quicksort algorithm in Python:

def quicksort(arr):
   if len(arr) <= 1:
       return arr
   pivot = arr[len(arr) // 2]
   left = [x for x in arr if x < pivot]
   middle = [x for x in arr if x == pivot]
   right = [x for x in arr if x > pivot]
   return quicksort(left) + middle + quicksort(right)

print quicksort([3,6,8,10,1,2,1])
[1, 1, 2, 3, 6, 8, 10]

---