Data Structures and Algorithms with Python: 100+ Coding Q&A (Code of Code) by Cakal Yasin

Author:Cakal, Yasin
Language: eng
Format: epub
Published: 2023-01-11T00:00:00+00:00

Let’s look at an example of Quicksort in action.

Example of Quicksort

Suppose we have a list of numbers: [8, 4, 1, 6, 5, 7, 3, 2] and we want to sort them in ascending order. We can use Quicksort to do this.

First, we select a pivot element. For this example, let’s select the first element, 8. Next, we partition the list around the pivot element. This means that we move all elements that are less than 8 to the left of 8 and all elements greater than 8 to the right of 8. This results in the following partitioned list: [4, 1, 6, 5, 7, 3, 2, 8].

Finally, we recursively sort the two parts. We apply Quicksort to the left part [4, 1, 6, 5, 7, 3, 2] and the right part [8]. This results in the following sorted list: [1, 2, 3, 4, 5, 6, 7, 8].

How does Quicksort Work?

Quicksort is an efficient sorting algorithm that uses a divide-and-conquer approach. It works by picking a pivot element from the array and then partitioning the array into two sub-arrays. The elements in the first sub-array are all less than the pivot element while the elements in the second sub-array are all greater than the pivot element. The two sub-arrays are then sorted recursively using quicksort until all elements in the array are sorted.

The steps of Quicksort are as follows:

Pick a pivot element from the array. This is usually the first or the last element.

Partition the array into two sub-arrays. All elements in the first sub-array should be less than the pivot element while all elements in the second sub-array should be greater than the pivot element.

Recursively apply Quicksort to the two sub-arrays.

When all elements in the sub-arrays have been sorted, combine the sorted sub-arrays and return the sorted array.

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.