Skip to main content

Quick Sort


Quick sort is a divide-and-conquer algorithm that is used to sort arrays of elements. The idea behind this algorithm is to pick a pivot element and partition the array into two parts such that elements to the left of the pivot are smaller and elements to the right of the pivot are greater. This partitioning process is repeated recursively for each part until the array is sorted.

Here's how it works in detail:

  1. Select a pivot element: The pivot element is usually selected as the last element in the array, but other elements can also be chosen.
  2. Partitioning: The pivot element is used to partition the array into two parts: elements smaller than the pivot, and elements greater than the pivot. This is achieved by maintaining two pointers, one starting from the beginning of the array and the other from the end of the array, and swapping elements that are on the wrong side of the pivot. The process continues until the pointers meet in the middle of the array.
  3. Recursion: The two sub-arrays generated by the partitioning process are then sorted recursively using the same quick sort algorithm, until each sub-array consists of only one element.

The time complexity of the quick sort algorithm depends on the choice of the pivot element. If the pivot is selected such that the resulting sub-arrays are roughly the same size, then the time complexity is O(n * log n), which makes it one of the fastest sorting algorithms. However, if the pivot is selected such that one of the sub-arrays is much smaller than the other, then the time complexity can become O(n^2), which makes it one of the slowest sorting algorithms. To avoid this issue, various pivot selection strategies have been developed, such as selecting the pivot as the median of the first, last, and middle elements.

In conclusion, quick sort is a powerful sorting algorithm that is efficient in practice and widely used in various applications. The algorithm's performance is largely dependent on the choice of the pivot element, and careful consideration should be given to pivot selection strategies to ensure good performance.

ALGORITHM:

The QuickSort algorithm consists of the following steps:
  1. Check if the start index is less than the end index. If it is not, the sub-array is already sorted and the function returns.
  2. Choose a pivot value from the sub-array. This is usually the last value, but it can also be chosen randomly or as the median of the first, last, and middle values.
  3. Use a boundary index to partition the sub-array into two parts. The boundary index starts at the start index minus one and is used to keep track of the boundary between elements that are less than or equal to the pivot and elements that are greater than the pivot.
  4. Iterate through the sub-array from the start index to the end index minus one. If the current element is less than or equal to the pivot, increment the boundary index and swap the boundary element with the current element.
  5. Swap the pivot with the element at the boundary index plus one to place the pivot in its final position.
  6. Recursively call QuickSort on the sub-array to the left and right of the pivot, until the sub-array is fully sorted.
  7. Repeat the process until all sub-arrays have been sorted, resulting in the entire array being sorted in ascending order.

PSEUDO CODE:

Here's the pseudocode for QuickSort:

The QuickSort function takes an array A, and two indices p and r that define the sub-array to be sorted. The function first checks if p is less than r. If it is, it calls the Partition function to partition the sub-array around a pivot, and then recursively calls QuickSort on the sub-arrays to the left and right of the pivot.

The Partition function selects the last element x of the sub-array as the pivot and uses a pointer i to keep track of the boundary between elements that are less than or equal to the pivot and elements that are greater than the pivot. It then iterates through the sub-array from p to r - 1 and swaps elements that are less than or equal to the pivot with the element at i + 1. Finally, it swaps the pivot with the element at i + 1 and returns i + 1 as the pivot's index.

The pivot selection and partitioning steps result in the sub-array being partitioned into two parts, with elements less than or equal to the pivot on the left and elements greater than the pivot on the right. The QuickSort function then recursively sorts the left and right sub-arrays, continuing this process until all sub-arrays have been sorted.

PYTHON CODE:

Here's an implementation of QuickSort in Python:



The quick_sort function takes an array array, and two indices low and high that define the sub-array to be sorted. The function first checks if low is less than high. If it is, it calls the partition function to partition the sub-array around a pivot, and then recursively calls quick_sort on the sub-arrays to the left and right of the pivot.

The partition function selects the last element pivot of the sub-array as the pivot and uses a pointer i to keep track of the boundary between elements that are less than or equal to the pivot and elements that are greater than the pivot. It then iterates through the sub-array from low to high - 1 and swaps elements that are less than or equal to the pivot with the element at i + 1. Finally, it swaps the pivot with the element at i + 1 and returns i + 1 as the pivot's index.

The pivot selection and partitioning steps result in the sub-array being partitioned into two parts, with elements less than or equal to the pivot on the left and elements greater than the pivot on the right. The quick_sort function then recursively sorts the left and right sub-arrays, continuing this process until all sub-arrays have been sorted.

JAVA CODE:

Here's an implementation of QuickSort in Java:


The quickSort function takes an array array, and two indices low and high that define the sub-array to be sorted. The function first checks if low is less than high. If it is, it calls the partition function to partition the sub-array around a pivot, and then recursively calls quickSort on the sub-arrays to the left and right of the pivot.

The partition function selects the last element pivot of the sub-array as the pivot and uses a pointer i to keep track of the boundary between elements that are less than or equal to the pivot and elements that are greater than the pivot. It then iterates through the sub-array from low to high - 1 and swaps elements that are less than or equal to the pivot with the element at i + 1. Finally, it swaps the pivot with the element at i + 1 and returns i + 1 as the pivot's index.

