// 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 ;
}
# 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
#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)
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);
}
}
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]"
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;
}
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;
}
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)
// 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);
}
}
"""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
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;
}
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))