quick sort

1#include<stdio.h>
2void quicksort(int number[25],int first,int last){
3   int i, j, pivot, temp;
4
5   if(first<last){
6      pivot=first;
7      i=first;
8      j=last;
9
10      while(i<j){
11         while(number[i]<=number[pivot]&&i<last)
12            i++;
13         while(number[j]>number[pivot])
14            j--;
15         if(i<j){
16            temp=number[i];
17            number[i]=number[j];
18            number[j]=temp;
19         }
20      }
21
22      temp=number[pivot];
23      number[pivot]=number[j];
24      number[j]=temp;
25      quicksort(number,first,j-1);
26      quicksort(number,j+1,last);
27
28   }
29}
30
31int main(){
32   int i, count, number[25];
33
34   printf("How many elements are u going to enter?: ");
35   scanf("%d",&count);
36
37   printf("Enter %d elements: ", count);
38   for(i=0;i<count;i++)
39      scanf("%d",&number[i]);
40
41   quicksort(number,0,count-1);
42
43   printf("Order of Sorted elements: ");
44   for(i=0;i<count;i++)
45      printf(" %d",number[i]);
46
47   return 0;
48}
49

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}

1//I Love Java
2import java.io.*;
3import java.util.*;
4import java.util.stream.*;
5import static java.util.Collections.*;
6
7import static java.util.stream.Collectors.*;
8
9public class Quick_Sort_P {
10
11    static void swap(List<Integer> arr, int i, int j) {
12        int temp = arr.get(i);
13        arr.set(i, arr.get(j));
14        arr.set(j, temp);
15    }
16
17    static int partition(List<Integer> arr, int low, int high) {
18
19        int pivot = arr.get(high);
20        int i = (low - 1);
21
22        for (int j = low; j <= high - 1; j++) {
23
24            if (arr.get(j) < pivot) {
25
26                i++;
27                swap(arr, i, j);
28            }
29        }
30        swap(arr, i + 1, high);
31        return (i + 1);
32    }
33
34    static void quickSort(List<Integer> arr, int low, int high) {
35        if (low < high) {
36
37            int pi = partition(arr, low, high);
38
39            quickSort(arr, low, pi - 1);
40            quickSort(arr, pi + 1, high);
41        }
42    }
43
44    public static void main(String[] args) throws IOException {
45
46        BufferedReader buffer = new BufferedReader(new InputStreamReader(System.in));
47
48        List<Integer> arr = Stream.of(buffer.readLine().replaceAll("\\s+$", "").split(" ")).map(Integer::parseInt)
49                .collect(toList());
50
51        int n = arr.size();
52
53        quickSort(arr, 0, n - 1);
54        System.out.println("Sorted array: ");
55        System.out.println(arr);
56    }
57}

1void swap(int* a, int* b)
2{
3    int t = *a;
4    *a = *b;
5    *b = t;
6}
7 
8/* This function takes last element as pivot, places
9the pivot element at its correct position in sorted
10array, and places all smaller (smaller than pivot)
11to left of pivot and all greater elements to right
12of pivot */
13int partition (int arr[], int low, int high)
14{
15    int pivot = arr[high]; // pivot
16    int i = (low - 1); // Index of smaller element and indicates the right position of pivot found so far
17 
18    for (int j = low; j <= high - 1; j++)
19    {
20        // If current element is smaller than the pivot
21        if (arr[j] < pivot)
22        {
23            i++; // increment index of smaller element
24            swap(&arr[i], &arr[j]);
25        }
26    }
27    swap(&arr[i + 1], &arr[high]);
28    return (i + 1);
29}
30 
31/* The main function that implements QuickSort
32arr[] --> Array to be sorted,
33low --> Starting index,
34high --> Ending index */
35void quickSort(int arr[], int low, int high)
36{
37    if (low < high)
38    {
39        /* pi is partitioning index, arr[p] is now
40        at right place */
41        int pi = partition(arr, low, high);
42 
43        // Separately sort elements before
44        // partition and after partition
45        quickSort(arr, low, pi - 1);
46        quickSort(arr, pi + 1, high);
47    }
48}
49 
50/* Function to print an array */
51void printArray(int arr[], int size)
52{
53    int i;
54    for (i = 0; i < size; i++)
55        cout << arr[i] << " ";
56    cout << endl;
57}
58 
59// Driver Code
60int main()
61{
62    int arr[] = {10, 7, 8, 9, 1, 5};
63    int n = sizeof(arr) / sizeof(arr[0]);
64    quickSort(arr, 0, n - 1);
65    cout << "Sorted array: \n";
66    printArray(arr, n);
67    return 0;
68}