Quick Sort- Marge Sort.ppt

Quick sort is an internal algorithm which is based on divide and conquer strategy. In this:

The array of elements is divided into parts repeatedly until it is not possible to divide it further.
It is also known as “partition exchange sort”.
It uses a key element (pivot) for partitioning the elements.
One left partition contains all those elements that are smaller than the pivot and one right partition contains all those elements which are greater than the key element.divide and conquer strategy. In this:

The elements are split into two sub-arrays (n/2) again and again until only one element is left.
Merge sort uses additional storage for sorting the auxiliary array.
Merge sort uses three arrays where two are used for storing each half, and the third external one is used to store the final sorted list by merging other two and each array is then sorted recursively.
At last, the all sub arrays are merged to make it ‘n’ element size of the array. Quick Sort vs Merge Sort
Partition of elements in the array : In the merge sort, the array is parted into just 2 halves (i.e. n/2). whereas In case of quick sort, the array is parted into any ratio. There is no compulsion of dividing the array of elements into equal parts in quick sort.
Worst case complexity : The worst case complexity of quick sort is O(n^2) as there is need of lot of comparisons in the worst condition. whereas In merge sort, worst case and average case has same complexities O(n log n).
Usage with datasets : Merge sort can work well on any type of data sets irrespective of its size (either large or small). whereas The quick sort cannot work well with large datasets.
Additional storage space requirement : Merge sort is not in place because it requires additional memory space to store the auxiliary arrays. whereas The quick sort is in place as it doesn’t require any additional storage.
Efficiency : Merge sort is more efficient and works faster than quick sort in case of larger array size or datasets. whereas Quick sort is more efficient and works faster than merge sort in case of smaller array size or datasets.
Sorting method : The quick sort is internal sorting method where the data is sorted in main memory. whereas The merge sort is external sorting method in which the data that is to be sorted cannot be accommodated in the memory and needed auxiliary memory for sorting.
Stability : Merge sort is stable as two elements with equal value appear in the same order in sorted output as they were in the input unsorted array. whereas Quick sort is unstable in this scenario. But it can be made stable using some changes in code.
Preferred for : Quick sort is preferred for arrays. whereas Merge sort is preferred for linked lists.
Locality of reference : Quicksort exhibits good cache locality and this makes quicksort faster than merge sort (in many cases like in virtual memory environment).

1. Mergesort and Quicksort
Chapter 8
Kruse and Ryba

2. Sorting algorithms
•Insertion, selection and bubble sort have
quadratic worst-case performance
•The faster comparison based algorithm ?
O(nlogn)
•Mergesort and Quicksort

3. Merge Sort
•Apply divide-and-conquer to sorting problem
•Problem: Given nelements, sort elements into
non-decreasing order
•Divide-and-Conquer:
–If n=1 terminate (every one-element list is already
sorted)
–If n>1, partition elements into two or more sub-
collections; sort each; combine into a single sorted list
•How do we partition?

