**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

- Elements to be sorted are stored from "fromIndex" to "toIndex-1" inclusive.
- At the beginning of each iteration of loop, elements from "fromIndex+1" to "j" are lower in order than element at "fromIndex".
- At the beginning of each iteration of loop, elements from "j+1" to "i-1" are higher than or equal to element at "fromIndex" in order.
- If the element at "i" is lower than element at "fromIndex", we need to place it in the "lower" section by swapping it with element at "j+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