CPP

quicksort algorithm

// in c++
#include<iostream>
#include<algorithm>
using namespace std;
int partition(int arr[], int low, int high){
    // i is used for determining the correct position of pivot element
    /*
      We can choose first element of the array as pivot element,
      or we can choose middle element/ last element / any element randomly as pivot element.
       In this program, we are using last element as pivot element.
    */
    int i = low -1;
    int pivot = arr[high];
    for(int j=low; j<= high-1; j++){
        if(arr[j] < pivot){
            i = i+1;
            // to do the swapping directly include "algorithms" library in the header, in c++
            swap(arr[i], arr[j]); 
        }
    }
    // put the pivot elements at its correct position
    swap(arr[i+1], arr[high]);
    return i+1;
}

void quickSort(int arr[], int low, int high){
    if(low < high){
    int pivot = partition(arr, low, high);
    quickSort(arr, low, pivot-1);
    quickSort(arr, pivot+1, high);
    }
}

// for printing the array
void printArray(int arr[], int n){
    for(int i=0; i<n; i++){
        cout<<arr[i]<<" " ;
    }
}
// main function

int main()
{
    int arr[100], pivot, low, high, n;
    cout<<"how many elements you want to put in the array"<<endl;
    cin>>n;
    cout<<endl;
    cout<<"insert elements in the  array"<<endl;
    for(int i =0; i<n; i++){
        cin>>arr[i];
    }
   
    cout<<"Array before Quick Sort"<<endl;
    printArray(arr, n);

     quickSort(arr, 0, n);

    cout<<endl;
    cout<<"Array after quick sort"<<endl;
    printArray(arr, n);

    return 0 ;

    
    
} 

quicksort

# Python3 implementation of QuickSort  
  
  
# Function to find the partition position
def partition(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
  
# Function to perform quicksort
def quick_sort(array, low, high):
  if low < high:
  
    # Find pivot element such that
    # element smaller than pivot are on the left
    # element greater than pivot are on the right
    pi = partition(array, low, high)
  
    # Recursive call on the left of pivot
    quick_sort(array, low, pi - 1)
  
    # Recursive call on the right of pivot
    quick_sort(array, pi + 1, high)
  
    
          
# Driver code
array = [ 10, 7, 8, 9, 1, 5]
quick_sort(array, 0, len(array) - 1)
  
print(f'Sorted array: {array}')
      
# This code is contributed by Adnan Aliakbar

quicksort

#Code With Redoy: https://www.facebook.com/codewithredoy/
#My python lectures: https://cutt.ly/python-full-playlist

def quick_sort(array):
    if len(array) < 2:
        return array
    else:
        #select pivot element
        pivot = array[0]
        #partitioning the main array into less and greater
        less = [i for i in array[1:] if i <= pivot]
        greater = [i for i in array[1:] if i > pivot]
        
        #calling recursively 
        return quick_sort(less) + [pivot] + quick_sort(greater)

array = [9,8,7,6,5,4,3,2,1]
res = quick_sort(array)
print(res)

quick sort

  static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }  
  
  static int partition(int[] arr, int low, int high) { 
    
    int pivot = arr[high]; 
    // Index of smaller element and
    // indicates the right position
    // of pivot found so far
    int i = (low - 1); 
  
    for(int j = low; j <= high - 1; j++) {
      // If current element is smaller 
      // than the pivot
      if (arr[j] < pivot) {
        // Increment index of 
        // smaller element
        i++; 
        swap(arr, i, j);
      }
    }
    swap(arr, i + 1, high);
    return (i + 1);
  }
  
  static void quickSort(int[] arr, int low, int high) {
      if (low < high) {
          // pi is partitioning index, arr[p]
          // is now at right place 
          int pi = partition(arr, low, high);

          // Separately sort elements before
          // partition and after partition
          quickSort(arr, low, pi - 1);
          quickSort(arr, pi + 1, high);
      }
  }

quick sort

def quicksort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quicksort(left) + middle + quicksort(right)

print(quicksort([3,6,8,10,1,2,1]))
# Prints "[1, 1, 2, 3, 6, 8, 10]"

quicksort algorithm

Implementation of Quick Sort Algorithm in C:
# include <stdio.h>

