Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

quicksort
sorting
java

# How to implement QuickSort in Java Educative Answers Team

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

QuickSort is an in-place sorting algorithm with worst-case time complexity of $n^{2}$

## Implementation

​​QuickSort can be implemented iteratively and recursively. We’ll mainly focus on the recursive implementation, as it is far more convenient, intuitive and simplistic. Iterative implementation is generally unrecommended. Arrays are used as an example here, but it can be implemented on other data structures (like linked lists) as well.

The algorithm can be broken down into 3 parts.

1. Partitioning the array about the pivot
2. Passing the smaller arrays to the recursive calls
3. Joining the sorted arrays that are returned from the recursive call, and the pivot 1 of 16

In the above illustration, we used the first element of the ​array as a pivot (though any of the elements can be taken).

## Code

import java.util.*;class Quick_Sort {      public static int[] QuickSort(int[] arr, int elements) {      if(elements < 2){     //Base Case          return arr;      }      int current_position=0;   //position of pivot element      int temp; //a temporary variable to assist in swapping      for(int i=1; i<elements; i++) //Partitioning loop      {          if(arr[i] <= arr)          {              current_position++;              temp = arr[i];              arr[i] = arr[current_position];              arr[current_position] = temp;          }      }      temp = arr;       arr = arr[current_position];       arr[current_position] = temp; //Brings pivot to it's appropriate position            int[] left = QuickSort(arr,current_position); //sorts the elements to the left of pivot            int[] arr2 = Arrays.copyOfRange(arr, current_position+1, elements);//separates elements right of pivot            int[] right = QuickSort(arr2, elements-current_position-1); //sorts the elements to the right of pivot            int[] final_array = new int[elements]; //final array, to merge everything together            for(int i=0; i<current_position; i++)      {          final_array[i] = left[i];       }      final_array[current_position] = arr[current_position];      for(int i=current_position+1; i<elements; i++)      {          final_array[i] = right[i-current_position-1];      }    return final_array;  }    public static void main( String args[] ) {        int[] array = {4,2,7,3,1,6}; //array to be sorted        System.out.print("Original Array: [");        for(int i=0; i<array.length;i++)        {               System.out.print(array[i]);            System.out.print(" ");        }        System.out.println("]");        array = QuickSort(array, array.length);//sorting                 System.out.print("Sorted Array: ["); //printing the sorted array        for(int i=0; i<array.length;i++)        {               System.out.print(array[i]);            System.out.print(" ");        }                System.out.print("]");    }}

RELATED TAGS

quicksort
sorting
java 