|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.ObjectSortingArrays
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 |
public SortingArrays()
Method Detail |
public static void selectionSort(java.lang.Comparable[] theArray, int n)
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.
theArray
- the array of elements to be sortedn
- the number of elements to be sortedpublic static void bubbleSort(java.lang.Comparable[] theArray, int n)
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.
theArray
- the array of elements to be sortedn
- the number of elements to be sortedpublic static void insertionSort(java.lang.Comparable[] theArray, int n)
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.
theArray
- the array of elements to be sortedn
- the number of elements to be sortedpublic static void mergesort(java.lang.Comparable[] theArray, int first, int last)
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.
theArray
- the array of elements to be sortedfirst
- an index into theArray, selecting the first element to be sortedlast
- an index into theArray, selecting the last element to be sortedpublic static void quickSort(java.lang.Comparable[] theArray, int first, int last)
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.
theArray
- the array of elements to be sortedfirst
- an index into theArray, selecting the first element to be sortedlast
- an index into theArray, selecting the last element to be sorted
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |