Algorithms/Sort - Revision history

Admin: Fix LaTeX errors: \prod_{k=1}{n} → \prod_{k=1}^{n} (missing ^) and floor → \lfloor...\rfloor (via update-page on MediaWiki MCP Server)

2026-06-05T23:16:10Z

Fix LaTeX errors: \prod_{k=1}{n} → \prod_{k=1}^{n} (missing ^) and floor → \lfloor...\rfloor (via update-page on MediaWiki MCP Server)

2017-07-16T09:53:14Z

Skiena Chapter 4

← Older revision		Revision as of 09:53, 16 July 2017
Line 18:		Line 18:

	Lots of good information here.		Lots of good information here.

			See [[Skiena Chapter 4 Questions]] for end of chapter questions.

	===Sorting===		===Sorting===

2017-07-16T03:43:34Z

Quick sort - randomization

← Older revision		Revision as of 03:43, 16 July 2017
Line 142:		Line 142:
	To get the overall cost of the algorithm, we must divide the array successively into halves - for a maximum of log(n) halving steps - and perform the linear merge step for each halving step, for a total of O(n log n).		To get the overall cost of the algorithm, we must divide the array successively into halves - for a maximum of log(n) halving steps - and perform the linear merge step for each halving step, for a total of O(n log n).

	===Quick ~~sort~~ - ~~randomization~~===		===Quick Sort - Randomization===

	Quick sort - pick a random item p from the items we seek to sort, and partition the other n-1 items into two piles: less than p, and greater than p.		Quick sort - pick a random item p from the items we seek to sort, and partition the other n-1 items into two piles: less than p, and greater than p.

2017-07-16T03:42:40Z

Lower Bound on Sorting

← Older revision		Revision as of 03:42, 16 July 2017
Line 240:		Line 240:
	===Lower Bound on Sorting===		===Lower Bound on Sorting===

	Any sorting algorithm must have a <math>\Omega(n \log n)</math> bound, shown by observing that any sorting algorithm must behave differently during execution on any of the possible n! permutations of n keys. Because <math>\log n! = \Theta(n \log n)</math>, the algorithm big-Omega is also n log n.		Any sorting algorithm must have a <math>\Omega(n \log n)</math> bound, shown by observing that any sorting algorithm must behave differently during execution on any of the possible n! permutations of n keys. Because <math>\log n! \sim \Theta(n \log n)</math>, the algorithm big-Omega is also n log n.

	Sorting has one of the few nontrivial lower bounds among algorithm problems		Sorting has one of the few nontrivial lower bounds among algorithm problems

2017-07-16T03:28:36Z

Bucket Sort

← Older revision		Revision as of 03:28, 16 July 2017
Line 237:		Line 237:

	Examples of bad cases: phone book (Shifflett example), extreme tails, can kill performance		Examples of bad cases: phone book (Shifflett example), extreme tails, can kill performance

			===Lower Bound on Sorting===

			Any sorting algorithm must have a <math>\Omega(n \log n)</math> bound, shown by observing that any sorting algorithm must behave differently during execution on any of the possible n! permutations of n keys. Because <math>\log n! = \Theta(n \log n)</math>, the algorithm big-Omega is also n log n.

			Sorting has one of the few nontrivial lower bounds among algorithm problems

	=Flags=		=Flags=

2017-07-16T03:26:54Z

Why Search

← Older revision		Revision as of 03:26, 16 July 2017
Line 59:		Line 59:
	* Learning sorting is not just about learning sorting - the design techniques you learn in sort are important for other algorithmic problems		* Learning sorting is not just about learning sorting - the design techniques you learn in sort are important for other algorithmic problems

	Sorting can be used to ~~illuastrate~~ many algorithm design paradigms - data structure techniques, divide-and-~~consquer~~, randomization, and incremental construction.		Sorting can be used to illustrate many algorithm design paradigms - data structure techniques, divide-and-conquer, randomization, and incremental construction.

	===Heap Sort===		===Heap Sort===

2017-07-16T03:26:33Z

Pragmatics

← Older revision		Revision as of 03:26, 16 July 2017
Line 52:		Line 52:

	The general approach should be to use an external comparison function (a comparator) that takes pointers to records and returns the result of the comparison. In general, compare(a,b) will return negative if a comes before b, positive if b comes before a, and 0 if they are equal.		The general approach should be to use an external comparison function (a comparator) that takes pointers to records and returns the result of the comparison. In general, compare(a,b) will return negative if a comes before b, positive if b comes before a, and 0 if they are equal.

			===Why Search===

	Why focus so much on search?		Why focus so much on search?
	* Knuth estimated 25% of compute time is spent sorting		* Knuth estimated 25% of compute time is spent sorting
	* Learning sorting is not just about learning sorting - the design techniques you learn in sort are important for other algorithmic problems		* Learning sorting is not just about learning sorting - the design techniques you learn in sort are important for other algorithmic problems

			Sorting can be used to illuastrate many algorithm design paradigms - data structure techniques, divide-and-consquer, randomization, and incremental construction.

	===Heap Sort===		===Heap Sort===

2017-07-16T02:40:14Z

Randomization Technique

@@ Line 218: / Line 218: @@
 * Random sampling - if you want to get an idea of the median value, but not enough time to look at all of them
 * Randomized hashing - hashing can be used to implement dictionary operations in O(1) expected time; to make this high probability, can choose a random hash function - make your hash function random so your keys don't have to be
 =Flags=

2017-07-16T02:37:34Z

Quick Sort Cost Analysis

← Older revision		Revision as of 02:37, 16 July 2017
Line 212:		Line 212:

	"Randomized quicksort runs in <math>\Theta(n \log n)</math> time on any input, with high probability."		"Randomized quicksort runs in <math>\Theta(n \log n)</math> time on any input, with high probability."

			===Randomization Technique===

			The randomization technique makes proper analysis more complicated (requires probability analysis), but overall there are some principles to keep in mind:
			* Random sampling - if you want to get an idea of the median value, but not enough time to look at all of them
			* Randomized hashing - hashing can be used to implement dictionary operations in O(1) expected time; to make this high probability, can choose a random hash function - make your hash function random so your keys don't have to be

	=Flags=		=Flags=

2017-07-16T02:35:01Z

Quick Sort Cost Analysis

← Older revision		Revision as of 02:35, 16 July 2017
Line 203:		Line 203:
	</math>		</math>

	This means the overall cost of the algorithm is <math>\Theta(log n)</math> - meaning the worst-case cost won't kill performance.		This means the overall cost of the algorithm is <math>\Theta(\log n)</math> - meaning the worst-case cost won't kill performance.

			Summary: we want to go from this:

			"Quicksort runs in <math>\Theta(n \log n)</math> time, with high probability, if you give me randomly ordered data to sort."

			to this:

			"Randomized quicksort runs in <math>\Theta(n \log n)</math> time on any input, with high probability."

	=Flags=		=Flags=