Interview Preparation Quick Sort - Revision history

Proj user18 at 11:13, 1 December 2016

2016-12-01T11:13:58Z

Proj user18 at 11:13, 1 December 2016

2016-12-01T11:13:40Z

Proj user18 at 11:11, 1 December 2016

2016-12-01T11:11:19Z

Proj user18 at 13:22, 25 November 2016

2016-11-25T13:22:42Z

Proj user18: Created page with "Algorithm for implementation of quick sort is as follows a. Any element can be marked as a pivot but in this algorithm, I am using the starting index as a pivot. b. Divide..."

2016-11-25T12:38:49Z

Created page with "Algorithm for implementation of quick sort is as follows a. Any element can be marked as a pivot but in this algorithm, I am using the starting index as a pivot. b. Divide..."

New page

Algorithm for implementation of quick sort is as follows

a. Any element can be marked as a pivot but in this algorithm, I am using the starting index as a pivot.

b. Divide the array such that, All the element that are less than pivot are kept in one part and other are kept in another part.

c. Now pivot can be placed at its position between two parts.

d. consider only left part and repeat the step b and c until only one element is left.

e. consider right part and repeat step b,c,d and e until all the elements are sorted.

For an array with n number of elements,

Best case complexity = Average case complexity = O(n log n).

Worst case complexity = O(n^2).

@@ Line 9: / Line 9: @@
 d. consider only left part and repeat the steps a, b and c until only one element is left.
-e. consider right part and repeat step a, b,c ,d and e until all the elements are sorted.
+e. consider right part and repeat step a, b ,c ,d and e until all the elements are sorted.
 '''Code snippet'''

@@ Line 9: / Line 9: @@
 d. consider only left part and repeat the steps a, b and c until only one element is left.
-e. consider right part and repeat step b,c,d and e until all the elements are sorted.
+e. consider right part and repeat step a, b,c ,d and e until all the elements are sorted.
 '''Code snippet'''

← Older revision		Revision as of 13:22, 25 November 2016
Line 10:		Line 10:

	e. consider right part and repeat step b,c,d and e until all the elements are sorted.		e. consider right part and repeat step b,c,d and e until all the elements are sorted.
		+
		+	'''Code snippet'''
		+	<pre>
		+	if (start < end)
		+	{
		+	pivot = start;
		+	i = start;
		+	j = end;
		+	while (i < j)
		+	{
		+	while (array[i] <= array[pivot] && i <= end)
		+	{
		+	i++;
		+	}
		+	while (array[j] > array[pivot] && j >= start)
		+	{
		+	j--;
		+	}
		+	if (i < j)
		+	{
		+	temp = array[i];
		+	array[i] = array[j];
		+	array[j] = temp;
		+	}
		+	}
		+	temp = array[j];
		+	array[j] = array[pivot];
		+	array[pivot] = temp;
		+	quicksort(array, start, j - 1);
		+	quicksort(array, j + 1, end);
		+	}</pre>
		+

	For an array with n number of elements,		For an array with n number of elements,

@@ Line 7: / Line 7: @@
 c. Now pivot can be placed at its position between two parts.
-d. consider only left part and repeat the step b and c until only one element is left.
+d. consider only left part and repeat the steps a, b and c until only one element is left.
 e. consider right part and repeat step b,c,d and e until all the elements are sorted.