de.weaut.sortDemo

Class FastQSort

java.lang.Object

de.weaut.sortDemo.SortApp.SortAlgorithm

de.weaut.sortDemo.InsertionSort

de.weaut.sortDemo.FastQSort

public final class FastQSort
extends InsertionSort

Quick sort algorithm demonstration.

Author: James Gosling, Kevin A. Smith. their version 1.3, 29 Feb 1996

This was extended with TriMedian and InsertionSort by Denis Ahrens with all the tips from Robert Sedgewick (Algorithms in C++). It uses TriMedian and InsertionSort for lists shorts than 4.

Modif. 15.11.2005, Albrecht Weinert (a-weinert.de) :
SortApp.SortAlgorithm + minor improvements.

Version:

V.16, 16.03.2019

Author:

Albrecht Weinert

Field Summary

Fields inherited from class de.weaut.sortDemo.SortApp.SortAlgorithm

stopRequested

Constructor Summary

Constructors

Constructor and Description
FastQSort()

Method Summary

Modifier and Type	Method and Description
static void	main(java.lang.String[] args) Start as application.
(package private) void	quickSort(int[] a, int l, int r) A generic version of C.A.R Hoare's Quick Sort algorithm.
void	sort(int[] a) The real sorting method.

Methods inherited from class de.weaut.sortDemo.InsertionSort

insertionSort

Methods inherited from class de.weaut.sortDemo.SortApp.SortAlgorithm

getMaxPossiVal, pause, pause, pause, startMe, stop, swap

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

FastQSort

public FastQSort()

Method Detail

quickSort

void quickSort(int[] a,
               int l,
               int r)

A generic version of C.A.R Hoare's Quick Sort algorithm.

This method will handle arrays that are already sorted, and arrays with duplicate keys.

If you think of a one dimensional array as going from the lowest index on the left to the highest index on the right then the parameters to this procedure are lowest index or left and highest index or right. The first time you call this procedure it will be with the parameters 0, a.length - 1.

Parameters:

a - the array to be sorted

l - left boundary of array partition

r - right boundary of array partition

sort

public void sort(int[] a)

Description copied from class: SortApp.SortAlgorithm

The real sorting method.

This method has to sort the array provided as parameter. Every substantial algorithmic step has to be marked by calling one of the callback methods SortApp.SortAlgorithm.pause(int, int), SortApp.SortAlgorithm.pause(int), SortApp.SortAlgorithm.pause() directly or indirectly by utilising SortApp.SortAlgorithm.swap(int, int) for element exchanges within the array having been provided to this sort implementation.
This pausing does all else like counting steps, displaying the sorting state and else.

As substantial step to be treated this way we see

• Assignments respectively swaps within the array to be sorted
  and (only in a first loop through the array) also
• a reading / comparing access to to one or two elements.

Overrides:

sort in class InsertionSort

main

public static void main(java.lang.String[] args)

Start as application.

See Also:

SortApp.SortAlgorithm.startMe()