Anne Dawson: N_Log_N_sorts.htm   

Last updated: Saturday 20th November 2004, 16:32 PT

This document is subject to change without notice.

Please report any errors or omissions in this document:

adawson@coquitlamcollege.com

 

 

 

 

N Log N sorts

 

 

http://knight.cis.temple.edu/~lakaemper/courses/cis068_2003/slides/cis068_09.ppt

http://www.site.uottawa.ca/~stan/csi2514/applets/sort/sort.html

http://www.student.seas.gwu.edu/~idsv/idsv.html

http://www.cosc.canterbury.ac.nz/people/mukundan/dsal/appldsal.html

http://www.cs.ubc.ca/spider/harrison/Java/sorting-demo.html

 

 

 

The topic of sorting occupies a prominent position in computer science. It has been estimated that anywhere from 25% to 50% of all computing time in the commercial world is spent on sorting data.  Many sorting methods have been conceived.  Some are more appropriate than others, depending on the nature of the data to be sorted. O(N2) sorts are too inefficient to be practical for sorting large quantities of data.  A bubblesort program which takes minutes to sort 1000 elements may take hours to sort 10,000 values. This document describes two sorting algorithms with better than O(N2) performance characteristics: Quicksort and Mergesort.  Quicksort has a best case running time of O(NLogN), an average case running time of O(NLogN) and a worst case running time of O(N2). Mergesort performs at O(NLogN) in best, average and worst case.

 

Quicksort

 

http://en.wikipedia.org/wiki/Quicksort

Quick sort description and animation:

http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/qsort.html

 

http://www.student.seas.gwu.edu/~idsv/idsv.html

http://www.coquitlamcollege.com/adawson/Quicksort.htm

http://www.coquitlamcollege.com/adawson/quicksort10.cpp

http://www.coquitlamcollege.com/adawson/quicksort_timed.cpp

 

Mergesort

 

http://www.coquitlamcollege.com/adawson/Mergesort.htm

http://www.coquitlamcollege.com/adawson/mergesort1.cpp

http://www.coquitlamcollege.com/adawson/mergesort2.cpp

http://www.coquitlamcollege.com/adawson/mergesort3.cpp

 

http://en.wikipedia.org/wiki/Mergesort

http://www.student.seas.gwu.edu/~idsv/idsv.html

http://www.cosc.canterbury.ac.nz/people/mukundan/dsal/MSort.html