comparing numbers to sort then get median value

问题:

Sorting five integers using bitwise or comparison operators can be achieved by first getting the highest number then the second highest then the third and so on.

Here is my code in getting the highest number:

#include <stdio.h>

int main() {
    int a, b, c, d, e;
    int aa, bb, cc, dd, ee;

    a = 4; b = 2; c = 5; d = 1; e = 3;

    aa = (a > b) ?
         ((a > c) ? ((a > d) ? ((a > e) ? a : e) : ((d > e) ? d : e)) :
                    ((c > d) ? ((c > e) ? c : e) : ((d > e) ? d : e))) :
         ((b > c) ? ((b > d) ? ((b > e) ? b : e) : ((d > e) ? d : e)) :
                    ((c > d) ? ((c > e) ? c : e) : ((d > e) ? d : e)));


    printf("highest: %d\n", aa);
    return 0;
}

I think getting the second, third, forth and fifth highest number could be possible using this method.

Is there any other way in getting the median of five integers using comparison/bitwise operators? any other combinatorial method might be valid.

By the way, I'm going to implement this algorithm in hardware.

Using combinatorial method in sorting will be fast rather than using a state machine.

回答1:

One way to think about it is to consider the 10 comparison operations between the 5 numbers as your binary inputs. Then you have options:

1. Draw a 10-input Karnaugh map and simplify the logic where possible.
2. Build a 10-bit number as an index into a table.

Some of the possibilities will never occur, so I'm sure there's some simplification possible. For instance if (a>b) and (b>c) then (a>c) will always be true. Which will help with approach #1 and generates an error case in approach #2.

回答2:

The third highest number of five integers is the median, so if you get the third highest number you are fine.

回答3:

UPDATE

I made a combinatorial sorting in verilog using sorting networks.

module comparator(
    input [31:0] a_1,
    input [31:0] b_1,
    output reg [31:0] a_0,
    output reg [31:0] b_0
);

    always @(a_1, b_1) begin
        if (a_1 > b_1) begin
            a_0 = a_1;
            b_0 = b_1;
        end
        else begin
            a_0 = b_1;
            b_0 = a_1;
        end
    end
endmodule

module sorting_test;
    reg [31:0] a, b, c, d, e;
    wire [31:0] aa, bb, cc, dd, ee;
    reg clk;

    initial begin
        $dumpfile("sorting.vcd");
        $dumpvars();
        #10 $finish;
    end

    initial begin
        clk = 0;
    end

    always #1 clk = ~clk;

    initial begin
        a = 0;
        b = 0;
        c = 0;
        d = 0;
        e = 0;


        #1
        a = 4;
        b = 1;
        c = 2;
        d = 5;
        e = 3;
        #1
        a = 1;
        b = 16;
        c = 12;
        d = 14;
        e = 15;

        #1
        a = 1;
        b = 4;
        c = 9;
        d = 19;
        e = 2;

        #1
        a = 16;
        b = 11;
        c = 12;
        d = 16;
        e = 12;

        #1  
        a = 16;
        b = 17;
        c = 11;
        d = 15;
        e = 3;

        #1  
        a = 13;
        b = 9;
        c = 2;
        d = 1;
        e = 18;

        #1  
        a = 17;
        b = 3;
        c = 8;
        d = 3;
        e = 14;

        #1  
        a = 14;
        b = 10;
        c = 9;
        d = 14;
        e = 14;

        #1  
        a = 15;
        b = 12;
        c = 13;
        d = 10;
        e = 19;

        #1  
        a = 6;
        b = 8;
        c = 7;
        d = 16;
        e = 15;

        #1  
        a = 10;
        b = 17;
        c = 18;
        d = 1;
        e = 16;
    end

    wire [31:0] a1, b1, c1, d1, b2, c2, d2, e2, a2, b3, c3, d3, b4, c4, d4, e4, a5, b5, c5, d5;
    comparator c1l1( a,  b, a1, b1);
    comparator c2l1( c,  d, c1, d1);
    comparator c1l2(b1, c1, b2, c2);
    comparator c2l2(d1,  e, d2, e2);
    comparator c1l3(a1, b2, a2, b3);
    comparator c2l3(c2, d2, c3, d3);
    comparator c1l4(b3, c3, b4, c4);
    comparator c2l4(d3, e2, d4, e4);
    comparator c1l5(a2, b4, a5, b5);
    comparator c2l6(c4, d4, c5, d5);

    assign aa = a5;
    assign bb = b5;
    assign cc = c5;
    assign dd = d5;
    assign ee = e4;

endmodule

@Steve Jessop thank you for providing information.

To @David Winant and @sth for providing ideas. =)