CS 412 Algorithm Analysis and Design - Chapter 7 Quicksort - PDF

Imam Abdulrahman Bin Faisal University College of Computer Science and Information Technology Department of Computer Science CS 412 Algorithm Analysis and Design Term 1 2021-2022 Chapter 7 Quicksort Instructors:...

Imam Abdulrahman Bin Faisal University College of Computer Science and Information Technology Department of Computer Science CS 412 Algorithm Analysis and Design Term 1 2021-2022 Chapter 7 Quicksort Instructors: Dr. Atta-ur-Rahman Summary of Sorting Algorithms Name Type Complexity Bubble Sort Iterative O(n^2) Insertion Sort Iterative O(n^2) Selection Iterative O(n^2) Merge Sort Divide and Conquer O(nlgn) extra space Heap Sort Divide and Conquer O(nlgn) in place Quick Sort Divide and Conquer O(n^2) – Worst case O(nlgn) – Average case 2 Outline Introduction. Divide and Conquer. (divide, conquer, combination) Partitioning Algorithm. Quicksort Algorithm. Running Time analysis. 3 Introduction Like merge sort, quicksort uses divide-and-conquer, and so it's a recursive algorithm. The way that quicksort uses divide-and- conquer is a little different from how merge sort does. o In merge sort, the divide step does hardly anything, and all the real work happens in the combine step. o Quicksort is the opposite: all the real work happens in the divide step. In fact, the combine step in quicksort does absolutely nothing. Quicksort has a couple of other differences from merge sort. o Sorts “in place” (like insertion sort, and the heapsort ). o Its worst-case running time is as bad as selection sort's and insertion sort's: Θ(n2). o But its average-case running time is as good as merge sort's: Θ(n log2 n). Quicksort is often the best practical choice for sorting because it is remarkably efficient on the average: o its expected running time is Θ(n log n). and the constant factors hidden in the Θ(n log n) notation are quite small. 4 OS – Page Replacement Algorithm Optimal Algorithm (best) Least Recently Used Algorithm (average) 5 Divide and conquer Quicksort an n-element array: 1. Divide: Partition the array A[p.. r] into two subarrays around a pivot x such that elements in lower subarray A[p.. q-1]