quicksort

1def partition(a,l,h):
2    pivot = a[l]
3    i = l
4    j=h
5    while i<j:
6        while a[i]<=pivot and i<h: i+=1
7        while a[j]>pivot and j>l: j-=1
8        if i<j: a[i],a[j]=a[j],a[i]
9        
10    a[j],a[l]=a[l],a[j]
11    return j
12
13def quickSort(a,l,h):
14    if l < h:
15        pi = partition(a, l, h)
16        quickSort(a, l, pi - 1)
17        quickSort(a, pi + 1, h)
18        
19#driver Code        
20a =[10, 7, 8, 9, 1, 5 ]
21quickSort(a, 0, len(a) - 1)
22print(a)
23#Output: [1, 5, 7, 8, 9, 10]

1// @see https://www.youtube.com/watch?v=es2T6KY45cA&vl=en
2// @see https://www.youtube.com/watch?v=aXXWXz5rF64
3// @see https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html
4
5function partition(list, start, end) {
6    const pivot = list[end];
7    let i = start;
8    for (let j = start; j < end; j += 1) {
9        if (list[j] <= pivot) {
10            [list[j], list[i]] = [list[i], list[j]];
11            i++;
12        }
13    }
14    [list[i], list[end]] = [list[end], list[i]];
15    return i;
16}
17
18function quicksort(list, start = 0, end = undefined) {
19    if (end === undefined) {
20        end = list.length - 1;
21    }
22    if (start < end) {
23        const p = partition(list, start, end);
24        quicksort(list, start, p - 1);
25        quicksort(list, p + 1, end);
26    }
27    return list;
28}
29
30quicksort([5, 4, 2, 6, 10, 8, 7, 1, 0]);
31

1//last element selected as pivot
2#include <iostream>
3
4using namespace std;
5void swap(int*,int*);
6int partition(int arr[],int start,int end)
7{
8    int pivot=arr[end];
9    int index=start;
10    int i=start;
11    while(i<end)
12    {
13        if(arr[i]<pivot)
14        {
15            swap(&arr[index],&arr[i]);
16            index++;
17        }
18        i++;
19    }
20    swap(&arr[end],&arr[index]);
21    return index;
22}
23void quicksort(int arr[],int start,int end)
24{
25    if(start<end)
26    {
27      int pindex=partition(arr,start,end);
28      quicksort(arr,start,pindex-1);
29      quicksort(arr,pindex+1,end);
30    }
31}
32void display(int arr[],int n)
33{
34    for(int i=0;i<n;i++)
35    {
36        cout<<arr[i]<<" ";
37    }
38    cout<<endl;
39}
40
41int main()
42{
43    int n;
44    cout<<"enter the size of the array:"<<endl;
45    cin>>n;
46    int arr[n];
47    cout<<"enter the elements of the array:"<<endl;
48    for(int i=0;i<n;i++)
49    {
50        cin>>arr[i];
51    }
52    cout<<"sorted array is:"<<endl;
53    quicksort(arr,0,n-1);
54    display(arr,n);
55
56    return 0;
57}
58void swap(int *a,int*b)
59{
60    int temp=*a;
61    *a=*b;
62    *b=temp;
63}
64

1#include<stdio.h>
2int partition(int arr[], int low, int high) {
3  int temp;
4  int pivot = arr[high];
5  int i = (low - 1); 
6  for (int j = low; j <= high - 1; j++) {
7    if (arr[j] <= pivot) { 
8      i++; 
9      temp = arr[i];
10      arr[i] = arr[j];
11      arr[j] = temp;
12    } 
13  } 
14  temp = arr[i + 1];
15  arr[i + 1] = arr[high];
16  arr[high] = temp;
17  return (i + 1); 
18} 
19void quick_sort(int arr[], int low, int high) { 
20  if (low < high) {
21    int pi = partition(arr, low, high); 
22    quick_sort(arr, low, pi - 1); 
23    quick_sort(arr, pi + 1, high); 
24  } 
25} 
26int print(int arr[], int n) {
27  for(int i = 0; i < n; i++) {
28    printf("%d ", arr[i]);
29  }
30}
31
32int main()
33{
34int n, i;
35scanf("%d", &n);
36int arr[n];
37for(i = 0; i < n; i++)
38{
39scanf("%d", &arr[i]);
40}
41quick_sort(arr, 0, n - 1);
42print(arr, n);
43}

1algorithm quicksort(A, lo, hi) is
2    if lo < hi then
3        p := partition(A, lo, hi)
4        quicksort(A, lo, p - 1)
5        quicksort(A, p + 1, hi)
6
7algorithm partition(A, lo, hi) is
8    pivot := A[hi]
9    i := lo
10    for j := lo to hi do
11        if A[j] < pivot then
12            swap A[i] with A[j]
13            i := i + 1
14    swap A[i] with A[hi]
15    return i
16

1/********** QuickSort(): sorts the vector 'list[]' **********/
2
3/**** Compile QuickSort for strings ****/
4#define QS_TYPE char*
5#define QS_COMPARE(a,b) (strcmp((a),(b)))
6
7/**** Compile QuickSort for integers ****/
8//#define QS_TYPE int
9//#define QS_COMPARE(a,b) ((a)-(b))
10
11/**** Compile QuickSort for doubles, sort list in inverted order ****/
12//#define QS_TYPE double
13//#define QS_COMPARE(a,b) ((b)-(a))
14
15void QuickSort(QS_TYPE list[], int beg, int end)
16{
17    QS_TYPE piv; QS_TYPE tmp;
18    
19    int  l,r,p;
20
21    while (beg<end)    // This while loop will substitude the second recursive call
22    {
23        l = beg; p = (beg+end)/2; r = end;
24
25        piv = list[p];
26
27        while (1)
28        {
29            while ((l<=r) && (QS_COMPARE(list[l],piv) <= 0)) l++;
30            while ((l<=r) && (QS_COMPARE(list[r],piv)  > 0)) r--;
31
32            if (l>r) break;
33
34            tmp=list[l]; list[l]=list[r]; list[r]=tmp;
35
36            if (p==r) p=l;
37            
38            l++; r--;
39        }
40
41        list[p]=list[r]; list[r]=piv;
42        r--;
43
44        // Select the shorter side & call recursion. Modify input param. for loop
45        if ((r-beg)<(end-l))   
46        {
47            QuickSort(list, beg, r);
48            beg=l;
49        }
50        else
51        {
52            QuickSort(list, l, end);
53            end=r;
54        }
55    }   
56}
57