# 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
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);
}
}
#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)
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]"
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)
void quick_sort(int q[], int l, int r)
{
if (l >= r) return;
int i = l - 1, j = r + 1, x = q[l + r >> 1];
while (i < j)
{
do i ++ ; while (q[i] < x);
do j -- ; while (q[j] > x);
if (i < j) swap(q[i], q[j]);
}
quick_sort(q, l, j), quick_sort(q, j + 1, r);
}
//piv: Pivot element
int partition ( int A[],int start ,int end) {
int i = start + 1;
int piv = A[start] ; //make the first element as pivot element.
for(int j =start + 1; j <= end ; j++ ) {
/*rearrange the array by putting elements which are less than pivot
on one side and which are greater that on other. */
if ( A[ j ] < piv) {
swap (A[ i ],A [ j ]);
i += 1;
}
}
swap ( A[ start ] ,A[ i-1 ] ) ; //put the pivot element in its proper place.
return i-1; //return the position of the pivot
}
// recursive function Quick_sort:
void quick_sort ( int A[ ] ,int start , int end ) {
if( start < end ) {
//stores the position of pivot element
int piv_pos = partition (A,start , end ) ;
quick_sort (A,start , piv_pos -1); //sorts the left side of pivot.
quick_sort ( A,piv_pos +1 , end) ; //sorts the right side of pivot.
}
}
// 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))