// ************************************************************************** // // // // eses eses // // eses eses // // eses eseses esesese eses Embedded Systems Group // // ese ese ese ese ese // // ese eseseses eseseses ese Department of Computer Science // // eses eses ese eses // // eses eseses eseseses eses University of Kaiserslautern // // eses eses // // // // ************************************************************************** // // CountSort is a simple algorithm that counts the number of array elements // // c[a[i]] that are less than or equal to a[i] so that the sorted array // // can be easily generated. The algorithm is linear in aSize, but requires // // two additional arrays b and c, where c is indexed by the range of array a. // // ************************************************************************** // macro aSize = 16; macro iSize = 64; module CountSort([aSize]nat{iSize} ?a,b, event !ready) { [iSize]nat{aSize+1} c; // count the number of occurrences of each a[i] for(i=0..aSize-1) { next(c[a[i]]) = c[a[i]]+1; w1: pause; } // count the number of elements less than or equal to a[i] for(i=1..aSize-1) { next(c[i]) = c[i]+c[i-1]; w2: pause; } // generate the sorted array for(i=0..aSize-1) { b[c[a[aSize-i-1]]-1] = a[aSize-i-1]; next(c[a[aSize-i-1]]) = c[a[aSize-i-1]]-1; w3: pause; } emit(ready); } drivenby Test01 { for(i=0..aSize-1) a[i] = i; dw: await(ready); for(i=0..aSize-1) assert(b[i] == i); } drivenby Test02 { for(i=0..aSize-1) a[i] = aSize-1-i; dw: await(ready); for(i=0..aSize-1) assert(b[i] == i); } drivenby Test03 { for(i=0..aSize-1) a[i] = ((i%2==0)?i:((aSize%2==0)?aSize-i:aSize-1-i)); dw: await(ready); for(i=0..aSize-1) assert(b[i] == i); }