Odd-even sort

Odd-even sort

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 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. It can be thought of as using parallel processors, each using bubblesort but starting at different points in the list (all odd indices for the first step). This sorting algorithm is only marginally more difficult than bubble sort to implement.


Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

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

  • 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

  • Comparison sort — Sorting a set of unlabelled weights by weight using only a balance scale requires a comparison sort algorithm A comparison sort is a type of sorting algorithm that only reads the list elements through a single abstract comparison operation (often …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”