QuickSort algorithm.

Quicksort use case.


Quicksort is a commonly used algorithm for sorting, another example of in-place sorting algorithm. It was developed in 1959 by british computer scientist Tony Hoare.

QuickSort is based on a Divide and Conquer principle just like Merge Sort. The algorithm picks an element as pivot and partitions the given array around the picked pivot, i. e. ann array is divided into subarrays by selecting a pivot element. The pivot element should be placed in such manner that elements less than pivot should be on the left side and elements greater than pivot should be on the right side.

QuickSort algorithm cheat sheet.



The left and right parts are also divided using the same method, the process goes on till each subarray contains only a single element. Then all elements are grouped to form a sorted array.
Quicksort is considered to be faster than merge sort and heapsort.


Quicksort Python code:




# partition function
def partition_f(array, low, high):

  # choose the rightmost element as pivot
  pivot = array[high]

  # pointer for greater element
  i = low - 1

  # traverse through all elements
  # compare each element with pivot
  for j in range(low, high):
    if array[j] <= pivot:
      # if element smaller than pivot is found
      # swap it with the greater element pointed by i
      i = i + 1

      # swapping element at i with element at j
      (array[i], array[j]) = (array[j], array[i])

  # swap the pivot element with the greater element specified by i
  (array[i + 1], array[high]) = (array[high], array[i + 1])

  # return the position from where partition is done
  return i + 1

# quicksort function
def quickSort_f(array, low, high):
  if low < high:

    # finding pivot element
    pi = partition_f(array, low, high)

    # recursive call on the left of pivot
    quickSort_f(array, low, pi - 1)

    # recursive call on the right of pivot
    quickSort_f(array, pi + 1, high)


data = [-10, 35, 0, 13, -7]

size = len(data)

quickSort_f(data, 0, size - 1)

print('Sorted elements in ascending order:')
print(data)

OUT: Sorted elements in ascending order:
[-10, -7, 0, 13, 35]





See also related topics: