Understanding the Quicksort Algorithm

Slide Note
Embed
Share

Quicksort is a widely used sorting algorithm that operates by partitioning an array into smaller subarrays. The `public.static.int.partition` method plays a crucial role in Quicksort by selecting a pivot element and rearranging elements around it based on their values. This process creates a split between elements less than the pivot and those greater than it, leading to a sorted array. Visualization and explanation of the partitioning step with examples like `5, 7, 1, 2, 8, 4, 3, 6` help in grasping the essence of Quicksort.

wild_i
wild_i Follow

Uploaded on Sep 28, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

E N D

Presentation Transcript

  1. Quicksort David Kauchak cs201 Spring 2014

  2. public static int partition(double[] nums, int start, int end){ int lessThanIndex = start-1; for( int i = start; i < end; i++ ){ if( nums[i] <= nums[end] ){ lessThanIndex++; swap(nums, lessThanIndex, i); } } swap(nums, lessThanIndex+1, end); return lessThanIndex+1; } what does this method do?

  3. public static int partition(double[] nums, int start, int end){ int lessThanIndex = start-1; for( int i = start; i < end; i++ ){ if( nums[i] <= nums[end] ){ lessThanIndex++; swap(nums, lessThanIndex, i); } } swap(nums, lessThanIndex+1, end); return lessThanIndex+1; } nums[end] is called the pivot Partitions the elements nums[start end-1] in to two sets, those pivot and those > pivot Operates in place Final result: start pivot end nums > pivot pivot

  4. 5 7 1 2 8 4 3 6 start end public static int partition(double[] nums, int start, int end){ int lessThanIndex = start-1; for( int i = start; i < end; i++ ){ if( nums[i] <= nums[end] ){ lessThanIndex++; swap(nums, lessThanIndex, i); } } swap(nums, lessThanIndex+1, end); return lessThanIndex+1; }

  5. lessThanIndex 5 7 1 2 8 4 3 6 start end public static int partition(double[] nums, int start, int end){ int lessThanIndex = start-1; for( int i = start; i < end; i++ ){ if( nums[i] <= nums[end] ){ lessThanIndex++; swap(nums, lessThanIndex, i); } } swap(nums, lessThanIndex+1, end); return lessThanIndex+1; }

  6. lessThanIndex i 5 7 1 2 8 4 3 6 start end public static int partition(double[] nums, int start, int end){ int lessThanIndex = start-1; for( int i = start; i < end; i++ ){ if( nums[i] <= nums[end] ){ lessThanIndex++; swap(nums, lessThanIndex, i); } } swap(nums, lessThanIndex+1, end); return lessThanIndex+1; }

  7. lessThanIndex i 5 7 1 2 8 4 3 6 start end public static int partition(double[] nums, int start, int end){ int lessThanIndex = start-1; for( int i = start; i < end; i++ ){ if( nums[i] <= nums[end] ){ lessThanIndex++; swap(nums, lessThanIndex, i); } } swap(nums, lessThanIndex+1, end); return lessThanIndex+1; }

  8. lessThanIndex i 5 7 1 2 8 4 3 6 start end public static int partition(double[] nums, int start, int end){ int lessThanIndex = start-1; for( int i = start; i < end; i++ ){ if( nums[i] <= nums[end] ){ lessThanIndex++; swap(nums, lessThanIndex, i); } } swap(nums, lessThanIndex+1, end); return lessThanIndex+1; }

  9. lessThanIndex i 5 7 1 2 8 4 3 6 start end public static int partition(double[] nums, int start, int end){ int lessThanIndex = start-1; for( int i = start; i < end; i++ ){ if( nums[i] <= nums[end] ){ lessThanIndex++; swap(nums, lessThanIndex, i); } } swap(nums, lessThanIndex+1, end); return lessThanIndex+1; }

  10. lessThanIndex i 5 7 1 2 8 4 3 6 start end public static int partition(double[] nums, int start, int end){ int lessThanIndex = start-1; for( int i = start; i < end; i++ ){ if( nums[i] <= nums[end] ){ lessThanIndex++; swap(nums, lessThanIndex, i); } } swap(nums, lessThanIndex+1, end); return lessThanIndex+1; }

  11. lessThanIndex i 5 7 1 2 8 4 3 6 start end public static int partition(double[] nums, int start, int end){ int lessThanIndex = start-1; for( int i = start; i < end; i++ ){ if( nums[i] <= nums[end] ){ lessThanIndex++; swap(nums, lessThanIndex, i); } } swap(nums, lessThanIndex+1, end); return lessThanIndex+1; }

  12. lessThanIndex i 5 7 1 2 8 4 3 6 start end public static int partition(double[] nums, int start, int end){ int lessThanIndex = start-1; for( int i = start; i < end; i++ ){ if( nums[i] <= nums[end] ){ lessThanIndex++; swap(nums, lessThanIndex, i); } } swap(nums, lessThanIndex+1, end); return lessThanIndex+1; }

  13. lessThanIndex i 5 1 7 2 8 4 3 6 start end public static int partition(double[] nums, int start, int end){ int lessThanIndex = start-1; for( int i = start; i < end; i++ ){ if( nums[i] <= nums[end] ){ lessThanIndex++; swap(nums, lessThanIndex, i); } } swap(nums, lessThanIndex+1, end); return lessThanIndex+1; }

  14. lessThanIndex i 5 1 7 2 8 4 3 6 start end public static int partition(double[] nums, int start, int end){ int lessThanIndex = start-1; for( int i = start; i < end; i++ ){ if( nums[i] <= nums[end] ){ lessThanIndex++; swap(nums, lessThanIndex, i); } } swap(nums, lessThanIndex+1, end); return lessThanIndex+1; }

  15. lessThanIndex i 5 1 7 2 8 4 3 6 start end public static int partition(double[] nums, int start, int end){ int lessThanIndex = start-1; for( int i = start; i < end; i++ ){ if( nums[i] <= nums[end] ){ lessThanIndex++; swap(nums, lessThanIndex, i); } } swap(nums, lessThanIndex+1, end); return lessThanIndex+1; }

  16. lessThanIndex i 5 1 2 7 8 4 3 6 start end public static int partition(double[] nums, int start, int end){ int lessThanIndex = start-1; for( int i = start; i < end; i++ ){ if( nums[i] <= nums[end] ){ lessThanIndex++; swap(nums, lessThanIndex, i); } } swap(nums, lessThanIndex+1, end); return lessThanIndex+1; }

  17. lessThanIndex i 5 1 2 7 8 4 3 6 start end public static int partition(double[] nums, int start, int end){ int lessThanIndex = start-1; for( int i = start; i < end; i++ ){ if( nums[i] <= nums[end] ){ lessThanIndex++; swap(nums, lessThanIndex, i); } } swap(nums, lessThanIndex+1, end); return lessThanIndex+1; }

  18. lessThanIndex i 5 1 2 7 8 4 3 6 start end public static int partition(double[] nums, int start, int end){ int lessThanIndex = start-1; for( int i = start; i < end; i++ ){ if( nums[i] <= nums[end] ){ lessThanIndex++; swap(nums, lessThanIndex, i); } } swap(nums, lessThanIndex+1, end); return lessThanIndex+1; }

  19. lessThanIndex i 5 1 2 7 8 4 3 6 start end What s happening?

  20. lessThanIndex i 5 1 2 7 8 4 3 6 start end > pivot unprocessed pivot

  21. lessThanIndex i 5 1 2 7 8 4 3 6 start end public static int partition(double[] nums, int start, int end){ int lessThanIndex = start-1; for( int i = start; i < end; i++ ){ if( nums[i] <= nums[end] ){ lessThanIndex++; swap(nums, lessThanIndex, i); } } swap(nums, lessThanIndex+1, end); return lessThanIndex+1; }

  22. lessThanIndex i 5 1 2 4 8 7 3 6 start end public static int partition(double[] nums, int start, int end){ int lessThanIndex = start-1; for( int i = start; i < end; i++ ){ if( nums[i] <= nums[end] ){ lessThanIndex++; swap(nums, lessThanIndex, i); } } swap(nums, lessThanIndex+1, end); return lessThanIndex+1; }

  23. lessThanIndex i 5 1 2 4 3 7 8 6 start end public static int partition(double[] nums, int start, int end){ int lessThanIndex = start-1; for( int i = start; i < end; i++ ){ if( nums[i] <= nums[end] ){ lessThanIndex++; swap(nums, lessThanIndex, i); } } swap(nums, lessThanIndex+1, end); return lessThanIndex+1; }

  24. lessThanIndex i 5 1 2 4 3 6 8 7 start end public static int partition(double[] nums, int start, int end){ int lessThanIndex = start-1; for( int i = start; i < end; i++ ){ if( nums[i] <= nums[end] ){ lessThanIndex++; swap(nums, lessThanIndex, i); } } swap(nums, lessThanIndex+1, end); return lessThanIndex+1; }

  25. Partition running time? O(n) public static int partition(double[] nums, int start, int end){ int lessThanIndex = start-1; for( int i = start; i < end; i++ ){ if( nums[i] <= nums[end] ){ lessThanIndex++; swap(nums, lessThanIndex, i); } } swap(nums, lessThanIndex+1, end); return lessThanIndex+1; }

  26. Quicksort How can we use this method to sort nums? public static int partition(double[] nums, int start, int end){ int lessThanIndex = start-1; for( int i = start; i < end; i++ ){ if( nums[i] <= nums[end] ){ lessThanIndex++; swap(nums, lessThanIndex, i); } } swap(nums, lessThanIndex+1, end); return lessThanIndex+1; }

  27. Quicksort private static void quicksortHelper(double[] nums, int start, int end){ if( start < end ){ int partition = partition(nums, start, end); quicksortHelper(nums, start, partition-1); quicksortHelper(nums, partition+1, end); } } public static int partition(double[] nums, int start, int end){ int lessThanIndex = start-1; for( int i = start; i < end; i++ ){ if( nums[i] <= nums[end] ){ lessThanIndex++; swap(nums, lessThanIndex, i); } } swap(nums, lessThanIndex+1, end); return lessThanIndex+1; }

  28. 8 5 1 3 6 2 7 4 private static void quicksortHelper(double[] nums, int start, int end){ if( start < end ){ int partition = partition(nums, start, end); quicksortHelper(nums, start, partition-1); quicksortHelper(nums, partition+1, end); } }

  29. 8 5 1 3 6 2 7 4 private static void quicksortHelper(double[] nums, int start, int end){ if( start < end ){ int partition = partition(nums, start, end); quicksortHelper(nums, start, partition-1); quicksortHelper(nums, partition+1, end); } }

  30. 1 3 2 4 6 8 7 5 private static void quicksortHelper(double[] nums, int start, int end){ if( start < end ){ int partition = partition(nums, start, end); quicksortHelper(nums, start, partition-1); quicksortHelper(nums, partition+1, end); } }

  31. 1 3 2 4 6 8 7 5 private static void quicksortHelper(double[] nums, int start, int end){ if( start < end ){ int partition = partition(nums, start, end); quicksortHelper(nums, start, partition-1); quicksortHelper(nums, partition+1, end); } }

  32. 1 3 2 4 6 8 7 5 private static void quicksortHelper(double[] nums, int start, int end){ if( start < end ){ int partition = partition(nums, start, end); quicksortHelper(nums, start, partition-1); quicksortHelper(nums, partition+1, end); } }

  33. 1 2 3 4 6 8 7 5 private static void quicksortHelper(double[] nums, int start, int end){ if( start < end ){ int partition = partition(nums, start, end); quicksortHelper(nums, start, partition-1); quicksortHelper(nums, partition+1, end); } }

  34. 1 2 3 4 6 8 7 5 private static void quicksortHelper(double[] nums, int start, int end){ if( start < end ){ int partition = partition(nums, start, end); quicksortHelper(nums, start, partition-1); quicksortHelper(nums, partition+1, end); } }

  35. 1 2 3 4 6 8 7 5 private static void quicksortHelper(double[] nums, int start, int end){ if( start < end ){ int partition = partition(nums, start, end); quicksortHelper(nums, start, partition-1); quicksortHelper(nums, partition+1, end); } }

  36. 1 2 3 4 6 8 7 5 private static void quicksortHelper(double[] nums, int start, int end){ if( start < end ){ int partition = partition(nums, start, end); quicksortHelper(nums, start, partition-1); quicksortHelper(nums, partition+1, end); } }

  37. 1 2 3 4 6 8 7 5 private static void quicksortHelper(double[] nums, int start, int end){ if( start < end ){ int partition = partition(nums, start, end); quicksortHelper(nums, start, partition-1); quicksortHelper(nums, partition+1, end); } }

  38. 1 2 3 4 5 8 7 6 What happens here? private static void quicksortHelper(double[] nums, int start, int end){ if( start < end ){ int partition = partition(nums, start, end); quicksortHelper(nums, start, partition-1); quicksortHelper(nums, partition+1, end); } }

  39. 1 2 3 4 5 8 7 6 private static void quicksortHelper(double[] nums, int start, int end){ if( start < end ){ int partition = partition(nums, start, end); quicksortHelper(nums, start, partition-1); quicksortHelper(nums, partition+1, end); } }

  40. 1 2 3 4 5 8 7 6 private static void quicksortHelper(double[] nums, int start, int end){ if( start < end ){ int partition = partition(nums, start, end); quicksortHelper(nums, start, partition-1); quicksortHelper(nums, partition+1, end); } }

  41. 1 2 3 4 5 6 7 8 private static void quicksortHelper(double[] nums, int start, int end){ if( start < end ){ int partition = partition(nums, start, end); quicksortHelper(nums, start, partition-1); quicksortHelper(nums, partition+1, end); } }

  42. 1 2 3 4 5 6 7 8 private static void quicksortHelper(double[] nums, int start, int end){ if( start < end ){ int partition = partition(nums, start, end); quicksortHelper(nums, start, partition-1); quicksortHelper(nums, partition+1, end); } }

  43. Running time of Quicksort? Worst case? Each call to Partition splits the array into an empty array and n-1 array

  44. Quicksort: Worst case running time n-1 + n-2 + n-3 + + 1 = O(n2) When does this happen? sorted reverse sorted near sorted/reverse sorted

  45. Quicksort best case? Each call to Partition splits the array into two equal parts How much work is done at each level , i.e. running time of a level? O(n)

  46. Quicksort best case? Each call to Partition splits the array into two equal parts How many levels are there? Similar to binary search, each call to Partition will throw away half the data until we re down to one element: log2 n levels

  47. Quicksort best case? Each call to Partition splits the array into two equal parts Overall runtime? O(n log n)

  48. Quicksort Average case? Two intuitions As long as the Partition procedure always splits the array into some constant ratio between the left and the right, say L-to-R, e.g. 9-to-1, then we maintain O(n log n) As long as we only have a constant number of bad partitions intermixed with a good partition then we maintain O(n log n)

  49. How can we avoid the worst case? Inject randomness into the data private static void randomizedPartition(double[] nums, int start, int end){ int i = random(start, end); swap(nums, i, end); return partition = partition(nums, start, end); } Randomized quicksort is average case O(n log n)

  50. What is the wost case running time of randomized Quicksort? O(n2) We could still get very unlucky and pick bad partitions at every step

