Java: Quick sort Algorithm
Java Sorting Algorithm: Exercise-1 with Solution
Write a Java program to sort an array of given integers using the Quick sort algorithm.
Quick sort is a comparison sort, meaning it can sort items of any type for which a "less-than" relation (formally, a total order) is defined.
Pictorial presentation - Quick Sort algorithm :


Sample Solution:
Java Code:
import java.util.Arrays;
public class QuickSort {
private int temp_array[];
private int len;
public void sort(int[] nums) {
if (nums == null || nums.length == 0) {
return;
}
this.temp_array = nums;
len = nums.length;
quickSort(0, len - 1);
}
private void quickSort(int low_index, int high_index) {
int i = low_index;
int j = high_index;
// calculate pivot number
int pivot = temp_array[low_index+(high_index-low_index)/2];
// Divide into two arrays
while (i <= j) {
while (temp_array[i] < pivot) {
i++;
}
while (temp_array[j] > pivot) {
j--;
}
if (i <= j) {
exchangeNumbers(i, j);
//move index to next position on both sides
i++;
j--;
}
}
// call quickSort() method recursively
if (low_index < j)
quickSort(low_index, j);
if (i < high_index)
quickSort(i, high_index);
}
private void exchangeNumbers(int i, int j) {
int temp = temp_array[i];
temp_array[i] = temp_array[j];
temp_array[j] = temp;
}
// Method to test above
public static void main(String args[])
{
QuickSort ob = new QuickSort();
int nums[] = {7, -5, 3, 2, 1, 0, 45};
System.out.println("Original Array:");
System.out.println(Arrays.toString(nums));
ob.sort(nums);
System.out.println("Sorted Array");
System.out.println(Arrays.toString(nums));
}
}
Sample Output:
Original Array: [7, -5, 3, 2, 1, 0, 45] Sorted Array [-5, 0, 1, 2, 3, 7, 45]
Flowchart:

Java Code Editor:
Contribute your code and comments through Disqus.
Previous: Java Sorting Exercises.
Next: Write a Java program to sort an array of given integers using the Bubble sorting Algorithm.
What is the difficulty level of this exercise?
Test your Programming skills with w3resource's quiz.
Java: Tips of the Day
Hashset vs Treeset:
HashSet is much faster than TreeSet (constant-time versus log-time for most operations like add, remove and contains) but offers no ordering guarantees like TreeSet.
HashSet
- the class offers constant time performance for the basic operations (add, remove, contains and size).
- it does not guarantee that the order of elements will remain constant over time
- iteration performance depends on the initial capacity and the load factor of the HashSet.
- It's quite safe to accept default load factor but you may want to specify an initial capacity that's about twice the size to which you expect the set to grow.
TreeSet
- guarantees log(n) time cost for the basic operations (add, remove and contains)
- guarantees that elements of set will be sorted (ascending, natural, or the one specified by you via its constructor) (implements SortedSet)
- doesn't offer any tuning parameters for iteration performance
- offers a few handy methods to deal with the ordered set like first(), last(), headSet(), and tailSet() etc
Important points:
- Both guarantee duplicate-free collection of elements
- It is generally faster to add elements to the HashSet and then convert the collection to a TreeSet for a duplicate-free sorted traversal.
- None of these implementations are synchronized. That is if multiple threads access a set concurrently, and at least one of the threads modifies the set, it must be synchronized externally.
- LinkedHashSet is in some sense intermediate between HashSet and TreeSet. Implemented as a hash table with a linked list running through it, however,it provides insertion-ordered iteration which is not same as sorted traversal guaranteed by TreeSet.
So a choice of usage depends entirely on your needs but I feel that even if you need an ordered collection then you should still prefer HashSet to create the Set and then convert it into TreeSet.
- e.g. SortedSet<String> s = new TreeSet<String>(hashSet);
Ref: https://bit.ly/3d3waGh
- Weekly Trends
- Java Basic Programming Exercises
- SQL Subqueries
- Adventureworks Database Exercises
- C# Sharp Basic Exercises
- SQL COUNT() with distinct
- JavaScript String Exercises
- JavaScript HTML Form Validation
- Java Collection Exercises
- SQL COUNT() function
- SQL Inner Join
- JavaScript functions Exercises
- Python Tutorial
- Python Array Exercises
- SQL Cross Join
- C# Sharp Array Exercises
We are closing our Disqus commenting system for some maintenanace issues. You may write to us at reach[at]yahoo[dot]com or visit us at Facebook