Last week I showed you the radix sort on simple linked lists. This week, I will present a version of QuickSort modified to sort simply linked lists.
Sorting Lists (part II)
June 23, 2009
2 Comments | 
algorithms, bit twiddling, C, C99, data structures, hacks, Mathematics, programming, theoretical computer science, Uncategorized | Tagged: address transformation, box plot, box-and-whiskers, boxplot, comparison sort, gettimeofday, graphs, median, microsecond, quartile, quartiles, Quick Sort, QuickSort, radix, Radix Sort, tests, timer, trials | 
Permalink
Posted by Steven Pigeon
Sorting Linked Lists (part I)
June 16, 2009The sorting algorithms we were taught in class were typically simplified versions of the algorithms that assumed that the data remained in memory and in contiguous memory locations, also known as an array. What we often have, however, are linked lists. Generalizing algorithms like the QuickSort to lists is not very hard in fact if we use a modification of the basic algorithm.
For lists with numerical keys (or values), there might be a simpler algorithm that scans the list in only one direction, so that simply linked lists are a perfectly cromulent data structure, that is, the radix sort.
2 Comments | algorithms, C99, data structures, database, Mathematics | Tagged: aces, card deck, cromulent, data mining, data set, deuces, external sorting, French suits, kings, large data set, linked lists, lists, playing cards, QuickSort, radix, Radix Sort, sorting cards | Permalink
Posted by Steven Pigeon
