Odd–even sort

Odd–even sort
Odd–even sort
Example of odd-even transposition sort sorting a list of random numbers.
Example of odd-even transposition sort sorting a list of random numbers.
Class Sorting algorithm
Data structure Array
Worst case performance 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.

Contents

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". http://homepages.ihug.co.nz/~aurora76/Malc/Sorting_Array.htm#Exchanging Sort Techniques. 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, http://books.google.com/books?id=Mo2Q-TEwKGUC&pg=PA322 
  4. ^ Robert Sedgewick (2003). Algorithms in Java, Parts 1-4 (3rd ed.). Addison-Wesley Professional. pp. 454–464. ISBN 9780201361209. http://books.google.com/books?id=hyvdUQUmf2UC&pg=PA455. 
  5. ^ Allen Kent and James G. Williams (1993). Encyclopedia of Computer Science and Technology: Supplement 14. CRC Press. p. 33–38. ISBN 9780824722821. http://books.google.com/books?id=F9Y4oZ9qZnYC&pg=PA33. 

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


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

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