Related


Algorithm Analysis

Algorithm Analysis

aram
Understanding Booth's Algorithm for Binary Integer Division

Understanding Booth's Algorithm for Binary Integer Division

yara
Understanding Stable Matchings and the Gale-Shapley Algorithm

Understanding Stable Matchings and the Gale-Shapley Algorithm

romi
Ricart and Agrawala's Algorithm for Mutual Exclusion

Ricart and Agrawala's Algorithm for Mutual Exclusion

ianis
Understanding Algorithm Efficiency Analysis

Understanding Algorithm Efficiency Analysis

vela
Understanding Lamport Algorithm for Mutual Exclusion

Understanding Lamport Algorithm for Mutual Exclusion

solene
Digital Differential Analyzer (DDA) Algorithm in Computer Graphics

Digital Differential Analyzer (DDA) Algorithm in Computer Graphics

talitha
Grey Wolf Optimizer: A Nature-Inspired Optimization Algorithm

Grey Wolf Optimizer: A Nature-Inspired Optimization Algorithm

deust
Emergency Paediatric Tracheostomy Management Algorithm

Emergency Paediatric Tracheostomy Management Algorithm

krystian
Development of Satellite Passive Microwave Snowfall Detection Algorithm

Development of Satellite Passive Microwave Snowfall Detection Algorithm

