Sort Algorithms

Sorting Algorithms

  • Modified Bubble Sort
  • Selection Sort
  • Insertion Sort
  • Heap Sort
  • MergeSort
  • QuickSort

http://www.cprogramming.com/tutorial/computersciencetheory/sortcomp.html

Sorting Algorithms visualized

Nice visualization of sorting algorithms
http://math.hws.edu/TMCM/java/labs/xSortLabLab.html#bubble

Short summary

  • quicksort is the fastest sorting algorithm in practice but has a number of pathological cases that can make it perform as badly as O(n2).
  • heapsort is guaranteed to run in O(n*ln(n)) and requires only finite additional storage. But there are many citations of real world tests which show that heapsort is significantly slower than quicksort on average.
  • Because of the above two facts, a relatively new hybrid sorting algorithm called "introspective sort" looks very promising. Introspective sort basically applies quicksort recursively until it realizes something has gone wrong then switches to heapsort. In this way it has a worst case performance of O(n*ln(n)) * and an average performance basically equal to quicksort.
  • mergesort is guaranteed to run in O(n*ln(n)) but requires n units of additional temporary storage.

http://www.azillionmonkeys.com/qed/sort.html

Using QuickSort in C

#include <stdlib.h>
_CRTIMP void __cdecl qsort(void*, size_t, size_t,
               int (*)(const void*, const void*));

[[/code]]

QuickSort implemented in various languages

http://en.literateprograms.org/Category:Quicksort

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License