Quick Sort

Reading Time: 1 minute

Definition

Quick sort is a very efficient algorithm that leverages the divide-and-conquer principle to sort a data structure. The calculated performance complexity of Quick Sort  as follows;

  1. Best Case: O(n log n),
  2. Average Case: O(n log n),
  3. Worse Case: O(n2), reason: the algorithm will select only one element in each iteration
  4. Space Complexity: O(log n).

Terminology

Furthermore, for starters, it will be a good practice to apprehend the terms in this algorithm;

  • Pivot: A reference element that is used as a line whose left and rights elements are divided. There are a few Quick Sort implementations, whose suggestions vary from picking the Pivot from the beginning, middle, end or randomly,
  • Partition: It is a practice that swaps elements on the left and right ends, while using the Pivot as a reference. By the end of Partitioning, a partition point for the next divided subsets(those will be divided also) is returned,
  • Left Pointer: A pointer or an index value that traverses on the last/low/left subset of the designated array,
  • Right Pointer: A pointer or an index value that traverses on the last/low/right subset of the designated array,

Internal of the Algorithm

In every step, the Quick Sort divides the array to subsets and aims to collect the lower numbers on the left side, the greater numbers  on the right side of the pivot in an ascending format. Let’s look at a glance how the code performs the operation;

  1. Choosing a Pivot,
  2. Beginning the partitioning by swapping the lower elements on the left, greater elements on the right side of the pivot,
  3. Apply partitioning on the left side and later on the right side.

Code

you can checkout my GitHub repository @ https://github.com/tugrulaslan/BlogCodeSnippets/tree/master/SortingAlgorithms

Leave a Reply

Your email address will not be published. Required fields are marked *