asd_library.sorting
Class SortingAlgorithms

java.lang.Object
  |
  +--asd_library.sorting.SortingAlgorithms

public class SortingAlgorithms
extends java.lang.Object

A collection of static methods implementing a wide variety of sorting algorithms.


Field Summary
(package private) static java.lang.Comparable[] temp
          static variable used by merge();
 
Constructor Summary
SortingAlgorithms()
           
 
Method Summary
static void insertionsort(java.lang.Comparable[] data)
          Scans successive elements for out of order item, then insert the item in the proper place.
static void insertionsort(java.lang.Comparable[] data, int first, int last)
          Scans successive elements for out of order item, then insert the item in the proper place of the segment between the index first and last.
protected static void merge(java.lang.Comparable[] data, int first, int last)
          Merges the two sorted halves of a segment into a only one ordered segment.
static void mergesort(java.lang.Comparable[] data)
          Calls the recursive method mergesort(Comparable[] data, int first, int last)
static void mergesort(java.lang.Comparable[] data, int first, int last)
          Divides recursively the array to order in two half up to find segments of length 1.
static void quicksort(java.lang.Comparable[] data)
          Finds the largest element and put it at the end of data then calls the recursive method quicksort(Comparable[] data, int first, int last)
static void quicksort(java.lang.Comparable[] data, int first, int last)
          Partitions array into two segments: the first segment all elements are less than or equal to the pivot value (bound), the second segment all elements are greater or equal to the pivot value.
static void quicksort2(java.lang.Comparable[] data)
          Finds the largest element and puts it at the end of data then calls the method quicksort2(Comparable[] data, int first, int last).
static void quicksort2(java.lang.Comparable[] data, int first, int last)
          quicksort2 uses insertionsort in recursion when size of sub-array < 30.
static void selectionsort(java.lang.Comparable[] data)
          Finds the least element in the array, and put it in the proper place.
protected static void swap(java.lang.Object[] a, int e1, int e2)
          Swaps element in position e1 with that in position e2
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

temp

static java.lang.Comparable[] temp
static variable used by merge();

Constructor Detail

SortingAlgorithms

public SortingAlgorithms()
Method Detail

swap

protected static void swap(java.lang.Object[] a,
                           int e1,
                           int e2)
Swaps element in position e1 with that in position e2

Parameters:
a - object array to sort.
e1 -
e2 -

insertionsort

public static void insertionsort(java.lang.Comparable[] data)
Scans successive elements for out of order item, then insert the item in the proper place. Sorts small array fast, big array very slowly.

Parameters:
data - array to sort.

selectionsort

public static void selectionsort(java.lang.Comparable[] data)
Finds the least element in the array, and put it in the proper place. Repeats until array is sorted.

Parameters:
data - array to sort.

quicksort

public static void quicksort(java.lang.Comparable[] data,
                             int first,
                             int last)
Partitions array into two segments: the first segment all elements are less than or equal to the pivot value (bound), the second segment all elements are greater or equal to the pivot value. Sorts the two segments recursively. Quicksort is fastest on average, but sometimes unbalanced partitions can lead to very slow sorting.

Parameters:
data - array which the segment to order belongs to.
first - is the index of the first element in the segment.
last - is the index of the last element in the segment.

quicksort

public static void quicksort(java.lang.Comparable[] data)
Finds the largest element and put it at the end of data then calls the recursive method quicksort(Comparable[] data, int first, int last)

Parameters:
data - array to sort.

insertionsort

public static void insertionsort(java.lang.Comparable[] data,
                                 int first,
                                 int last)
Scans successive elements for out of order item, then insert the item in the proper place of the segment between the index first and last. Is called by the method quicksort2(Comparable[] data, int first, int last).

Parameters:
data - array which the segment to order belongs to.
first - is the index of the first element in the segment.
last - is the index of the last element in the segment.

quicksort2

public static void quicksort2(java.lang.Comparable[] data,
                              int first,
                              int last)
quicksort2 uses insertionsort in recursion when size of sub-array < 30.

Parameters:
data - data array which the segment to order belongs to.
first - is the index of the first element in the segment.
last - is the index of the last element in the segment.

quicksort2

public static void quicksort2(java.lang.Comparable[] data)
Finds the largest element and puts it at the end of data then calls the method quicksort2(Comparable[] data, int first, int last).

Parameters:
data - array to sort.

merge

protected static void merge(java.lang.Comparable[] data,
                            int first,
                            int last)
Merges the two sorted halves of a segment into a only one ordered segment.

Parameters:
data - array which the segment to order belongs to.
first - is the index of the first element in the segment.
last - is the index of the last element in the segment.

mergesort

public static void mergesort(java.lang.Comparable[] data,
                             int first,
                             int last)
Divides recursively the array to order in two half up to find segments of length 1. Therefore calls the merge(Comparable[] data, int first, int last) method which merge into a single run of twice the length.

Parameters:
data - array which the segment to order belongs to.
first - is the index of the first element in the segment.
last - is the index of the last element in the segment.

mergesort

public static void mergesort(java.lang.Comparable[] data)
Calls the recursive method mergesort(Comparable[] data, int first, int last)

Parameters:
data - array to sort.