4. Partitioning -Choice 1
•First n-1 elements into set A, last element set B
•Sort A using this partitioning scheme recursively
–B already sorted
•Combine A and B using method Insert() (= insertion
into sorted array)
•Leads to recursive version of InsertionSort()
–Number of comparisons: O(n
2
)
•Best case = n-1
•Worst case = 2
)1(
2



nn
ic
n
i

5. Partitioning -Choice 2
•Put element with largest key in B, remaining elements
in A
•Sort A recursively
•To combine sorted A and B, append B to sorted A
–Use Max() to find largest element recursive
SelectionSort()
–Use bubbling process to find and move largest element to
right-most position recursive BubbleSort()
•All O(n
2
)

6. Partitioning -Choice 3
•Let’s try to achieve balanced partitioning
•A gets n/2 elements, B gets rest half
•Sort A and B recursively
•Combine sorted A and B using a process
called merge, which combines two sorted
lists into one
–How? We will see soon

7. Example
•Partition into lists of size n/2
[10, 4, 6, 3]
[10, 4, 6, 3, 8, 2, 5, 7]
[8, 2, 5, 7]
[10, 4][6, 3] [8, 2] [5, 7]
[4] [10][3][6] [2][8][5][7]

8. Example Cont’d
•Merge
[3, 4, 6, 10]
[2, 3, 4, 5, 6, 7, 8, 10 ]
[2, 5, 7, 8]
[4, 10][3, 6] [2, 8] [5, 7]
[4] [10][3][6] [2][8][5][7]

9. Static Method mergeSort()
Public static void mergeSort(Comparable []a, int left,
int right)
{
// sort a[left:right]
if (left < right)
{// at least two elements
int mid = (left+right)/2; //midpoint
mergeSort(a, left, mid);
mergeSort(a, mid + 1, right);
merge(a, b, left, mid, right); //merge from a to b
copy(b, a, left, right); //copy result back to a
}
}

10. Quicksort Algorithm
Given an array of nelements (e.g., integers):
•If array only contains one element, return
•Else
–pick one element to use as pivot.
–Partition elements into two sub-arrays:
•Elements less than or equal to pivot
•Elements greater than pivot
–Quicksort two sub-arrays
–Return results

11. Example
We are given array of n integers to sort:
402010806050730100

12. Pick Pivot Element
There are a number of ways to pick the pivot element. In this
example, we will use the first element in the array:
402010806050730100

13. Partitioning Array
Given a pivot, partition the elements of the array
such that the resulting array consists of:
1.One sub-array that contains elements >= pivot
2.Another sub-array that contains elements < pivot
The sub-arrays are stored in the original data array.
Partitioning loops through, swapping elements
below/above pivot.

14. 402010806050730100
pivot_index = 0
[0] [1] [2] [3] [4] [5] [6] [7] [8]
too_big_index too_small_index

15. 402010806050730100
pivot_index = 0
[0] [1] [2] [3] [4] [5] [6] [7] [8]
too_big_index too_small_index
1.While data[too_big_index] <= data[pivot]
++too_big_index

16. 402010806050730100
pivot_index = 0
[0] [1] [2] [3] [4] [5] [6] [7] [8]
too_big_index too_small_index
1.While data[too_big_index] <= data[pivot]
++too_big_index

17. 402010806050730100
pivot_index = 0
[0] [1] [2] [3] [4] [5] [6] [7] [8]
too_big_index too_small_index
1.While data[too_big_index] <= data[pivot]
++too_big_index

18. 402010806050730100
pivot_index = 0
[0] [1] [2] [3] [4] [5] [6] [7] [8]
too_big_index too_small_index
1.While data[too_big_index] <= data[pivot]
++too_big_index
2.While data[too_small_index] > data[pivot]
--too_small_index

19. 402010806050730100
pivot_index = 0
[0] [1] [2] [3] [4] [5] [6] [7] [8]
too_big_index too_small_index
1.While data[too_big_index] <= data[pivot]
++too_big_index
2.While data[too_small_index] > data[pivot]
--too_small_index

20. 402010806050730100
pivot_index = 0
[0] [1] [2] [3] [4] [5] [6] [7] [8]
too_big_index too_small_index
1.While data[too_big_index] <= data[pivot]
++too_big_index
2.While data[too_small_index] > data[pivot]
--too_small_index
3.If too_big_index < too_small_index
swap data[too_big_index] and data[too_small_index]

21. 402010306050780100
pivot_index = 0
[0] [1] [2] [3] [4] [5] [6] [7] [8]
too_big_index too_small_index
1.While data[too_big_index] <= data[pivot]
++too_big_index
2.While data[too_small_index] > data[pivot]
--too_small_index
3.If too_big_index < too_small_index
swap data[too_big_index] and data[too_small_index]

22. 402010306050780100
pivot_index = 0
[0] [1] [2] [3] [4] [5] [6] [7] [8]
too_big_index too_small_index
1.While data[too_big_index] <= data[pivot]
++too_big_index
2.While data[too_small_index] > data[pivot]
--too_small_index
3.If too_big_index < too_small_index
swap data[too_big_index] and data[too_small_index]
4.While too_small_index > too_big_index, go to 1.

23. 402010306050780100
pivot_index = 0
[0] [1] [2] [3] [4] [5] [6] [7] [8]
too_big_index too_small_index
1.While data[too_big_index] <= data[pivot]
++too_big_index
2.While data[too_small_index] > data[pivot]
--too_small_index
3.If too_big_index < too_small_index
swap data[too_big_index] and data[too_small_index]
4.While too_small_index > too_big_index, go to 1.

24. 402010306050780100
pivot_index = 0
[0] [1] [2] [3] [4] [5] [6] [7] [8]
too_big_indextoo_small_index
1.While data[too_big_index] <= data[pivot]
++too_big_index
2.While data[too_small_index] > data[pivot]
--too_small_index
3.If too_big_index < too_small_index
swap data[too_big_index] and data[too_small_index]
4.While too_small_index > too_big_index, go to 1.

25. 402010306050780100
pivot_index = 0
[0] [1] [2] [3] [4] [5] [6] [7] [8]
too_big_indextoo_small_index
1.While data[too_big_index] <= data[pivot]
++too_big_index
2.While data[too_small_index] > data[pivot]
--too_small_index
3.If too_big_index < too_small_index
swap data[too_big_index] and data[too_small_index]
4.While too_small_index > too_big_index, go to 1.

26. 402010306050780100
pivot_index = 0
[0] [1] [2] [3] [4] [5] [6] [7] [8]
too_big_indextoo_small_index
1.While data[too_big_index] <= data[pivot]
++too_big_index
2.While data[too_small_index] > data[pivot]
--too_small_index
3.If too_big_index < too_small_index
swap data[too_big_index] and data[too_small_index]
4.While too_small_index > too_big_index, go to 1.

27. 402010306050780100
pivot_index = 0
[0] [1] [2] [3] [4] [5] [6] [7] [8]
too_big_indextoo_small_index
1.While data[too_big_index] <= data[pivot]
++too_big_index
2.While data[too_small_index] > data[pivot]
--too_small_index
3.If too_big_index < too_small_index
swap data[too_big_index] and data[too_small_index]
4.While too_small_index > too_big_index, go to 1.

28. 1.While data[too_big_index] <= data[pivot]
++too_big_index
2.While data[too_small_index] > data[pivot]
--too_small_index
3.If too_big_index < too_small_index
swap data[too_big_index] and data[too_small_index]
4.While too_small_index > too_big_index, go to 1.
402010307506080100
pivot_index = 0
[0] [1] [2] [3] [4] [5] [6] [7] [8]
too_big_indextoo_small_index

29. 1.While data[too_big_index] <= data[pivot]
++too_big_index
2.While data[too_small_index] > data[pivot]
--too_small_index
3.If too_big_index < too_small_index
swap data[too_big_index] and data[too_small_index]
4.While too_small_index > too_big_index, go to 1.
402010307506080100
pivot_index = 0
[0] [1] [2] [3] [4] [5] [6] [7] [8]
too_big_indextoo_small_index

30. 1.While data[too_big_index] <= data[pivot]
++too_big_index
2.While data[too_small_index] > data[pivot]
--too_small_index
3.If too_big_index < too_small_index
swap data[too_big_index] and data[too_small_index]
4.While too_small_index > too_big_index, go to 1.
402010307506080100
pivot_index = 0
[0] [1] [2] [3] [4] [5] [6] [7] [8]
too_big_indextoo_small_index

31. 1.While data[too_big_index] <= data[pivot]
++too_big_index
2.While data[too_small_index] > data[pivot]
--too_small_index
3.If too_big_index < too_small_index
swap data[too_big_index] and data[too_small_index]
4.While too_small_index > too_big_index, go to 1.
402010307506080100
pivot_index = 0
[0] [1] [2] [3] [4] [5] [6] [7] [8]
too_big_indextoo_small_index

32. 1.While data[too_big_index] <= data[pivot]
++too_big_index
2.While data[too_small_index] > data[pivot]
--too_small_index
3.If too_big_index < too_small_index
swap data[too_big_index] and data[too_small_index]
4.While too_small_index > too_big_index, go to 1.
402010307506080100
pivot_index = 0
[0] [1] [2] [3] [4] [5] [6] [7] [8]
too_big_indextoo_small_index

33. 1.While data[too_big_index] <= data[pivot]
++too_big_index
2.While data[too_small_index] > data[pivot]
--too_small_index
3.If too_big_index < too_small_index
swap data[too_big_index] and data[too_small_index]
4.While too_small_index > too_big_index, go to 1.
402010307506080100
pivot_index = 0
[0] [1] [2] [3] [4] [5] [6] [7] [8]
too_big_indextoo_small_index

34. 1.While data[too_big_index] <= data[pivot]
++too_big_index
2.While data[too_small_index] > data[pivot]
--too_small_index
3.If too_big_index < too_small_index
swap data[too_big_index] and data[too_small_index]
4.While too_small_index > too_big_index, go to 1.
402010307506080100
pivot_index = 0
[0] [1] [2] [3] [4] [5] [6] [7] [8]
too_big_indextoo_small_index

35. 1.While data[too_big_index] <= data[pivot]
++too_big_index
2.While data[too_small_index] > data[pivot]
--too_small_index
3.If too_big_index < too_small_index
swap data[too_big_index] and data[too_small_index]
4.While too_small_index > too_big_index, go to 1.
402010307506080100
pivot_index = 0
[0] [1] [2] [3] [4] [5] [6] [7] [8]
too_big_indextoo_small_index

36. 1.While data[too_big_index] <= data[pivot]
++too_big_index
2.While data[too_small_index] > data[pivot]
--too_small_index
3.If too_big_index < too_small_index
swap data[too_big_index] and data[too_small_index]
4.While too_small_index > too_big_index, go to 1.
402010307506080100
pivot_index = 0
[0] [1] [2] [3] [4] [5] [6] [7] [8]
too_big_indextoo_small_index

37. 1.While data[too_big_index] <= data[pivot]
++too_big_index
2.While data[too_small_index] > data[pivot]
--too_small_index
3.If too_big_index < too_small_index
swap data[too_big_index] and data[too_small_index]
4.While too_small_index > too_big_index, go to 1.
5.Swap data[too_small_index] and data[pivot_index]
402010307506080100
pivot_index = 0
[0] [1] [2] [3] [4] [5] [6] [7] [8]
too_big_indextoo_small_index

38. 1.While data[too_big_index] <= data[pivot]
++too_big_index
2.While data[too_small_index] > data[pivot]
--too_small_index
3.If too_big_index < too_small_index
swap data[too_big_index] and data[too_small_index]
4.While too_small_index > too_big_index, go to 1.
5.Swap data[too_small_index] and data[pivot_index]
720103040506080100pivot_index = 4
[0] [1] [2] [3] [4] [5] [6] [7] [8]
too_big_indextoo_small_index

39. Partition Result
720103040506080100
[0] [1] [2] [3] [4] [5] [6] [7] [8]
<= data[pivot]> data[pivot]

40. Recursion: Quicksort Sub-arrays
720103040506080100
[0] [1] [2] [3] [4] [5] [6] [7] [8]
<= data[pivot]> data[pivot]

41. Quicksort Analysis
•Assume that keys are random, uniformly
distributed.
•What is best case running time?

42. Quicksort Analysis
•Assume that keys are random, uniformly
distributed.
•What is best case running time?
–Recursion:
1.Partition splits array in two sub-arrays of size n/2
2.Quicksort each sub-array

43. Quicksort Analysis
•Assume that keys are random, uniformly
distributed.
•What is best case running time?
–Recursion:
1.Partition splits array in two sub-arrays of size n/2
2.Quicksort each sub-array
–Depth of recursion tree?

44. Quicksort Analysis
•Assume that keys are random, uniformly
distributed.
•What is best case running time?
–Recursion:
1.Partition splits array in two sub-arrays of size n/2
2.Quicksort each sub-array
–Depth of recursion tree? O(log
2n)

45. Quicksort Analysis
•Assume that keys are random, uniformly
distributed.
•What is best case running time?
–Recursion:
1.Partition splits array in two sub-arrays of size n/2
2.Quicksort each sub-array
–Depth of recursion tree? O(log
2n)
–Number of accesses in partition?

46. Quicksort Analysis
•Assume that keys are random, uniformly
distributed.
•What is best case running time?
–Recursion:
1.Partition splits array in two sub-arrays of size n/2
2.Quicksort each sub-array
–Depth of recursion tree? O(log
2n)
–Number of accesses in partition? O(n)

47. Quicksort Analysis
•Assume that keys are random, uniformly
distributed.
•Best case running time: O(n log
2n)

48. Quicksort Analysis
•Assume that keys are random, uniformly
distributed.
•Best case running time: O(n log
2n)
•Worst case running time?

49. Quicksort: Worst Case
•Assume first element is chosen as pivot.
•Assume we get array that is already in
order:
24101213505763100
pivot_index = 0
[0] [1] [2] [3] [4] [5] [6] [7] [8]
too_big_index too_small_index

50. 1.While data[too_big_index] <= data[pivot]
++too_big_index
2.While data[too_small_index] > data[pivot]
--too_small_index
3.If too_big_index < too_small_index
swap data[too_big_index] and data[too_small_index]
4.While too_small_index > too_big_index, go to 1.
5.Swap data[too_small_index] and data[pivot_index]
24101213505763100
pivot_index = 0
[0] [1] [2] [3] [4] [5] [6] [7] [8]
too_big_index too_small_index

51. 1.While data[too_big_index] <= data[pivot]
++too_big_index
2.While data[too_small_index] > data[pivot]
--too_small_index
3.If too_big_index < too_small_index
swap data[too_big_index] and data[too_small_index]
4.While too_small_index > too_big_index, go to 1.
5.Swap data[too_small_index] and data[pivot_index]
24101213505763100
pivot_index = 0
[0] [1] [2] [3] [4] [5] [6] [7] [8]
too_big_index too_small_index

52. 1.While data[too_big_index] <= data[pivot]
++too_big_index
2.While data[too_small_index] > data[pivot]
--too_small_index
3.If too_big_index < too_small_index
swap data[too_big_index] and data[too_small_index]
4.While too_small_index > too_big_index, go to 1.
5.Swap data[too_small_index] and data[pivot_index]
24101213505763100
pivot_index = 0
[0] [1] [2] [3] [4] [5] [6] [7] [8]
too_big_index too_small_index

53. 1.While data[too_big_index] <= data[pivot]
++too_big_index
2.While data[too_small_index] > data[pivot]
--too_small_index
3.If too_big_index < too_small_index
swap data[too_big_index] and data[too_small_index]
4.While too_small_index > too_big_index, go to 1.
5.Swap data[too_small_index] and data[pivot_index]
24101213505763100
pivot_index = 0
[0] [1] [2] [3] [4] [5] [6] [7] [8]
too_big_index too_small_index

54. 1.While data[too_big_index] <= data[pivot]
++too_big_index
2.While data[too_small_index] > data[pivot]
--too_small_index
3.If too_big_index < too_small_index
swap data[too_big_index] and data[too_small_index]
4.While too_small_index > too_big_index, go to 1.
5.Swap data[too_small_index] and data[pivot_index]
24101213505763100
pivot_index = 0
[0] [1] [2] [3] [4] [5] [6] [7] [8]
too_big_index too_small_index

55. 1.While data[too_big_index] <= data[pivot]
++too_big_index
2.While data[too_small_index] > data[pivot]
--too_small_index
3.If too_big_index < too_small_index
swap data[too_big_index] and data[too_small_index]
4.While too_small_index > too_big_index, go to 1.
5.Swap data[too_small_index] and data[pivot_index]
24101213505763100
pivot_index = 0
[0] [1] [2] [3] [4] [5] [6] [7] [8]
too_big_index too_small_index

56. 1.While data[too_big_index] <= data[pivot]
++too_big_index
2.While data[too_small_index] > data[pivot]
--too_small_index
3.If too_big_index < too_small_index
swap data[too_big_index] and data[too_small_index]
4.While too_small_index > too_big_index, go to 1.
5.Swap data[too_small_index] and data[pivot_index]
24101213505763100
pivot_index = 0
[0] [1] [2] [3] [4] [5] [6] [7] [8]
> data[pivot]<= data[pivot]

57. Quicksort Analysis
•Assume that keys are random, uniformly
distributed.
•Best case running time: O(n log
2n)
•Worst case running time?
–Recursion:
1.Partition splits array in two sub-arrays:
•one sub-array of size 0
•the other sub-array of size n-1
2.Quicksort each sub-array
–Depth of recursion tree?

58. Quicksort Analysis
•Assume that keys are random, uniformly
distributed.
•Best case running time: O(n log
2n)
•Worst case running time?
–Recursion:
1.Partition splits array in two sub-arrays:
•one sub-array of size 0
•the other sub-array of size n-1
2.Quicksort each sub-array
–Depth of recursion tree? O(n)

59. Quicksort Analysis
•Assume that keys are random, uniformly
distributed.
•Best case running time: O(n log
2n)
•Worst case running time?
–Recursion:
1.Partition splits array in two sub-arrays:
•one sub-array of size 0
•the other sub-array of size n-1
2.Quicksort each sub-array
–Depth of recursion tree? O(n)
–Number of accesses per partition?

60. Quicksort Analysis
•Assume that keys are random, uniformly
distributed.
•Best case running time: O(n log
2n)
•Worst case running time?
–Recursion:
1.Partition splits array in two sub-arrays:
•one sub-array of size 0
•the other sub-array of size n-1
2.Quicksort each sub-array
–Depth of recursion tree? O(n)
–Number of accesses per partition? O(n)

61. Quicksort Analysis
•Assume that keys are random, uniformly
distributed.
•Best case running time: O(n log
2n)
•Worst case running time: O(n
2
)!!!

62. Quicksort Analysis
•Assume that keys are random, uniformly
distributed.
•Best case running time: O(n log
2n)
•Worst case running time: O(n
2
)!!!
•What can we do to avoid worst case?

63. Improved Pivot Selection
Pick median value of three elements from data array:
data[0], data[n/2], and data[n-1].
Use this median value as pivot.

64. Improving Performance of
Quicksort
•Improved selection of pivot.
•For sub-arrays of size 3 or less, apply brute
force search:
–Sub-array of size 1: trivial
–Sub-array of size 2:
•if(data[first] > data[second]) swap them
–Sub-array of size 3: left as an exercise.