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

page revision: 4, last edited: 29 Dec 2007 10:05