Merge Sort/Pseudocode - Revision history

Admin: /* Merge two arrays function using pop */

2019-02-01T07:39:14Z

Merge two arrays function using pop

← Older revision		Revision as of 07:39, 1 February 2019
Line 23:		Line 23:

	<pre>		<pre>
	function mergeTwoArrays (array[] s1, array[] s2, array[] dest) {		function mergeTwoArrays (array[] s1, array[] s2, array[] dest):
	n_iterations = length of dest		n_iterations = length(dest)
	q1 = populate queue from s1		q1 = populate queue from s1
	q2 = populate queue from s2		q2 = populate queue from s2
	for k = 0 to k = n_iterations - 1 {		for k = 0 to k = n_iterations - 1:
	if q1.peek() < q2.peek() {		if q1.peek() < q2.peek():
	front = q1.pop()		front = q1.pop()
	} else {		else:
	front = q2.pop()		front = q2.pop()
	}
	dest[k] = front		dest[k] = front
	}
	return		return
	}
	</pre>		</pre>

Line 42:		Line 41:

	<pre>		<pre>
	function mergeTwoArrays (arr[] s1, arry[] s2, arr[] dest) {		function mergeTwoArrays (arr[] s1, arry[] s2, arr[] dest):
	n_iterations = length of dest		n_iterations = length of dest
	i = j = 0		i = j = 0
	for k = 0 to k = n_iterations - 1 {		for k = 0 to k = n_iterations - 1:
	if s1[i] < s2[j] {		if s1[i] < s2[j]:
	front = s1[i]		front = s1[i]
	i += 1		i += 1
	} else {		else:
	front = s2[j]		front = s2[j]
	j += 1		j += 1
	}
	dest[k] = front		dest[k] = front
	}
	return		return
	}
	</pre>		</pre>

Admin: /* Recursive merge sort function */

2019-02-01T07:38:15Z

Recursive merge sort function

← Older revision		Revision as of 07:38, 1 February 2019
Line 72:		Line 72:

	<pre>		<pre>
	function mergeSort( array[] data ) {		function mergeSort( array[] data ):

	// base case:		// base case:
	if len(data) < 2 {		if len(data) < 2:
	return data		return data
	}

	// recursive case:		// recursive case:

Admin: /* Flags */

2019-02-01T07:35:30Z

Flags

← Older revision		Revision as of 07:35, 1 February 2019
Line 119:		Line 119:

	==Flags==		==Flags==

			{{MergeSortFlag}}

	{{AlgorithmsFlag}}		{{AlgorithmsFlag}}

Admin: /* Nonrecursive (Bottom-Up) Merge Sort Algorithm Pseudocode */

2019-02-01T05:54:05Z

Nonrecursive (Bottom-Up) Merge Sort Algorithm Pseudocode

← Older revision		Revision as of 05:54, 1 February 2019
Line 103:		Line 103:
	Deploy a second array that stores the merged runs (swap input/output arrays at every iteration).		Deploy a second array that stores the merged runs (swap input/output arrays at every iteration).

	<pr>		<pre>
	function merge_sort(S) {		function merge_sort(S) {
	src = S		src = S

Admin: /* Merge Sort Algorithm Pseudocode */

2019-02-01T05:50:17Z

Merge Sort Algorithm Pseudocode

@@ Line 14: / Line 14: @@
 * merge two arrays into a destination array of correct size
-==Merge Sort Algorithm Pseudocode==
+==Recursive Merge Sort Algorithm Pseudocode==
 ===Merge two arrays function using pop===
@@ Line 59: / Line 59: @@
 </pre>
-===Merge sort function - recursive===
+===Recursive merge sort function===
 Recursive merge sort starts with an input array. It splits the array in half. It recursively calls merge sort on the left and right halves. It then merges the left and right halves into a final result array and returns it.
@@ Line 92: / Line 92: @@
      return data
+}
 </pre>

Admin: /* Merge sort function - recursive */

2019-02-01T05:35:30Z

Merge sort function - recursive

← Older revision		Revision as of 05:35, 1 February 2019
Line 94:		Line 94:
	}		}
	</pre>		</pre>

	~~other approaches:~~
	* you can also have a public method that takes an array, and a private method that copies the array into some other data structure (for example, a queue or a stack) to make it easier to pop elements/etc
	* you can either make left and right halves a copy,
	* or you can... make your algorithm do an in-place shuffle that would get more complicated

	==Flags==		==Flags==

Admin: /* Merge sort function - recursive */

