1import java.util.Arrays;
2public class QuickSortInJava
3{
4 int partition(int[] arrNumbers, int low, int high)
5 {
6 int pivot = arrNumbers[high];
7 // smaller element index
8 int a = (low - 1);
9 for(int b = low; b < high; b++)
10 {
11 // if current element is smaller than the pivot
12 if(arrNumbers[b] < pivot)
13 {
14 a++;
15 // swap arrNumbers[a] and arrNumbers[b]
16 int temp = arrNumbers[a];
17 arrNumbers[a] = arrNumbers[b];
18 arrNumbers[b] = temp;
19 }
20 }
21 // swap arrNumbers[a + 1] and arrNumbers[high] or pivot
22 int temp = arrNumbers[a + 1];
23 arrNumbers[a + 1] = arrNumbers[high];
24 arrNumbers[high] = temp;
25 return a + 1;
26 }
27 void sort(int[] arrNumbers, int low, int high)
28 {
29 if (low < high)
30 {
31 int p = partition(arrNumbers, low, high);
32 /* recursive sort elements before
33 partition and after partition */
34 sort(arrNumbers, low, p - 1);
35 sort(arrNumbers, p + 1, high);
36 }
37 }
38 static void displayArray(int[] arrNumbers)
39 {
40 int s = arrNumbers.length;
41 for(int a = 0; a < s; ++a)
42 System.out.print(arrNumbers[a] + " ");
43 System.out.println();
44 }
45 public static void main(String[] args)
46 {
47 int[] arrNumbers = {59, 74, 85, 67, 56, 29, 68, 34};
48 int s = arrNumbers.length;
49 QuickSortInJava obj = new QuickSortInJava();
50 obj.sort(arrNumbers, 0, s - 1);
51 System.out.println("After sorting array: ");
52 displayArray(arrNumbers);
53 }
54}
1//GOD's quicksort
2public static <E extends Comparable<E>> List<E> sort(List<E> col) {
3 if (col == null || col.isEmpty())
4 return Collections.emptyList();
5 else {
6 E pivot = col.get(0);
7 Map<Integer, List<E>> grouped = col.stream()
8 .collect(Collectors.groupingBy(pivot::compareTo));
9 return Stream.of(sort(grouped.get(1)), grouped.get(0), sort(grouped.get(-1)))
10 .flatMap(Collection::stream).collect(Collectors.toList());
11 }
12}
1
2import java.util.*;
3class QuickSort {
4 //selects last element as pivot, pi using which array is partitioned.
5 int partition(int intArray[], int low, int high) {
6 int pi = intArray[high];
7 int i = (low-1); // smaller element index
8 for (int j=low; j<high; j++) {
9 // check if current element is less than or equal to pi
10 if (intArray[j] <= pi) {
11 i++;
12 // swap intArray[i] and intArray[j]
13 int temp = intArray[i];
14 intArray[i] = intArray[j];
15 intArray[j] = temp;
16 }
17 }
18
19 // swap intArray[i+1] and intArray[high] (or pi)
20 int temp = intArray[i+1];
21 intArray[i+1] = intArray[high];
22 intArray[high] = temp;
23
24 return i+1;
25 }
26
27
28 //routine to sort the array partitions recursively
29 void quick_sort(int intArray[], int low, int high) {
30 if (low < high) {
31 //partition the array around pi=>partitioning index and return pi
32 int pi = partition(intArray, low, high);
33
34 // sort each partition recursively
35 quick_sort(intArray, low, pi-1);
36 quick_sort(intArray, pi+1, high);
37 }
38 }
39}
40
41class QUICK_SORT{
42 public static void main(String args[]) {
43 //initialize a numeric array, intArray
44 int intArray[] = {3,2,1,6,5,4};
45 int n = intArray.length;
46 //print the original array
47 System.out.println("Original Array: " + Arrays.toString(intArray));
48 //call quick_sort routine using QuickSort object
49 QuickSort obj = new QuickSort();
50 obj.quick_sort(intArray, 0, n-1);
51 //print the sorted array
52 System.out.println("\nSorted Array: " + Arrays.toString(intArray));
53 }
54}
1 //Worst case: if pivot was at the end and all numbers are greater than the pivot
2 //Best case: (n log n): due to you cutting the array in half n times
3 // Average case(n log n): ^
4
5public class QuickSort {
6
7 public static void main(String [] args) {
8 int [] arr = {5, 1, 6, 4, 2, 3};
9 quickSort(arr, 0, arr.length);
10
11 /*Using a for each loop to print out the ordered numbers from the array*/
12 for(int i: arr){
13 System.out.println(i);
14 }// End of the for-each loop
15
16 }// End of the main method
17
18 public static void quickSort(int [] arr, int start, int end) {
19 /*Base case*/
20 if(start >= end) {
21 return;
22 }// End of the base case
23
24 int pIndex = partition(arr, start, end);// The index of the pivot.
25 //System.out.println(pIndex);
26
27 /*Recursive cases*/
28 quickSort(arr, start, pIndex - 1);// Left side of the array
29 quickSort(arr, pIndex + 1, end);// Right side of the array
30
31 }// End of the quicksort method
32
33 public static int partition(int [] arr, int start, int end) {
34 int pivot = arr[end - 1];// Select the pivot to be the last element
35 int pIndex = start;// (Partition index) Indicates where the pivot will be.
36
37 for(int i = start; i < end; i++) {
38 if(arr[i] < pivot) {
39
40 // if a number is smaller than the pivot, it gets swapped with the Partition index
41 int temp = arr[pIndex];
42 arr[pIndex] = arr[i];
43 arr[i] = temp;
44
45 pIndex++;// increments the partition index, only stops when pivot is in the right area
46 }// End of the if statement
47
48 }// End of the for loop
49
50 // This swaps the pivot with the element that stopped where the pivot should be
51 arr[end - 1] = arr[pIndex];
52 arr[pIndex] = pivot;
53 return pIndex;
54 }// End of the partition method
55
56}// End of the QuickSort class
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
1public static ArrayList<Vehicle> quickSort(ArrayList<Vehicle> list)
2{
3 if (list.isEmpty())
4 return list; // start with recursion base case
5 ArrayList<Vehicle> sorted; // this shall be the sorted list to return, no needd to initialise
6 ArrayList<Vehicle> smaller = new ArrayList<Vehicle>(); // Vehicles smaller than pivot
7 ArrayList<Vehicle> greater = new ArrayList<Vehicle>(); // Vehicles greater than pivot
8 Vehicle pivot = list.get(0); // first Vehicle in list, used as pivot
9 int i;
10 Vehicle j; // Variable used for Vehicles in the loop
11 for (i=1;i<list.size();i++)
12 {
13 j=list.get(i);
14 if (j.compareTo(pivot)<0) // make sure Vehicle has proper compareTo method
15 smaller.add(j);
16 else
17 greater.add(j);
18 }
19 smaller=quickSort(smaller); // capitalise 's'
20 greater=quickSort(greater); // sort both halfs recursively
21 smaller.add(pivot); // add initial pivot to the end of the (now sorted) smaller Vehicles
22 smaller.addAll(greater); // add the (now sorted) greater Vehicles to the smaller ones (now smaller is essentially your sorted list)
23 sorted = smaller; // assign it to sorted; one could just as well do: return smaller
24
25 return sorted;
26}