289,261 views 258 on YTPak
977 96

Published on 15 Jan 2013 | over 4 years ago

This video describes the algorithm for quicksort, a popular sorting technique used widely in practice. It employs a recursive "divide and conquer" strategy. Using several examples, the video develops the ideas that drive the algorithm, and shows how quicksort works on a variety of inputs, from the most extreme to the most general. The running time of quicksort is built from counts of item-to-item comparisons for specific examples, leading to the big O generalization. The running time is then compared with that of insertion sort, telling us which sorting algorithm to use when. This video is part of a series on data structures and algorithms, by Sesh Venugopal, Rutgers University. http://www.cs.rutgers.edu/~venugopa

(One of you pointed out an error - thanks! - at 10:45, where instead of adding the 16s I mistakenly multiplied them: so what shows as 16*16*16*16 should be 16+16+16+16. The subsequent numbers are correct--16*4 = 64, for total number of comparisons. Sorry for the error.)

Loading related videos...