w3resource

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 :

PHP Quick sort pictorial presentation
c # Quick sort part-2

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:

Flowchart: Sort an array  of given integers using Quick sort Algorithm.

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.



Follow us on Facebook and Twitter for latest update.

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

 





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