Answers for "quick sort implementation in java"

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);
   }
}

quicksort java

//Worst case: if pivot was at the end and all numbers are greater than the pivot
	//Best case: (n log n): due to you cutting the array in half n times
	// Average case(n log n): ^

public class QuickSort {
	
	public static void main(String [] args) {
		int [] arr = {5, 1, 6, 4, 2, 3};
		quickSort(arr, 0, arr.length);
		
      	/*Using a for each loop to print out the ordered numbers from the array*/
      	for(int i: arr){
        	System.out.println(i);
        }// End of the for-each loop
	
	}// End of the main method
	
	public static void quickSort(int [] arr, int start, int end) {
		/*Base case*/
		if(start >= end) {
			return;
		}// End of the base case
		
		int pIndex = partition(arr, start, end);// The index of the pivot.
		//System.out.println(pIndex);
		
		/*Recursive cases*/
		quickSort(arr, start, pIndex - 1);// Left side of the array
		quickSort(arr, pIndex + 1, end);// Right side of the array
		
	}// End of the quicksort method
	
	public static int partition(int [] arr, int start, int end) {
		int pivot = arr[end - 1];// Select the pivot to be the last element
		int pIndex = start;// (Partition index) Indicates where the pivot will be. 
		
		for(int i = start; i < end; i++) {
			if(arr[i] < pivot) {
				
				// if a number is smaller than the pivot, it gets swapped with the Partition index
				int temp = arr[pIndex];
				arr[pIndex] = arr[i];
				arr[i] = temp;
				
				pIndex++;// increments the partition index, only stops when pivot is in the right area
			}// End of the if statement
			
		}// End of the for loop
		
		// This swaps the pivot with the element that stopped where the pivot should be
		arr[end - 1] = arr[pIndex];
		arr[pIndex] = pivot;
		return pIndex;
	}// End of the partition method
	
}// End of the QuickSort class

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());
  }
}