quicksort java

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}