# Quick Sort in java

If you want to practice data structure and algorithm programs, you can go through data structure and algorithm interview questions.

Quick sort or partition-exchange sort, is a sorting algorithm, which is using divide and conquer algorithm.

In quick sort, we first choose a `pivot` and divide into two sublists,one will contain elements `lower than pivot` and other will have elements `greater than pivot`.

## Quick sort Algorithm

Lets say array is arr[]

• Choose a `pivot`, it is generally mid element of the list.
• Initialise two index variable , `left=0` and `right=arr.length-1`
• Increment left variable until you get element higher than pivot.
• Decrement right variable until you get element lesser than pivot
• swap `arr[left]` and `arr[right]`
• `Recursively sort sublists`(sublist with less than pivot, sublist greater than pivot) using above algorithm.
• In the end , you will get `sorted array`.

## Quick Sort implementation

Output:

Before Sorting :
[33, 21, 45, 64, 55, 34, 11, 8, 3, 5, 1] ==================
After Sorting :
[1, 3, 5, 8, 11, 21, 33, 34, 45, 55, 64]

## Time complexity

Best Case : `O(n log n)`
Average Case : `O(n log n)`
Worst Case : `O(n^2)`

That’s all about quick sort in java.

## Related Posts

• 04 November

### Topological Sort in java

Table of ContentsTopological Sort exampleTopological Sort AlgorithmWhy it works?Java program to implement topological sortingTime Complexity In this post, we will see about Topological Sorting in the graph. Topological Sorting is ordering of vertices or nodes such if there is an edge between (u,v) then u should come before v in topological sorting. Topological sort is […]

• 23 August

### Sort array in java

Table of ContentsJava Sort ArraySort Array of numbersSort Array of StringsSort array of custom objects In this post, we will see how to sort an array in java. There are various ways to sort array in java. You can implement different sorting algorithms to sort an array. You can use Arrays.sort method to sort array […]

• 12 October

### Selection sort in java

Table of ContentsSelection sort algorithmSelection sort algorithmTime complexity If you want to practice data structure and algorithm programs, you can go through data structure and algorithm interview programs. Selection sort is an in place comparison sorting algorithm. It is very simple to implement but it does not go well with large number of inputs. Selection sort […]

• 12 October

### Shell sort in java

Shell sort is in place comparison based sorting algorithm. It is generalization of insertion sort. It was invented by Donald shell. It allows to sort elements which are far apart. In case of insertion sort, comparison happens between only adjacent elements but in shell sort, it avoid comparing adjacent elements until last steps. Last step of shell […]

• 12 October

### Counting Sort in java

Table of ContentsSteps for Counting Sort:Java program for counting sort: Counting sort is special sorting technique used to sort elements between specific range. Lets say elements belong to range 1 to K , then Counting sort can be used to sort elements in O(N) times. Basic idea of counting sort to find number of elements […]

• 12 October

### Heap sort in java

Table of ContentsWhat is heap?Binary heapsUnderstanding complete binary treeTypes of heapsHeapifying an element:Steps for heap sortJava code for heap sortTime and space complexity In this post, we will see how to implement heap sort in java. I will divide heap sort in multiple parts to make it more understandable. What is heap? A heap is […]

## Subscribe to our newletter

Get quality tutorials to your inbox. Subscribe now.