2019-02-01T05:30:11Z

Merge sort function - recursive

← Older revision		Revision as of 05:30, 1 February 2019
Line 67:		Line 67:
	Successively splitting the array to sort into left and right halves; calling merge sort function on each half, merging the sorted halves.		Successively splitting the array to sort into left and right halves; calling merge sort function on each half, merging the sorted halves.

	To split in half, take the length (number of elements), divide by two, and round down to the nearest integer. This gives you the element that starts the second half of the array. Left half = everything up to but not including the mid index, right half = everything including the mid index through the end of the array		To split in half, take the length (number of elements), divide by two, and round down to the nearest integer. This gives you the element that starts the second half of the array.

			Left half = everything up to but not including the mid index, right half = everything including the mid index through the end of the array

	<pre>		<pre>

Admin: /* Merge sort function */

2019-02-01T05:29:47Z

Merge sort function

← Older revision		Revision as of 05:29, 1 February 2019
Line 59:		Line 59:
	</pre>		</pre>

	===Merge sort function===		===Merge sort function - recursive===

	~~NOTE: this will require you to be able to do rounding (math.ceil, math.floor).~~

	~~'''Recursive Merge Sort:'''~~

	Recursive merge sort starts with an input array. It splits the array in half. It recursively calls merge sort on the left and right halves. It then merges the left and right halves into a final result array and returns it.		Recursive merge sort starts with an input array. It splits the array in half. It recursively calls merge sort on the left and right halves. It then merges the left and right halves into a final result array and returns it.

	The base case of this recursive ~~array~~ is if the length of the array to sort is 1 or 0, in which case no recursive call to sort or merge the array halves is needed.		The base case of this recursive method is if the length of the array to sort is 1 or 0, in which case no recursive call to sort or merge the array halves is needed.

	Successively splitting the array to sort into left and right halves; calling merge sort function on each half, merging the sorted halves.		Successively splitting the array to sort into left and right halves; calling merge sort function on each half, merging the sorted halves.

Admin: /* Merge two arrays function */

2019-02-01T05:29:10Z

Merge two arrays function

← Older revision		Revision as of 05:29, 1 February 2019
Line 16:		Line 16:
	==Merge Sort Algorithm Pseudocode==		==Merge Sort Algorithm Pseudocode==

	===Merge two arrays function===		===Merge two arrays function using pop===

	The key to writing the <code>mergeTwoArrays()</code> function is to explicitly declare, up front, that the source and destination arrays are correctly sized.		The key to writing the <code>mergeTwoArrays()</code> function is to explicitly declare, up front, that the source and destination arrays are correctly sized.

			We can copy s1 and s2 into queue data structures that have peek/pop functionality:

	<pre>		<pre>
	function mergeTwoArrays (array[] s1, array[] s2, array[] dest) {		function mergeTwoArrays (array[] s1, array[] s2, array[] dest) {
	n_iterations = length of dest		n_iterations = length of dest
			q1 = populate queue from s1
			q2 = populate queue from s2
	for k = 0 to k = n_iterations - 1 {		for k = 0 to k = n_iterations - 1 {
	if ~~s1[0]~~ < ~~s2[0]~~ {		if q1.peek() < q2.peek() {
	front = s1.~~pop_front~~()		front = q1.pop()
	} else {		} else {
	front = s2.~~pop_front~~()		front = q2.pop()
	}		}
	dest[k] = front		dest[k] = front
	}		}
	return		return
Line 35:		Line 39:
	</pre>		</pre>

	This can be slightly modified so that we do not ~~do a pop operation~~, but rather keep track of two indices in s1 and s2:		This can be slightly modified so that we do not make copies, but rather keep track of two indices in s1 and s2:

	<pre>		<pre>
Line 54:		Line 58:
	}		}
	</pre>		</pre>


	===Merge sort function===		===Merge sort function===

Admin: /* Merge Sort Algorithm Notes */

2019-02-01T05:26:44Z

Merge Sort Algorithm Notes

← Older revision		Revision as of 05:26, 1 February 2019
Line 5:		Line 5:
	* How to implement a generics data structure (but start simple with integers or strings if up to you)		* How to implement a generics data structure (but start simple with integers or strings if up to you)
	* How to implement comparators for custom objects		* How to implement comparators for custom objects
			* How to pop from a data structure (queue-type data structure)
	* How to compute ceiling and floor functions		* How to compute ceiling and floor functions
	* How to do recursion (and limits to recursion)		* How to do recursion (and limits to recursion)