際際滷

際際滷Share a Scribd company logo

Quicksort algorithm

Download as PPTX, PDF
Bapan Maity
Bapan Maity

The quicksort algorithm sorts an array by recursively dividing it into smaller sub-arrays by picking a pivot element. It partitions the array into two halves based on the pivot, putting elements less than the pivot in one half and greater elements in the other. The process is then repeated on each sub-array until the entire array is sorted. It works by first choosing a pivot element, partitioning the array around the pivot so that elements less than the pivot come before elements greater than it, and then quicksorting the two resulting sub-arrays.

1 of 31
Downloaded 19 times
Quicksort Algorithm Given an array of n elements (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
Example We are given array of n integers to sort: 40 20 10 80 60 50 7 30 100
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: 40 20 10 80 60 50 7 30 100
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.
40 20 10 80 60 50 7 30 100pivot_index = 0 [0] [1] [2] [3] [4] [5] [6] [7] [8] too_big_index too_small_index
40 20 10 80 60 50 7 30 100pivot_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
40 20 10 80 60 50 7 30 100pivot_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
40 20 10 80 60 50 7 30 100pivot_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
40 20 10 80 60 50 7 30 100pivot_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
40 20 10 80 60 50 7 30 100pivot_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
40 20 10 80 60 50 7 30 100pivot_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]
40 20 10 30 60 50 7 80 100pivot_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]
40 20 10 30 60 50 7 80 100pivot_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.
40 20 10 30 60 50 7 80 100pivot_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.
40 20 10 30 60 50 7 80 100pivot_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.
40 20 10 30 60 50 7 80 100pivot_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.
40 20 10 30 60 50 7 80 100pivot_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.
40 20 10 30 60 50 7 80 100pivot_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.
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. 40 20 10 30 7 50 60 80 100pivot_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. 40 20 10 30 7 50 60 80 100pivot_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. 40 20 10 30 7 50 60 80 100pivot_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. 40 20 10 30 7 50 60 80 100pivot_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. 40 20 10 30 7 50 60 80 100pivot_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. 40 20 10 30 7 50 60 80 100pivot_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. 40 20 10 30 7 50 60 80 100pivot_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. 40 20 10 30 7 50 60 80 100pivot_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. 40 20 10 30 7 50 60 80 100pivot_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. 5. Swap data[too_small_index] and data[pivot_index] 40 20 10 30 7 50 60 80 100pivot_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. 5. Swap data[too_small_index] and data[pivot_index] 7 20 10 30 40 50 60 80 100pivot_index = 4 [0] [1] [2] [3] [4] [5] [6] [7] [8] too_big_index too_small_index
Partition Result 7 20 10 30 40 50 60 80 100 [0] [1] [2] [3] [4] [5] [6] [7] [8] <= data[pivot] > data[pivot]
Recursion: Quicksort Sub-arrays 7 20 10 30 40 50 60 80 100 [0] [1] [2] [3] [4] [5] [6] [7] [8] <= data[pivot] > data[pivot]

More Related Content

Quicksort algorithm

  • 1. Quicksort Algorithm Given an array of n elements (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
  • 2. Example We are given array of n integers to sort: 40 20 10 80 60 50 7 30 100
  • 3. 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: 40 20 10 80 60 50 7 30 100
  • 4. 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.
  • 5. 40 20 10 80 60 50 7 30 100pivot_index = 0 [0] [1] [2] [3] [4] [5] [6] [7] [8] too_big_index too_small_index
  • 6. 40 20 10 80 60 50 7 30 100pivot_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
  • 7. 40 20 10 80 60 50 7 30 100pivot_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
  • 8. 40 20 10 80 60 50 7 30 100pivot_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
  • 9. 40 20 10 80 60 50 7 30 100pivot_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
  • 10. 40 20 10 80 60 50 7 30 100pivot_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
  • 11. 40 20 10 80 60 50 7 30 100pivot_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]
  • 12. 40 20 10 30 60 50 7 80 100pivot_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]
  • 13. 40 20 10 30 60 50 7 80 100pivot_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.
  • 14. 40 20 10 30 60 50 7 80 100pivot_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.
  • 15. 40 20 10 30 60 50 7 80 100pivot_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.
  • 16. 40 20 10 30 60 50 7 80 100pivot_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.
  • 17. 40 20 10 30 60 50 7 80 100pivot_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.
  • 18. 40 20 10 30 60 50 7 80 100pivot_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.
  • 19. 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. 40 20 10 30 7 50 60 80 100pivot_index = 0 [0] [1] [2] [3] [4] [5] [6] [7] [8] too_big_index too_small_index
  • 20. 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. 40 20 10 30 7 50 60 80 100pivot_index = 0 [0] [1] [2] [3] [4] [5] [6] [7] [8] too_big_index too_small_index
  • 21. 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. 40 20 10 30 7 50 60 80 100pivot_index = 0 [0] [1] [2] [3] [4] [5] [6] [7] [8] too_big_index too_small_index
  • 22. 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. 40 20 10 30 7 50 60 80 100pivot_index = 0 [0] [1] [2] [3] [4] [5] [6] [7] [8] too_big_index too_small_index
  • 23. 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. 40 20 10 30 7 50 60 80 100pivot_index = 0 [0] [1] [2] [3] [4] [5] [6] [7] [8] too_big_index too_small_index
  • 24. 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. 40 20 10 30 7 50 60 80 100pivot_index = 0 [0] [1] [2] [3] [4] [5] [6] [7] [8] too_big_index too_small_index
  • 25. 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. 40 20 10 30 7 50 60 80 100pivot_index = 0 [0] [1] [2] [3] [4] [5] [6] [7] [8] too_big_index too_small_index
  • 26. 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. 40 20 10 30 7 50 60 80 100pivot_index = 0 [0] [1] [2] [3] [4] [5] [6] [7] [8] too_big_index too_small_index
  • 27. 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. 40 20 10 30 7 50 60 80 100pivot_index = 0 [0] [1] [2] [3] [4] [5] [6] [7] [8] too_big_index too_small_index
  • 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. 5. Swap data[too_small_index] and data[pivot_index] 40 20 10 30 7 50 60 80 100pivot_index = 0 [0] [1] [2] [3] [4] [5] [6] [7] [8] too_big_index too_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. 5. Swap data[too_small_index] and data[pivot_index] 7 20 10 30 40 50 60 80 100pivot_index = 4 [0] [1] [2] [3] [4] [5] [6] [7] [8] too_big_index too_small_index
  • 30. Partition Result 7 20 10 30 40 50 60 80 100 [0] [1] [2] [3] [4] [5] [6] [7] [8] <= data[pivot] > data[pivot]
  • 31. Recursion: Quicksort Sub-arrays 7 20 10 30 40 50 60 80 100 [0] [1] [2] [3] [4] [5] [6] [7] [8] <= data[pivot] > data[pivot]