// to swap two numbers
void swap(int* a, int* b)
{
    int t = *a;
    *a = *b;
    *b = t;
}

int partition (int arr[], int low, int high)
{
    int pivot = arr[high];  // selecting last element as pivot
    int i = (low - 1);  // index of smaller element
 
    for (int j = low; j <= high- 1; j++)
    {
        // If the current element is smaller than or equal to pivot
        if (arr[j] <= pivot)
        {
            i++;    // increment index of smaller element
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}
/*  
    a[] is the array, p is starting index, that is 0, 
    and r is the last index of array.  
*/
void quicksort(int a[], int p, int r)    
{
    if(p < r)
    {
        int q;
        q = partition(a, p, r);
        quicksort(a, p, q-1);
        quicksort(a, q+1, r);
    }
}


// function to print the array
void printArray(int a[], int size)
{
    int i;
    for (i=0; i < size; i++)
    {
        printf("%d ", a[i]);
    }
    printf("
");
}

int main()
{
    int arr[] = {9, 7, 5, 11, 12, 2, 14, 3, 10, 6};
    int n = sizeof(arr)/sizeof(arr[0]);
    
    // call quickSort function
    quicksort(arr, 0, n-1);
    
    printf("Sorted array: 
");
    printArray(arr, n);
    return 0;
}

quicksort algorithm

Implementation of Quick Sort Algorithm in C:
# include <stdio.h>

// to swap two numbers
void swap(int* a, int* b)
{
    int t = *a;
    *a = *b;
    *b = t;
}

int partition (int arr[], int low, int high)
{
    int pivot = arr[high];  // selecting last element as pivot
    int i = (low - 1);  // index of smaller element
 
    for (int j = low; j <= high- 1; j++)
    {
        // If the current element is smaller than or equal to pivot
        if (arr[j] <= pivot)
        {
            i++;    // increment index of smaller element
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}
/*  
    a[] is the array, p is starting index, that is 0, 
    and r is the last index of array.  
*/
void quicksort(int a[], int p, int r)    
{
    if(p < r)
    {
        int q;
        q = partition(a, p, r);
        quicksort(a, p, q-1);
        quicksort(a, q+1, r);
    }
}


// function to print the array
void printArray(int a[], int size)
{
    int i;
    for (i=0; i < size; i++)
    {
        printf("%d ", a[i]);
    }
    printf("
");
}

int main()
{
    int arr[] = {9, 7, 5, 11, 12, 2, 14, 3, 10, 6};
    int n = sizeof(arr)/sizeof(arr[0]);
    
    // call quickSort function
    quicksort(arr, 0, n-1);
    
    printf("Sorted array: 
");
    printArray(arr, n);
    return 0;
}

quicksort algorithm

#function for doing partitining
from array import array


def partition(array,low,high):
    i = low-1
    pivot = array[high]
    for j in range(low,high):
        if array[j] <= pivot:
            i = i +1
            (array[i] , array[j]) = (array[j], array[i])
    (array[i+1],array[high]) = (array[high], array[i+1])
    return i+1



# function for quick sort
def quickSort(array, low, high):
    if (low<high):
        pivot = partition(array,low,high)
        quickSort(array,low, pivot-1)
        quickSort(array,pivot+1,high)



# driver code
array = [10,7,8,9,1,5]
n = len(array)
print("array before quick sort",array)
quickSort(array,0,n-1)
print("after quicksort",array)

quick sort

def partition(start, end, array):
     
    # Initializing pivot's index to start
    pivot_index = start
    pivot = array[pivot_index]
     
    # This loop runs till start pointer crosses
    # end pointer, and when it does we swap the
    # pivot with element on end pointer
    while start < end:
         
        # Increment the start pointer till it finds an
        # element greater than  pivot
        while start < len(array) and array[start] <= pivot:
            start += 1
             
        # Decrement the end pointer till it finds an
        # element less than pivot
        while array[end] > pivot:
            end -= 1
         
        # If start and end have not crossed each other,
        # swap the numbers on start and end
        if(start < end):
            array[start], array[end] = array[end], array[start]
     
    # Swap pivot element with element on end pointer.
    # This puts pivot on its correct sorted place.
    array[end], array[pivot_index] = array[pivot_index], array[end]
    
    # Returning end pointer to divide the array into 2
    return end
     
# The main function that implements QuickSort
def quick_sort(start, end, array):
     
    if (start < end):
         
        # p is partitioning index, array[p]
        # is at right place
        p = partition(start, end, array)
         
        # Sort elements before partition
        # and after partition
        quick_sort(start, p - 1, array)
        quick_sort(p + 1, end, array)

Quick sort

// Take Left (first) Index of the array and Right (last) Index of the array
void quickSort(int Data[], int l , int r)
{
	// If the first index less or equal than the last index
	if (l <= r)
	{
		// Create a Key/Pivot Element
		int key = Data[(l+r)/2];

		// Create temp Variables to loop through array
		int i = l;
		int j = r;

		while (i <= j)
		{
			while (Data[i] < key)
				i++;
			while (Data[j] > key)
				j--;

			if (i <= j)
			{
				swap(Data[i], Data[j]);
				i++;
				j--;
			}
		}

		// Recursion to the smaller partition in the array after sorted above

		if (l < j)
			quickSort(Data, l, j);
		if (r > i)
			quickSort(Data, i, r);
	}
}

quicksort

"""3-way Quicksort
	Simpler to implement than basic quicksort
"""
from random import randint
def qs_3_way(nums):
    # Sorting
    if len(nums) > 1:
        pivot = nums[randint(0, len(nums)-1)]
        smaller, greater, equals = [], [], []
        
        for num in nums:
            if num < pivot:
                smaller.append(num)
            elif num > pivot:
                greater.append(num)
            else:
                equals.append(num)
        
        # Recursive Partition
        return qs_3_way(smaller) + equals + qs_3_way(greater)
    return nums # for easy testing

quicksort

"""Basic Quicksort
"""
from random import randint
def qs_basic(nums, low=0, high=None):
    if high is None:
        high = len(nums) - 1
    # Sorting
    if low < high:
        pivot = nums[randint(low, high)]
        # i finds greater than pivot, j finds smaller than pivot
        i, j = low, high
        
        # Sort the pivot
        while i <= j:
            while nums[i] < pivot:
                i += 1
            while nums[j] > pivot:
                j -= 1
                
            # Pivot still not sorted
            if i <= j:
                nums[i], nums[j] = nums[j], nums[i]
                i += 1
                j -= 1
                
        # Recursive Partition
        qs_basic(nums, low, j)
        qs_basic(nums, i, high)
    return nums # for easy testing

quick sort

function swap(arr, leftIndex, rightIndex){
  // swap 2 elements in the array
    var temp = arr[leftIndex];
    arr[leftIndex] = arr[rightIndex];
    arr[rightIndex] = temp;
}
function partition(arr, left, right) {
    var pivot   = arr[Math.floor((right + left) / 2)], //middle element
        i       = left, //left pointer
        j       = right; //right pointer
    while (i <= j) { // while left pointer is smaller than right pointer
        while (arr[i] < pivot) { // move the left pointer to the right
            i++;
        }
        while (arr[j] > pivot) { // move the right pointer to the left
            j--;
        }
        if (i <= j) { //left pointer smaller or equal to right pointer
            swap(arr, i, j); //sawpping two elements
            i++;
            j--;
        }
    }
    return i;
}
// run as quickSort(array, 0, array.length - 1);
function quickSort(arr, left, right) {
    var index;
    if (arr.length > 1) {
        index = partition(arr, left, right); //index returned from partition
        if (left < index - 1) { //more elements on the left side of the pivot
            quickSort(arr, left, index - 1);
        }
        if (index < right) { //more elements on the right side of the pivot
            quickSort(arr, index, right);
        }
    }
    return arr;
}

Quicksort

array = [29,99,27,41,66,28,44,78,87,19,31,76,58,88,83,97,12,21,44]
q = lambda l: q([x for x in l[1:] if x <= l[0]]) + [l[0]] + q([x for x in l if x > l[0]]) if l else []
print(q(array))

quicksort

public void quickSort(int arr[], int begin, int end) {
    if (begin < end) {
        int partitionIndex = partition(arr, begin, end);

        quickSort(arr, begin, partitionIndex-1);
        quickSort(arr, partitionIndex+1, end);
    }
}