analytics

Sunday, June 14, 2015

"Thresher": Sorting networks for 2^n inputs

As an example here is the "Thresher" sorting network for n=4 or 16 inputs, it has 99 comparators and 15 depth...

The pattern might be more obvious from looking at the code listed below but it is completely procedurally generated for any number of inputs that are a power of 2, and it's the same pattern every time. The 32 input network, for example, gets harder to draw but I found that it sorts random input as many times as I've tried... The depth for X inputs is always X-1...

This source code allows one to change in main the power of 2 of the size of the network, and it designs the Thresher network and tests it on a randomly ordered list of that size... The code runs really fast, it designed the 32 input Thresher sorting network and tested it almost instantly...
**Go Source Code**
package main
import (
    "fmt"    "math/rand"    "time")
func swap(l []int, x int, y int){
    if l[x] > l[y]{
        temp:=l[y]
        l[y]=l[x]
        l[x] = temp
    }
}
func y(l [] int, y int, a int, b int){
    for i:=a; i<=b; i*=2{
        x:=y
        j:=0        for x+i+j <= len(l)-1{
            fmt.Println(x+j, x+j+i)
            swap(l, x+j, x+j+i)
            j += 1            if j == i{
                x=x+j+i
                j = 0                            }
                    }
    }
}
func z(l [] int, y int, a int, b int){
    c:=0        for i:=a; i>b; i--{
        x:=y
        x+=c
        c+=1        j:=0        for x+j+i <= len(l)-1{
            fmt.Println(x+j, x+j+i)
            swap(l, x+j, x+j+i)
            j += 1            if j == i{
                x=x+j+i
                j = 0                            }
                    }
    }
}
func sortn(l [] int){
    c:=0    for i:=2; i <= len(l)/2; i*=2{
        y(l, c, 1, len(l)/i)
        c+=1        b:=len(l)/(2*i)
        if b > 1{
            z(l, c, len(l)/i-1, len(l)/(2*i))            }else{
            z(l, c, len(l)/i-1, 0)            }
            }
}
func main() {
    rand.Seed(time.Now().UTC().UnixNano())
    l := make([] int, 32)
    for i:=0; i<32; i++{
        l[i] = rand.Intn(100)
    }
    sortn(l)
    fmt.Println(l)
    }

No comments:

Post a Comment