Class SortingArrays

java.lang.Object
  SortingArrays

public class SortingArrays

extends java.lang.Object

This is a collection of methods to sort an array.

Constructor Summary

SortingArrays()

Method Summary

static void	bubbleSort(java.lang.Comparable[] theArray, int n) Sorts the items in an array into ascending order, by repeatedly swapping adjacent items that are out of order.
static void	insertionSort(java.lang.Comparable[] theArray, int n) Sorts the items in an array into ascending order, by progressively inserting the i-th item in its correct position in the first i items.
static void	mergesort(java.lang.Comparable[] theArray, int first, int last) Sorts the items in an array into ascending order, by recursively sorting the first half of the elements, then the second half, and then merging them.
static void	quickSort(java.lang.Comparable[] theArray, int first, int last) Sorts the items in an array into ascending order, by using a pivot elements to divide the array into two parts, one which contains only elements smaller than the pivot element and one which contains only elements larger than the pivot element.
static void	selectionSort(java.lang.Comparable[] theArray, int n) Sorts the items in an array into ascending order, by selecting the largest item and putting it last; then selecting the next largest and putting it next to last; and so on.

Methods inherited from class java.lang.Object

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

Constructor Detail

SortingArrays

public SortingArrays()

Method Detail

selectionSort

public static void selectionSort(java.lang.Comparable[] theArray,
                                 int n)

Sorts the items in an array into ascending order, by selecting the largest item and putting it last; then selecting the next largest and putting it next to last; and so on. The elements of the input parameter theArray are re-ordered so that the array is sorted.

This sort requires O(n^2) compares and O(n) moves. It is a good sort to use when moves are much more expensive than compares.

Precondition: theArray is an array of n items implementing interface Comparable.
Postcondition: theArray is sorted into ascending order.

Parameters:

theArray - the array of elements to be sorted

n - the number of elements to be sorted

bubbleSort

public static void bubbleSort(java.lang.Comparable[] theArray,
                              int n)

Sorts the items in an array into ascending order, by repeatedly swapping adjacent items that are out of order. The elements of the input parameter theArray are re-ordered so that the array is sorted.

This sort requires O(n^2) moves and O(n^2) compares. It is simple, but not a very good way to sort an array.

Precondition: theArray is an array of n items implementing interface Comparable.
Postcondition: theArray is sorted into ascending order.

Parameters:

theArray - the array of elements to be sorted

n - the number of elements to be sorted

insertionSort

public static void insertionSort(java.lang.Comparable[] theArray,
                                 int n)

Sorts the items in an array into ascending order, by progressively inserting the i-th item in its correct position in the first i items. The elements of the input parameter theArray are re-ordered so that the array is sorted.

This sort requires O(n^2) moves and O(n^2) compares. It is simple, but not a very good way to sort an array.

Precondition: theArray is an array of n items implementing interface Comparable.
Postcondition: theArray is sorted into ascending order.

Parameters:

theArray - the array of elements to be sorted

n - the number of elements to be sorted

mergesort

public static void mergesort(java.lang.Comparable[] theArray,
                             int first,
                             int last)

Sorts the items in an array into ascending order, by recursively sorting the first half of the elements, then the second half, and then merging them. The elements of the input parameter theArray are re-ordered so that the array is sorted.

This sort requires O(n log n) moves and O(n log n) compares. This is a very efficient sort, and especially effective for files.

Precondition: theArray is an array of n items implementing interface Comparable.
Postcondition: theArray is sorted into ascending order.

Parameters:

theArray - the array of elements to be sorted

first - an index into theArray, selecting the first element to be sorted

last - an index into theArray, selecting the last element to be sorted

quickSort

public static void quickSort(java.lang.Comparable[] theArray,
                             int first,
                             int last)

Sorts the items in an array into ascending order, by using a pivot elements to divide the array into two parts, one which contains only elements smaller than the pivot element and one which contains only elements larger than the pivot element. Then each part is recursively sorted. The elements of the input parameter theArray are re-ordered so that the array is sorted.

This sort requires O(n^2) compares and O(n^2) moves in the worst case. However, the average case requires only O(n log n) moves and O(n log n) compares. This is a usually an efficient sort for arrays in random access memory.

Precondition: theArray is an array of n items implementing interface Comparable.
Postcondition: theArray is sorted into ascending order.

Parameters:

theArray - the array of elements to be sorted

first - an index into theArray, selecting the first element to be sorted

last - an index into theArray, selecting the last element to be sorted