chizi
Understanding Euclid's Algorithm: An Ancient Approach to Finding Greatest Common Divisors

Understanding Euclid's Algorithm: An Ancient Approach to Finding Greatest Common Divisors

rive_l
GPU Accelerated Algorithm for 3D Delaunay Triangulation

GPU Accelerated Algorithm for 3D Delaunay Triangulation

aleksan
Introduction to QuickSort Algorithm

Introduction to QuickSort Algorithm

jane781
Cuckoo Search: A Nature-Inspired Optimization Algorithm

Cuckoo Search: A Nature-Inspired Optimization Algorithm

liss_n
Ford-Fulkerson Algorithm for Maximum Flow in Networks

Ford-Fulkerson Algorithm for Maximum Flow in Networks

fenn_t
3GPP Voting Rights Algorithm: Contiguous-3 Solution Evaluation

3GPP Voting Rights Algorithm: Contiguous-3 Solution Evaluation

adebr
Review of Common Algorithms and Probability in Computer Science

Review of Common Algorithms and Probability in Computer Science

smuss
Introduction to Algorithm Analysis and Complexity in Computer Science

Introduction to Algorithm Analysis and Complexity in Computer Science

mama
Bresenham Line Drawing Algorithm Explained with Examples

Bresenham Line Drawing Algorithm Explained with Examples

alan_21
Understanding Divide and Conquer Sorting at Otterbein University

Understanding Divide and Conquer Sorting at Otterbein University

mish_3
Algorithm Strategies: Greedy Algorithms and the Coin-changing Problem

Algorithm Strategies: Greedy Algorithms and the Coin-changing Problem

ser_fer
Stable Matching Problem and Gale-Shapley Algorithm Overview

Stable Matching Problem and Gale-Shapley Algorithm Overview

dem_k

More Related Content