JAVA EXAMPLE PROGRAMS

JAVA EXAMPLE PROGRAMS

Publish Your Article Here

Program: Implement quick sort in java.


Quicksort or partition-exchange sort, is a fast sorting algorithm, which is using divide and conquer algorithm. Quicksort first divides a large list into two smaller sub-lists: the low elements and the high elements. Quicksort can then recursively sort the sub-lists.

Steps to implement Quick sort:

1) Choose an element, called pivot, from the list. Generally pivot can be the middle index element.
2) Reorder the list so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.
3) Recursively apply the above steps to the sub-list of elements with smaller values and separately the sub-list of elements with greater values.

Quick Sort


The complexity of quick sort in the average case is Θ(n log(n)) and in the worst case is Θ(n2).


package com.java2novice.sorting;

public class MyQuickSort {
	
	private int array[];
	private int length;

	public void sort(int[] inputArr) {
		
		if (inputArr == null || inputArr.length == 0) {
			return;
		}
		this.array = inputArr;
		length = inputArr.length;
		quickSort(0, length - 1);
	}

	private void quickSort(int lowerIndex, int higherIndex) {
		
		int i = lowerIndex;
		int j = higherIndex;
		// calculate pivot number, I am taking pivot as middle index number
		int pivot = array[lowerIndex+(higherIndex-lowerIndex)/2];
		// Divide into two arrays
		while (i <= j) {
			/**
			 * In each iteration, we will identify a number from left side which 
			 * is greater then the pivot value, and also we will identify a number 
			 * from right side which is less then the pivot value. Once the search 
			 * is done, then we exchange both numbers.
			 */
			while (array[i] < pivot) {
				i++;
			}
			while (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 (lowerIndex < j)
			quickSort(lowerIndex, j);
		if (i < higherIndex)
			quickSort(i, higherIndex);
	}

	private void exchangeNumbers(int i, int j) {
		int temp = array[i];
		array[i] = array[j];
		array[j] = temp;
	}
	
	public static void main(String a[]){
		
		MyQuickSort sorter = new MyQuickSort();
	    int[] input = {24,2,45,20,56,75,2,56,99,53,12};
	    sorter.sort(input);
	    for(int i:input){
	    	System.out.print(i);
	    	System.out.print(" ");
	    }
	}
}

Output:
2 2 12 20 24 45 53 56 56 75 99 
<< Previous Program | Next Program >>

Tech Tip : Software developer can take a positive steps towards being productive by moving their software testing and debugging environment into the cloud with virtual desktop from www.CloudDesktopOnline.com with 24*7 dedicated migration support from Apps4Rent.com.

Java Sorting Algorithms Examples

  1. Implement bubble sort in java.
  2. Implement selection sort in java.
  3. Implement insertion sort in java.
  4. Implement quick sort in java.
  5. Implement merge sort in java.
Knowledge Centre
Interface and its usage
Interface is similar to a class which may contain method's signature only but not bodies and it is a formal set of method and constant declarations that must be defined by the class that implements it. Interfaces are useful for declaring methods that one or more classes are expected to implement, capturing similarities between unrelated classes without forcing a class relationship and determining an object's programming interface without revealing the actual body of the class.
Famous Quotations
Discipline is just choosing between what you want now and what you want most.
-- Unknown Author

About Author

I'm Nataraja Gootooru, programmer by profession and passionate about technologies. All examples given here are as simple as possible to help beginners. The source code is compiled and tested in my dev environment.

If you come across any mistakes or bugs, please email me to [email protected].

Most Visited Pages

Other Interesting Sites

Reference: Java™ Platform Standard Ed. 7 - API Specification | Java™ Platform Standard Ed. 8 - API Specification | Java is registered trademark of Oracle.
Privacy Policy | Copyright © 2022 by Nataraja Gootooru. All Rights Reserved.