ObjectiveLib: Sorting

Many ways of sorting can be performed, including various partial sorts and stable sorts. Since sorting requires random access iterators some containers cannot be sorted using the generic algorithms. In these cases the container will provide its own sorting messages. Additionally, sorting algorithms should not be used with containers that are inherently sorted. These include all associative containers, like OLMap and OLSet, and the containers based on hash tables, like OLHashMap and OLHashSet.

Function Documentation

+ (BOOL) isSortedFrom:	(OLForwardIterator *)	first
to:	(OLForwardIterator *)	last

Test whether a given range is sorted.

This message simply sends the message isSortedFrom:to:predicate: using OLLess as the predicate.

Parameters:

	first	the first in the range of elements to test
	last	one position beyond the last in the range of elements to test

Returns:: YES if the range is sorted, NO otherwise

+ (BOOL) isSortedFrom:	(OLForwardIterator *)	first
to:	(OLForwardIterator *)	last
predicate:	(id< OLBoolBinaryFunction >)	pred

Test whether a given range is sorted.

The range [first, last) is tested to determine whether it is in the order defined by pred.

Parameters:

	first	the first in the range of elements to test
	last	one position beyond the last in the range of elements to test
	pred	the function object that defines the sorting order

Returns:: YES if the range is sorted, NO otherwise

+ (void) nthElementFrom:	(OLRandomAccessIterator *)	first
nth:	(OLRandomAccessIterator *)	mid
to:	(OLRandomAccessIterator *)	last

Partially sort a given range.

This message simply sends the message nthElementFrom:nth:to:predicate: using OLLess as the predicate.

Parameters:

	first	the first in the range of elements to sort
	mid	the element by which to determine the partial sort
	last	one position beyond the last in the range of elements to sort

+ (void) nthElementFrom:	(OLRandomAccessIterator *)	first
nth:	(OLRandomAccessIterator *)	mid
to:	(OLRandomAccessIterator *)	last
predicate:	(id< OLBoolBinaryFunction >)	pred

Partially sort a given range.

The message reorders the elements in the range [first, last) such that every element in the range [first, nth) satisfies the predicate pred when compared to every element in the range [nth, last). For example, if the predicate is an instance of OLLess, then every element in the range [first, nth) will be less than every element in the range [nth, last).

This message is similar to partialSortFrom:middle:to:predicate: except that it does less work. It does not actually sort the elements; it just partitions the sequence around the value of mid.

Parameters:

	first	the first in the range of elements to sort
	mid	the element by which to determine the partial sort
	last	one position beyond the last in the range of elements to sort
	pred	the function object used to compare elements

+ (OLRandomAccessIterator*) partialSortCopyFrom:	(OLForwardIterator *)	first
to:	(OLForwardIterator *)	last
destinationFrom:	(OLRandomAccessIterator *)	rFirst
destinationTo:	(OLRandomAccessIterator *)	rLast

Partially sort a given range.

This message simply sends the message partialSortCopyFrom:to:destinationFrom:destinationTo:predicate: using OLLess as the predicate.

Parameters:

	first	the first in the range of elements to sort
	last	one position beyond the last in the range of elements to sort
	rFirst	the first in the destination range
	rLast	one position beyond the last in the destination range

Returns:: an iterator pointing to one position beyond the last element copied

+ (OLRandomAccessIterator*) partialSortCopyFrom:	(OLForwardIterator *)	first
to:	(OLForwardIterator *)	last
destinationFrom:	(OLRandomAccessIterator *)	rFirst
destinationTo:	(OLRandomAccessIterator *)	rLast
predicate:	(id< OLBoolBinaryFunction >)	pred

Partially sort a given range.

Elements from the range [first, last) are copied to the destination rFirst. The number of elements copied is the lesser of the distance from first to last and the distance from rFirst to rLast. The elements are copied in the order determined by the predicate pred.

An iterator is returned pointing to one position beyond the last element copied to the destination.

Note:: If OpenStep is present the returned object will be autoreleased before being returned.

Parameters:

	first	the first in the range of elements to sort
	last	one position beyond the last in the range of elements to sort
	rFirst	the first in the destination range
	rLast	one position beyond the last in the destination range
	pred	the function object used to determine the sorting order

Returns:: an iterator pointing to one position beyond the last element copied

+ (void) partialSortFrom:	(OLRandomAccessIterator *)	first
middle:	(OLRandomAccessIterator *)	mid
to:	(OLRandomAccessIterator *)	last

Partially sort a given range.

This message simple sends the message partialSortFrom:middle:to:predicate: using OLLess as the predicate.

Parameters:

	first	the first in the range of elements to sort
	mid	the middle position which defines the length of the resulting sorted range
	last	one position beyond the last in the range of elements to sort

+ (void) partialSortFrom:	(OLRandomAccessIterator *)	first
middle:	(OLRandomAccessIterator *)	mid
to:	(OLRandomAccessIterator *)	last
predicate:	(id< OLBoolBinaryFunction >)	pred

