Discussion topics

Week of Feb 19th


Comparing Sorting Algorithms with Different Applications



			      


Matching Sorting Methods with Applications:  

First, outline what the strengths(weaknesses) of the following sorts.

1)  Bubble Sort (N^2/2 Comp, N^2/2 exch -- avg)
		a. To what types of data sets is it suited?
		b. Bubble vs. Shaker Sort
		c. Would you ever just use Bubble?
		d. Stable?
	 	e. Avg/Worst complexity?
		f. Improving avg with adaptive sorting
		
2)  Insertion Sort (N^2/4 Comp, N^2/2 exch, double that for worst)
		a. To what types of data sets is it suited?
		b. Insertion vs Shaker 
		c. Stable?
		d. Avg/Worst complexity?
		e. Improving avg performance with adaptive sorting
		
3)	Selection Sort (N^2) 
		a. Our Text claims it is good for objects with large data and small 
			 keys, due to the small number of swaps.  
			  -->What is a better solution for large objects?
		b. What else would selection sort be good for?
		c. Adaptive?

4) 	Index Sorting
		a. Renders insertion sort practically useless.
		b. Use for sort by multiple fields
		
5)	QuickSort (Nlog(N) best and avg, N^2 worst)
		a. stability?
		b. appropriate data sets
		c. using median of 3 partitioning to improve performance

6)	MergeSort (Nlog(N) best avg and worst)
		a. Extra memory requirement
		b. stability

7)	Radix Sort 
		a.	Binary Quicksort (min( N^2, N*keylength)) worst 
		b.	MSD Radix Quicksort
		c. 	Bin sorting with linked lists
		
		
Now, Select a sort for the following applications:

1) You have a sorted array, and a new element is inserted randomly
2) You have a sorted array, and a few elements are swapped
3) You want to sort a database to index by name and phone number
4) You want to sort a Deck of Cards.
5) You want a computer to sort a deck of cards.
6) You are a computer architect and want to implment a sort in Hardware
7) You want to sort runners by times after each leg of a race.
8)