Talk:TADM2E 4.4 - Revision history

Landisdesign at 00:12, 21 November 2019

2019-11-21T00:12:38Z

Joky at 07:31, 30 December 2016

2016-12-30T07:31:55Z

Anandp219 at 22:03, 29 October 2015

2015-10-29T22:03:34Z

Far9999: Created page with "Why break up the pairs and use buckets? It seems like you simply need three passes: First pass - get the reds and insert them in order into a new array of size n (assuming w..."

2015-01-07T14:26:44Z

Created page with "Why break up the pairs and use buckets? It seems like you simply need three passes: First pass - get the reds and insert them in order into a new array of size n (assuming w..."

New page

Why break up the pairs and use buckets? It seems like you simply need three passes:
First pass - get the reds and insert them in order into a new array of size n (assuming we can use additional space)
Second pass - get the blues and insert them in order into the array
Third pass - get the yellows and insert them in order into the array

Each pass is O(n) since we have to visit each element, so the entire algorithm is O(n).

← Older revision		Revision as of 00:12, 21 November 2019
Line 19:		Line 19:
	swap(a,++index_blue,index)		swap(a,++index_blue,index)

−	The ''swap''' above makes it a non-stable sort.	+	The ''swap'' above makes it a non-stable sort.
		+
		+	''Any stable source can do'' looks inaccurate to me. Insert and selection are O(n^2). Bucket sort and the variant at the top seem the only ways to do it in O(n).

@@ Line 5: / Line 5: @@
 Each pass is O(n) since we have to visit each element, so the entire algorithm is O(n).
@@ Line 17: / Line 18: @@
          if a[index].color=="blue"
               swap(a,++index_blue,index)

← Older revision		Revision as of 22:03, 29 October 2015
Line 5:		Line 5:

	Each pass is O(n) since we have to visit each element, so the entire algorithm is O(n).		Each pass is O(n) since we have to visit each element, so the entire algorithm is O(n).
		+
		+
		+	EDIT:
		+	Why three passes ? .Two passes can do it
		+	index_red=-1
		+	for index =0 to a.length-1
		+	if a[index].color == "Red"
		+	swap(a,++index_red,index)
		+	index_blue=index_red
		+	for index = index_blue+1 to a.length-1
		+	if a[index].color=="blue"
		+	swap(a,++index_blue,index)