// ************************************************************************** // // // // 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 // // // // ************************************************************************** // // CombSort improves BubbleSort in a similar way as ShellSort improves // // InsertionSort: To avoid turtles in BubbleSort (i.e. small values on the // // right of the list), CombSort makes use of gap sequence. This way, turtles // // move faster during the first phases where the gaps are large. The final // // phase is made with gap=1 and therefore is BubbleSort which is enough to // // assure correctness. // // ************************************************************************** // macro aSize = 16; macro iSize = 64; macro hSize = 4; module CombSort([aSize]nat{iSize} ?a,b, event !ready) { nat{aSize+1} i; bool swapped; [hSize]nat{iSize} steps; nat{hSize} s; s = hSize-1; steps[0] = 1; steps[1] = 2; steps[2] = 3; steps[3] = 6; for(i=0..aSize-1) b[i] = a[i]; i = 0; do { // perform BubbleSort using gap step[s] next(swapped) = false; w0: pause; do { if(b[i+steps[s]] < b[i]) { next(b[i]) = b[i+steps[s]]; next(b[i+steps[s]]) = b[i]; next(swapped) = true; } next(i) = i+1; w1: pause; } while(i+steps[s]<aSize-1); if(b[i+steps[s]] < b[i]) { next(b[i]) = b[i+steps[s]]; next(b[i+steps[s]]) = b[i]; next(swapped) = true; } if(s>0) next(s) = s-1; next(i) = 0; w2: pause; } while(swapped | s!=0); 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); }