This blog post is a continuation of a series of blog posts about Algorithms, as it has been a hard concept for me to grasp as a programmer. Feel to check out the first blogpost about Algorithms, where I provide an introduction of what Algorithms are and an example of an algorithm and the second blog post about Data Structures, where I explained what are Data Structures and what are some types of Data Structures. Also check out the third blog post about Time Complexity and Space Complexity, which I provide an explanation of Time and Space Complexity. I have also written a blog post about Big O Notation. Recently I have written blog posts about Binary Search, Linear Search, Interpolation Search, Sorting Algorithms, Selection Sort, Insertion Sort and Merge Sort.
This blog post I will focus on Quick Sort. I will explain what Quick Sort is, how Quick Sort is associated with Algorithms, try to break down Quick Sort step by step and provide an example.
What is Quick Sort and how is it associated with Algorithms?
Quick Sort is a sorting algorithm, which is commonly used in computer science. Quick Sort is a divide and conquer algorithm. It creates two empty arrays to hold elements less than the pivot value and elements greater than the pivot value, and then recursively sort the sub arrays. There are two basic operations in the algorithm, swapping items in place and partitioning a section of the array.
Quick Sort Algorithm: Steps on how it works:
- Find a ?pivot? item in the array. This item is the basis for comparison for a single round.
- Start a pointer (the left pointer) at the first item in the array.
- Start a pointer (the right pointer) at the last item in the array.
- While the value at the left pointer in the array is less than the pivot value, move the left pointer to the right (add 1). Continue until the value at the left pointer is greater than or equal to the pivot value.
- While the value at the right pointer in the array is greater than the pivot value, move the right pointer to the left (subtract 1). Continue until the value at the right pointer is less than or equal to the pivot value.
- If the left pointer is less than or equal to the right pointer, then swap the values at these locations in the array.
- Move the left pointer to the right by one and the right pointer to the left by one.
- If the left pointer and right pointer don?t meet, go to step 1.
Below is an image of an array, which needs to be sorted. We will use the Quick Sort Algorithm, to sort this array:
And here is a YouTube video which explains Quick Sort:
Quick Sort: An example
Here is an example of writing the Quick Sort Algorithm based on the steps I provided earlier. Below I have written a function, which accept the following parameter: an array. The function returns the sorted array.
Important Characteristics of Quick Sort:
- Quick Sort is useful for sorting arrays.
- In efficient implementations Quick Sort is not a stable sort, meaning that the relative order of equal sort items is not preserved.
- Overall time complexity of Quick Sort is O(nLogn). In the worst case, it makes O(n2) comparisons, though this behavior is rare.
- The space complexity of Quick Sort is O(nLogn). It is an in-place sort (i.e. it doesn?t require any extra storage)
Overall Quick Sort is an important concept to understand when it comes to algorithms. Thank you for reading this blog post. In upcoming blog posts of this series, I will go over other sorting algorithms like bubble sort.
