Week 03 (Sorting) (39)

39

Summary of Elementary Sorts

Comparison of sorting algorithms (online)

	#compares			#swaps			#moves
	min	avg	max	min	avg	max	min	avg	max
Selection sort	n²	n²	n²	n	n	n	.	.	.
Bubble sort	n	n²	n²	0	n²	n²	.	.	.
Insertion sort	n	n²	n²	.	.	.	n	n²	n²
Shell sort	n	n^4/3	n^4/3	.	.	.	1	n^4/3	n^4/3

Which is best?

depends on cost of compare vs swap vs move for Items
depends on likelihood of average vs worst case