Bitonic sorting algorithm

This is a discussion on Bitonic sorting algorithm within the Tech Board forums, part of the Community Boards category; Let's assume we want to apply bitonic sorting in this example input: 12, 4, 9, 7, 5, 8, 1, 10, ...

  1. #1
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,694

    Bitonic sorting algorithm

    Let's assume we want to apply bitonic sorting in this example input:

    12, 4, 9, 7, 5, 8, 1, 10, 4, 14, 6, 11, 7, 2, 0, 3

    I admit I have no understanding of bitonic sorting algorithm, so if one wants to be scholastic, do not hesitate from being!

    Actually my real problem is how to convert this sequence of numbers in a bitonic sequence :/

    //Thanks in advance
    Last edited by std10093; 06-25-2013 at 07:35 PM.
    Code - functions and small libraries I use


    It’s 2014 and I still use printf() for debugging.


    "Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson

  2. #2
    Registered User
    Join Date
    Apr 2013
    Posts
    1,340
    It's meant to be used for parallel merge like sorting, except that the created subgroups alternate between ascending and descending sequences:

    Links to articles:

    Bitonic sorter - Wikipedia, the free encyclopedia

    Bitonic Sort: Overview

    As mentioned in the articles, for a single threaded environment, it's slower than a normal (bottom up) merge sort, but can be faster if used in a parallel environment. I'm not sure about a multi-threaded version, since there's only a single main memory bus, and typically the outer cache is shared between cores, so the only parallel memory operations take place in the inner cache for each core.
    Last edited by rcgldr; 06-25-2013 at 08:23 PM.

  3. #3
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,694
    The bitonic sequence would be

    1, 5, 7, 8, 9, 10, 12, 15, 14, 13, 11, 6, 4, 3, 2, 07

    This is a good example. I had found the links you provided, but they are no good to me
    Last edited by std10093; 06-25-2013 at 08:48 PM.
    Code - functions and small libraries I use


    It’s 2014 and I still use printf() for debugging.


    "Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson

  4. #4
    Registered User
    Join Date
    Apr 2013
    Posts
    1,340
    This example matches the first example from the wiki article.

    In the example you linked to, after the first pass, the first pair of the second half are descending, so the right half does not contain bitonic sub-sequences. In the case of both the wiki and overview algorithms, after the first pass, there are 4 bitonic sequence of size 4. After the second pass, there are 2 bitonic sequences of size 8. After the third pass, there is 1 bitonic sequence of size 16. After the fourth pass, the data is sorted.

    Code:
    12 04   09 07   05 13   08 01   10 14   06 11   15 02   00 03
    
    
    04 12 | 09 07 | 05 13 | 08 01 | 10 14 | 11 06 | 02 15 | 03 00
    
    04 07   09 12 | 08 13   05 01 | 10 06   11 14 | 03 15   02 00
    04 07 | 09 12 | 13 08 | 05 01 | 06 10 | 11 14 | 15 03 | 02 00
    
    04 07   05 01   13 08   09 12 | 15 10   11 14   06 03   02 00
    04 01   05 07 | 09 08   13 12 | 15 14   11 10 | 06 03   02 00
    01 04 | 05 07 | 08 09 | 12 13 | 15 14 | 11 10 | 06 03 | 02 00
    
    01 04   05 07   06 03   02 00   15 14   11 10   08 09   12 13
    01 03   02 00   06 04   05 07 | 08 09   11 10   15 14   12 13
    01 00   02 03 | 05 04   06 07 | 08 09   11 10 | 12 13   15 14
    00 01 | 02 03 | 04 05 | 06 07 | 08 09 | 10 11 | 12 13 | 14 15
    update - The purpose of using bitonic sequences for a hardware based sort is that for each phase of each pass of the sort, the distance between compared values is fixed, which would reduce variation in propagation delays. I'm not sure if there's any advantage for a software based sort.
    Last edited by rcgldr; 06-25-2013 at 09:53 PM.

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    For bitonic sorting, you don't start off by making that into a bitonic sequence. That's just a step along the way, though it certainly depends on the order you do things. As a bitonic sorter is really just a static sorting network, there are a few different ways in which you can structure that sorting network.

    From the point of view of understanding the algorithm, the way you need to think about it is:
    If I already have two bitonic sequences, how can I merge to two to become a single monotonic sequence, in either ascending or descending direction?
    You can then look at the base case where any sequence of exactly two items is already a bitonic sequence consisting of 1 item in ascending order followed by 1 item in descending order. Then you apply the recursive step.
    So you never have to think about how you get to a bitonic sequence at all. You always just think of how you transform a bitonic sequence into a monotonic sequence.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  6. #6
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,694
    I got the idea by the example I provided, but thank you for your answers
    Code - functions and small libraries I use


    It’s 2014 and I still use printf() for debugging.


    "Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson

  7. #7
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,694
    //post no. 3, the bitonic sequence provided is obviously wrong. (it is not the corresponding sequence for the sequence in the 1st post).
    Code - functions and small libraries I use


    It’s 2014 and I still use printf() for debugging.


    "Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. sorting algorithm logic
    By cfanatic in forum C Programming
    Replies: 3
    Last Post: 10-08-2012, 03:33 PM
  2. Online sorting algorithm
    By mdtanos in forum C Programming
    Replies: 10
    Last Post: 03-06-2012, 12:08 AM
  3. Sorting Algorithm Help
    By cjwenigma in forum C++ Programming
    Replies: 8
    Last Post: 11-02-2007, 03:04 PM
  4. sorting algorithm
    By RazielX in forum C Programming
    Replies: 4
    Last Post: 05-04-2004, 07:20 PM
  5. 'Sorting' algorithm
    By Dual-Catfish in forum C++ Programming
    Replies: 3
    Last Post: 11-03-2001, 02:09 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21