Partially sort a given range.

The elements in the range [first, last) are sorted such that afterwards the range [first, mid) contains elements that satisfy the order defined by pred and the remaining elements are placed in unspecified order in the range [mid, last). For example, if the predicate is an instance of OLLess, then the smallest elements will be placed in ascending order in the range [first, mid).

Parameters:

	first	the first in the range of elements to sort
	mid	the middle position which defines the length of the resulting sorted range
	last	one position beyond the last in the range of elements to sort
	pred	the function object used to determine the sorting order

+ (void) sortFrom:	(OLRandomAccessIterator *)	first
to:	(OLRandomAccessIterator *)	last

Sort a given range.

This message simply sends the message sortFrom:to:predicate: using OLLess as the predicate.

Parameters:

	first	the first in the range of elements to sort
	last	one position beyond the last in the range of elements to sort

+ (void) sortFrom:	(OLRandomAccessIterator *)	first
to:	(OLRandomAccessIterator *)	last
predicate:	(id< OLBoolBinaryFunction >)	pred

Sort a given range.

The elements in the range [first, last) are placed in the order defined by the predicate pred.

Parameters:

	first	the first in the range of elements to sort
	last	one position beyond the last in the range of elements to sort
	pred	the function object used to determine the sorting order

+ (void) sortHeapFrom:	(OLRandomAccessIterator *)	first
to:	(OLRandomAccessIterator *)	last

Sort a heap.

This message simply sends the message sortHeapFrom:to:predicate: using OLLess as the predicate.

Precondition:: The range [first, last) must be a heap that was created using the predicate pred. That is, isHeapFrom:to:predicate: must return YES when given first, last and pred as arguments.

Parameters:

	first	the first in the range of elements to sort
	last	one position beyond the last in the range of elements to sort

See also:: Heaps

+ (void) sortHeapFrom:	(OLRandomAccessIterator *)	first
to:	(OLRandomAccessIterator *)	last
predicate:	(id< OLBoolBinaryFunction >)	pred

Sort a heap.

The elements in the range [first, last) are placed in the order defined by the predicate pred.

Precondition:: The range [first, last) must be a heap that was created using the predicate pred. That is, isHeapFrom:to:predicate: must return YES when given first, last and pred as arguments.

Parameters:

	first	the first in the range of elements to sort
	last	one position beyond the last in the range of elements to sort
	pred	the function object used to determine the sorting order

See also:: Heaps

+ (void) stableSortFrom:	(OLRandomAccessIterator *)	first
to:	(OLRandomAccessIterator *)	last

Sort a given range stably.

This message simply sends the message stableSortFrom:to:predicate: using OLLess as the predicate.

Parameters:

	first	the first in the range of elements to sort
	last	one position beyond the last in the range of elements to sort

+ (void) stableSortFrom:	(OLRandomAccessIterator *)	first
to:	(OLRandomAccessIterator *)	last
predicate:	(id< OLBoolBinaryFunction >)	pred

Sort a given range stably.

This message is similar to sortFrom:to:predicate: except that the sort is done stably. A stable sort is one in which the original order of equivilent elements is not disrupted. The resulting sequence will be in the order defined by the predicate pred, but the relative order of equivilent elements will not change.

Parameters:

	first	the first in the range of elements to sort
	last	one position beyond the last in the range of elements to sort
	pred	the function object used to determine the sorting order

Sorting
[Algorithms]

Sorting

Detailed Description

Function Documentation


Sorting
(BOOL)	+ isSortedFrom:to:
	Test whether a given range is sorted.
(BOOL)	+ isSortedFrom:to:predicate:
	Test whether a given range is sorted.
(void)	+ nthElementFrom:nth:to:
	Partially sort a given range.
(void)	+ nthElementFrom:nth:to:predicate:
	Partially sort a given range.
(OLRandomAccessIterator *)	+ partialSortCopyFrom:to:destinationFrom:destinationTo:
	Partially sort a given range.
(OLRandomAccessIterator *)	+ partialSortCopyFrom:to:destinationFrom:destinationTo:predicate:
	Partially sort a given range.
(void)	+ partialSortFrom:middle:to:
	Partially sort a given range.
(void)	+ partialSortFrom:middle:to:predicate:
	Partially sort a given range.
(void)	+ sortFrom:to:
	Sort a given range.
(void)	+ sortFrom:to:predicate:
	Sort a given range.
(void)	+ sortHeapFrom:to:
	Sort a heap.
(void)	+ sortHeapFrom:to:predicate:
	Sort a heap.
(void)	+ stableSortFrom:to:
	Sort a given range stably.
(void)	+ stableSortFrom:to:predicate:
	Sort a given range stably.

Sorting [Algorithms]

Sorting

Detailed Description

Function Documentation

Sorting
[Algorithms]