# Odd–even sort

Odd–even sort
Class Example of odd-even transposition sort sorting a list of random numbers. Sorting algorithm Array O(n2)

In computing, an odd–even sort or odd–even transpostion sort (also known as brick sort[1]) is a relatively simple sorting algorithm, developed originally for use on parallel processors with local interconnections. It is a comparison sort related to bubble sort, with which it shares many characteristics. It functions by comparing all (odd, even)-indexed pairs of adjacent elements in the list and, if a pair is in the wrong order (the first is larger than the second) the elements are switched. The next step repeats this for (even, odd)-indexed pairs (of adjacent elements). Then it alternates between (odd, even) and (even, odd) steps until the list is sorted.

## Sorting on processor arrays

On parallel processors, with one value per processor and only local left–right neighbor connections, the processors all concurrently do a compare–exchange operation with their neighbors, alternating between odd–even and even–odd pairings. This algorithm was originally presented, and shown to be efficient on such processors, by Habermann in 1972.[2]

The algorithm extends efficiently to the case of multiple items per processor. In the Baudet–Stevenson odd–even merge-splitting algorithm, each processor sorts its own sublist at each step, using any efficient sort algorithm, and then performs a merge splitting, or transposition–merge, operation with its neighbor, with neighbor pairing alternating between odd–even and even–odd on each step.[3]

## Batcher's odd–even mergesort

A related but more efficient sort algorithm is the Batcher odd–even mergesort, using compare–exchange operations and perfect-shuffle operations.[4] Batcher's method is efficient on parallel processors with long-range connections.[5]

## Algorithm

The single-processor algorithm, like bubblesort, is simple but not very efficient. Here a zero-based index is assumed:

```/* Assumes a is an array of values to be sorted. */
var sorted = false;
while(!sorted)
{
sorted=true;
for(var i = 1; i < list.length-1; i += 2)
{
if(a[i] > a[i+1])
{
swap(a, i, i+1);
sorted = false;
}
}

for(var i = 0; i < list.length-1; i += 2)
{
if(a[i] > a[i+1])
{
swap(a, i, i+1);
sorted = false;
}
}
}
```

## References

1. ^ Phillips, Malcolm. Sort Techniques "Array Sorting". Retrieved 3 August 2011.
2. ^ N. Haberman (1972) "Parallel Neighbor Sort (or the Glory of the Induction Principle)," CMU Computer Science Report (available as Technical report AD-759 248, National Technical Information Service, US Department of Commerce, 5285 Port Royal Rd Sprigfield VA 22151).
3. ^ S. Lakshmivarahan, S. K. Dhall, and L. L. Miller (1984), Franz L. Alt and Marshall C. Yovits, ed., "Parallel Sorting Algorithms", Advances in computers (Academic Press) 23: 295–351, ISBN 9780120121236
4. ^ Robert Sedgewick (2003). Algorithms in Java, Parts 1-4 (3rd ed.). Addison-Wesley Professional. pp. 454–464. ISBN 9780201361209.
5. ^ Allen Kent and James G. Williams (1993). Encyclopedia of Computer Science and Technology: Supplement 14. CRC Press. p. 33–38. ISBN 9780824722821.

Wikimedia Foundation. 2010.

### См. также в других словарях:

• Odd-even sort — is a relatively simple sorting algorithm. It is a comparison sort based on bubble sort with which it shares many characteristics. It functions by comparing all (odd, even) indexed pairs of adjacent elements in the list and, if a pair is in the… …   Wikipedia

• Batcher odd–even mergesort — Visualization of the odd–even mergesort network with eight inputs Batcher s odd–even mergesort is a generic construction devised by Ken Batcher for sorting networks of size O(n (log n)2) and depth O((log n)2), where n is the number …   Wikipedia

• Odd Blood — Studio album by Yeasayer Released February 8, 2010 …   Wikipedia

• Merge sort — Example of merge sort sorting a list of random dots. Class Sorting algorithm Data structure Array Worst case performance O(n log n) …   Wikipedia

• Counting sort — In computer science, counting sort is an algorithm for sorting a collection of objects according to keys that are small integers; that is, it is an integer sorting algorithm. It operates by counting the number of objects that have each distinct… …   Wikipedia

• Comb sort — Class Sorting algorithm Data structure Array Worst case performance O(n log n)[1] …   Wikipedia

• Cocktail sort — Class Sorting algorithm Data structure Array Worst case performance О(n²) Best case performance O(n) …   Wikipedia

• Pigeonhole sort — Class Sorting algorithm Data structure Array Worst case performance O(N + n), where N is the range of key values and n is the input size Worst case space complexity O(N * n) …   Wikipedia

• Cycle sort — Example of cycle sort sorting a list of random numbers. Class Sorting algorithm Data structure Array Worst case performance Θ(n2) …   Wikipedia

• Bubble sort — Infobox Algorithm class=Sorting algorithm data=Array time= О(n²) space= О(n) total, O(1) auxiliary optimal=NoBubble sort is a simple sorting algorithm. It works by repeatedly stepping through the list to be sorted, comparing two items at a time… …   Wikipedia

### Поделиться ссылкой на выделенное

##### Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»