Quicksort java code example

Example 1: Quicksort java

import java.util.Arrays;
public class QuickSortInJava
{
   int partition(int[] arrNumbers, int low, int high)
   {
      int pivot = arrNumbers[high];
      // smaller element index
      int a = (low - 1);
      for(int b = low; b < high; b++)
      {
         // if current element is smaller than the pivot
         if(arrNumbers[b] < pivot)
         {
            a++;
            // swap arrNumbers[a] and arrNumbers[b]
            int temp = arrNumbers[a];
            arrNumbers[a] = arrNumbers[b];
            arrNumbers[b] = temp;
         }
      }
      // swap arrNumbers[a + 1] and arrNumbers[high] or pivot
      int temp = arrNumbers[a + 1];
      arrNumbers[a + 1] = arrNumbers[high];
      arrNumbers[high] = temp;
      return a + 1;
   }
   void sort(int[] arrNumbers, int low, int high)
   {
      if (low < high)
      {
         int p = partition(arrNumbers, low, high);
         /* recursive sort elements before
         partition and after partition */
         sort(arrNumbers, low, p - 1);
         sort(arrNumbers, p + 1, high);
      }
   }
   static void displayArray(int[] arrNumbers)
   {
      int s = arrNumbers.length;
      for(int a = 0; a < s; ++a)
         System.out.print(arrNumbers[a] + " ");
      System.out.println();
   }
   public static void main(String[] args)
   {
      int[] arrNumbers = {59, 74, 85, 67, 56, 29, 68, 34};
      int s = arrNumbers.length;
      QuickSortInJava obj = new QuickSortInJava();
      obj.sort(arrNumbers, 0, s - 1);
      System.out.println("After sorting array: ");
      displayArray(arrNumbers);
   }
}

Example 2: quick sort code in java

import java.util.*;
class QuickSort {
    //selects last element as pivot, pi using which array is partitioned.
    int partition(int intArray[], int low, int high) {
        int pi = intArray[high];
        int i = (low-1); // smaller element index
        for (int j=low; j<high; j++) {
            // check if current element is less than or equal to pi
            if (intArray[j] <= pi) {
                i++;
                // swap intArray[i] and intArray[j]
                int temp = intArray[i];
                intArray[i] = intArray[j];
                intArray[j] = temp;
            }
        }

        // swap intArray[i+1] and intArray[high] (or pi)
        int temp = intArray[i+1];
        intArray[i+1] = intArray[high];
        intArray[high] = temp;

        return i+1;
    }


    //routine to sort the array partitions recursively
    void quick_sort(int intArray[], int low, int high) {
        if (low < high) {
            //partition the array around pi=>partitioning index and return pi
            int pi = partition(intArray, low, high);

            // sort each partition recursively
            quick_sort(intArray, low, pi-1);
            quick_sort(intArray, pi+1, high);
        }
    }
}

class QUICK_SORT{
    public static void main(String args[]) {
        //initialize a numeric array, intArray
        int intArray[] = {3,2,1,6,5,4};
        int n = intArray.length;
        //print the original array
        System.out.println("Original Array: " + Arrays.toString(intArray));
        //call quick_sort routine using QuickSort object
        QuickSort obj = new QuickSort();
        obj.quick_sort(intArray, 0, n-1);
        //print the sorted array
        System.out.println("\nSorted Array: " + Arrays.toString(intArray));
    }
}

Example 3: quicksort java

//GOD's quicksort
public static <E extends Comparable<E>> List<E> sort(List<E> col) {
  if (col == null || col.isEmpty())
    return Collections.emptyList();
  else {
    E pivot = col.get(0);
    Map<Integer, List<E>> grouped = col.stream()
      .collect(Collectors.groupingBy(pivot::compareTo));
    return Stream.of(sort(grouped.get(1)), grouped.get(0), sort(grouped.get(-1)))
      .flatMap(Collection::stream).collect(Collectors.toList());
  }
}

Example 4: quicksort

// @see https://www.youtube.com/watch?v=es2T6KY45cA&vl=en
// @see https://www.youtube.com/watch?v=aXXWXz5rF64
// @see https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html

function partition(list, start, end) {
    const pivot = list[end];
    let i = start;
    for (let j = start; j < end; j += 1) {
        if (list[j] <= pivot) {
            [list[j], list[i]] = [list[i], list[j]];
            i++;
        }
    }
    [list[i], list[end]] = [list[end], list[i]];
    return i;
}

function quicksort(list, start = 0, end = undefined) {
    if (end === undefined) {
        end = list.length - 1;
    }
    if (start < end) {
        const p = partition(list, start, end);
        quicksort(list, start, p - 1);
        quicksort(list, p + 1, end);
    }
    return list;
}

quicksort([5, 4, 2, 6, 10, 8, 7, 1, 0]);

Example 5: quicksort for arraylist

public static ArrayList<Vehicle> quickSort(ArrayList<Vehicle> list)
{
    if (list.isEmpty()) 
        return list; // start with recursion base case
    ArrayList<Vehicle> sorted;  // this shall be the sorted list to return, no needd to initialise
    ArrayList<Vehicle> smaller = new ArrayList<Vehicle>(); // Vehicles smaller than pivot
    ArrayList<Vehicle> greater = new ArrayList<Vehicle>(); // Vehicles greater than pivot
    Vehicle pivot = list.get(0);  // first Vehicle in list, used as pivot
    int i;
    Vehicle j;     // Variable used for Vehicles in the loop
    for (i=1;i<list.size();i++)
    {
        j=list.get(i);
        if (j.compareTo(pivot)<0)   // make sure Vehicle has proper compareTo method 
            smaller.add(j);
        else
            greater.add(j);
    }
    smaller=quickSort(smaller);  // capitalise 's'
    greater=quickSort(greater);  // sort both halfs recursively
    smaller.add(pivot);          // add initial pivot to the end of the (now sorted) smaller Vehicles
    smaller.addAll(greater);     // add the (now sorted) greater Vehicles to the smaller ones (now smaller is essentially your sorted list)
    sorted = smaller;            // assign it to sorted; one could just as well do: return smaller

    return sorted;
}