Class SortingArrays

java.lang.Object
  extended bySortingArrays

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