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

Selection Sort

Selection sort is a simple sorting algorithm that sorts an array by repeatedly finding the minimum element from the unsorted portion of the array and swapping it with the first element of the unsorted portion. It is called selection sort because it repeatedly selects the smallest element of the unsorted portion of the array and moves it to its correct position in the sorted portion of the array. The time complexity of selection sort is O(n^2), where n is the number of elements in the array. This makes it inefficient for large arrays and it is not a good choice for sorting large datasets. However, selection sort is easy to understand and implement, and it is useful for educational purposes and for small arrays. One of the advantages of selection sort is that it makes fewer swaps than other sorting algorithms such as bubble sort. This makes it more efficient in terms of memory writes, which can be important in some situations. Another advantage of selection sort is that it is a stable so
2 comments
Read more

Counting Sort

Counting sort is a sorting algorithm that operates by counting the frequency of each element in the input array, and then using these frequencies to compute the final sorted output. The algorithm works by first creating an array of counters, with each counter corresponding to a distinct element in the input array. The counters are initialized to zero, and then the input array is scanned once to count the number of occurrences of each element. This count information is stored in the corresponding counter in the counter array. Once the count information is obtained, the algorithm uses it to determine the final position of each element in the sorted output array. This is done by iterating over the counter array, and for each counter value, writing the corresponding element to the sorted output array the appropriate number of times. The time complexity of counting sort is O(n+k), where n is the length of the input array and k is the range of the elements. The space complexity is also O(n+k
2 comments
Read more

Pigeonhole Sort

Pigeonhole sort is a sorting algorithm that works by distributing elements of an input sequence into a set of pigeonholes or buckets. It is an efficient sorting algorithm for small ranges of values where the number of elements to be sorted is roughly the same as the range of values. Pigeonhole sort is an example of a bucket sort algorithm. The pigeonhole sort algorithm works by first determining the range of values in the input sequence. This range is used to create a set of pigeonholes or buckets, each of which can hold one or more elements from the input sequence. Each element in the input sequence is then placed into its corresponding pigeonhole based on its value. If two or more elements have the same value, they can be placed in the same pigeonhole. Once all the elements have been placed into their corresponding pigeonholes, the elements are sorted within each pigeonhole. Finally, the sorted elements are combined into a single output sequence. Pigeonhole sort has a time complexity
Post a Comment
Read more