The pivot selection and partitioning steps result in the sub-array being partitioned into two parts, with elements less than or equal to the pivot on the left and elements greater than the pivot on the right. The quickSort function then recursively sorts the left and right sub-arrays, continuing this process until all sub-arrays have been sorted.

C CODE:

Here's an implementation of QuickSort in C:


The quickSort function takes an array arr, and two indices low and high that define the sub-array to be sorted. The function first checks if low is less than high. If it is, it calls the partition function to partition the sub-array around a pivot, and then recursively calls quickSort on the sub-arrays to the left and right of the pivot.

The partition function selects the last element pivot of the sub-array as the pivot and uses a pointer i to keep track of the boundary between elements that are less than or equal to the pivot and elements that are greater than the pivot. It then iterates through the sub-array from low to high - 1 and swaps elements that are less than or equal to the pivot with the element at i + 1. Finally, it swaps the pivot with the element at i + 1 and returns i + 1 as the pivot's index.

The pivot selection and partitioning steps result in the sub-array being partitioned into two parts, with elements less than or equal to the pivot on the left and elements greater than the pivot on the right. The quickSort function then recursively sorts the left and right sub-arrays, continuing this process until all sub-arrays have been sorted.

C++ CODE:

Here's an implementation of QuickSort in C++:


The quickSort function takes an array arr, and two indices low and high that define the sub-array to be sorted. The function first checks if low is less than high. If it is, it calls the partition function to partition the sub-array around a pivot, and then recursively calls quickSort on the sub-arrays to the left and right of the pivot.

The partition function selects the last element pivot of the sub-array as the pivot and uses a pointer i to keep track of the boundary between elements that are less than or equal to the pivot and elements that are greater than the pivot. It then iterates through the sub-array from low to high - 1 and swaps elements that are less than or equal to the pivot with the element at i + 1. Finally, it swaps the pivot with the element at i + 1 and returns i + 1 as the pivot's index.

The pivot selection and partitioning steps result in the sub-array being partitioned into two parts, with elements less than or equal to the pivot on the left and elements greater than the pivot on the right. The quickSort function then recursively sorts the left and right sub-arrays, continuing this process until all sub-arrays have been sorted.

JAVASCRIPT CODE:

Here's an implementation of QuickSort in JavaScript:


The quickSort function takes an array array, and two indices low and high that define the sub-array to be sorted. The function first checks if low is less than high. If it is, it calls the partition function to partition the sub-array around a pivot, and then recursively calls quickSort on the sub-arrays to the left and right of the pivot.

The partition function selects the last element pivot of the sub-array as the pivot and uses a pointer i to keep track of the boundary between elements that are less than or equal to the pivot and elements that are greater than the pivot. It then iterates through the sub-array from low to high - 1 and swaps elements that are less than or equal to the pivot with the element at i + 1. Finally, it swaps the pivot with the element at i + 1 and returns i + 1 as the pivot's index.

The pivot selection and partitioning steps result in the sub-array being partitioned into two parts, with elements less than or equal to the pivot on the left and elements greater than the pivot on the right. The quickSort function then recursively sorts the left and right sub-arrays, continuing this process until all sub-arrays have been sorted.

Comments

Post a Comment

Popular posts from this blog

Leetcode 1: Two Sum

  Leetcode Link: https://leetcode.com/problems/two-sum/ 1. Problem Statement (Simple Explanation) You are given: An array of integers nums An integer target You need to  return the indices of two numbers in the array  such that: Conditions: Each input has  exactly one solution . You  cannot use the same element twice . You can return the answer in  any order . 2. Examples Example 1 Input:                                    nums = [2, 7, 11, 15], target = 9 Output:                                 [0, 1] Explanation:                     nums[0]+nums[1]=2+7=9              So we return [0, 1]. Example 2 Input:           ...
Post a Comment
Read more

Leetcode 3: Longest Substring Without Repeating Characters

  Leetcode Link 1. Problem Statement (Simple Explanation) You are given a string s. You need to find the length of the longest substring of s that does not  contain any repeated characters. A substring is a contiguous sequence of characters in the string. You must return an integer length, not the substring itself. 2. Examples Example 1 Input: s = "abcabcbb" Output: 3 Explanation: Some substrings without repeating characters: "abc", "bca", "cab"The longest length is 3. Example 2 Input: s = "bbbbb" Output: 1 Explanation: All substrings that are valid are just "b". The longest length is 1. Example 3 Input:   s = "pwwkew" Output:   3 Explanation: Possible substrings without repetition: "pw", "wke", "kew". "wke" or "kew" have length 3. "pwke" is not valid because it’s not contiguous in the original string (p and k are separated by ww). Constraints...
Post a Comment
Read more

Leetcode 2: Add Two Numbers

Leetcode Link: https://leetcode.com/problems/add-two-numbers/ 1. Problem Statement (Simple Explanation) You are given  two non-empty linked lists , l1 and l2, that represent two non-negative integers. Each node contains a  single digit . The digits are stored in  reverse order  (i.e., the 1’s digit is at the head). You need to  add the two numbers  and return the  sum as a linked list , also in reverse order. You can assume: There are  no leading zeros , except when the number itself is 0. 2. Examples Example 1 Input:                l1 = [2,4,3]                l2 = [5,6,4]           Interpreting linked lists as numbers (reverse order): l1 represents 342 l2 represents 465 Output:                [7,0,8] Explanation:        ...
Post a Comment
Read more