Class OArray<D extends java.lang.Comparable<D>>

java.lang.Object
  Array<D>
      OArray<D>

Type Parameters:

D - The type of the elements in the array. These elements must be comparable.

public class OArray<D extends java.lang.Comparable<D>>
extends Array<D>

An (O)rdered array is like an array but there additional methods to sort an array (quicksort() and heapsort()). Moreover, for a sorted array there are efficient methods to check whether an element is present in an array binsearch(Comparable). Finally, there are methods like insert(Comparable) and extract_min() which should only be used if the array has a heap-structure and which ensure that the heap-structure is guaranteed afterwards.

Author:

Rossmanith

See Also:

Comparable

Constructor Summary

OArray()

Method Summary

boolean	binsearch(D d) Performs a binary search of d, requires logarithmic time in the size of the array.
void	heapsort() Sorts this array in place in O(n log(n)) time using the heap-sort algorithm.
void	insert(D d) Inserts d into this array and preserves the heap-property if this array had the heap-property before the call to this method.
void	quicksort() Sorts this array using the quicksort-algorithm.

Methods inherited from class Array

get, isempty, iterator, permute_randomly, print, resize, set, size

Methods inherited from class java.lang.Object

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

Constructor Detail

OArray

public OArray()

Method Detail

heapsort

public void heapsort()

Sorts this array in place in O(n log(n)) time using the heap-sort algorithm.

insert

public void insert(D d)

Inserts d into this array and preserves the heap-property if this array had the heap-property before the call to this method.

Parameters:

d - The data to insert.

quicksort

public void quicksort()

Sorts this array using the quicksort-algorithm. (with runtimes O(n log(n)) in the average, and O(n²) in the worst case. The worst case occurs for example when invoking quicksort on an already sorted array.)

binsearch

public boolean binsearch(D d)

Performs a binary search of d, requires logarithmic time in the size of the array. Requires that this array is sorted.

Parameters:

d - The data to search for

Returns:

true iff d is contained in this array.