Sorting Algorithm Tutorials - Herong's Tutorial Examples - Version 6.01, by Dr. Herong Yang
Quicksort - Java Implementation
This section provides a tutorial on how to implement the Quicksort algorithm in Java. An implementation diagram is also provided.
Here is my Java implementation of Quicksort algorithm:
/** * HyArrays.java * This class contains sorting methods similar to java.util.Arrays. * All sorting methods should have a signature of * %Sort(Object[] a, int fromIndex, int toIndex) * where "fromIndex" is inclusive, and "toIndex" is exclusive. * Copyright (c) 2011 by Dr. Herong Yang, herongyang.com */ public class HyArrays { public static void quickSort(Object[] a, int fromIndex, int toIndex) { Object d; if (toIndex-1>fromIndex) { int j = fromIndex; for (int i=j+1; i<toIndex; i++) { if (((Comparable)a[fromIndex]).compareTo(a[i])>0) { j++; d = a[i]; a[i] = a[j]; a[j] = d; } } d = a[j]; a[j] = a[fromIndex]; a[fromIndex] = d; quickSort(a, fromIndex, j+1); quickSort(a, j+1, toIndex); } } }
The following diagram illustrates how this implementation works:
53--------------- 39 ... 92 | 67 ... 42 | | | | | +---+-----------+---+---+---+-------+---+---+---------------+ | | | | | 36 29 ... 17 24 ---------------11 | | | | fromIndex j i toIndex-1
Last update: 2011.
Table of Contents
Introduction of Sorting Algorithms
Java API for Sorting Algorithms
Insertion Sort Algorithm and Implementation
Selection Sort Algorithm and Implementation
Bubble Sort Algorithm and Implementation
►Quicksort Algorithm and Implementation
Quicksort - Algorithm Introduction
►Quicksort - Java Implementation
Quicksort - Implementation Improvements
Merge Sort Algorithm and Implementation
Heap Sort Algorithm and Implementation
Shell Sort Algorithm and Implementation