A Variation of Quicksort for Model Checking with Promela and SPIN

摘要

Because of the speed and memory efficiency of sorting, quicksort is often the best choice in software development. However, in model checking with SPIN, it is difficult to implement quicksort using Promela. Regular recursion-based implementations are not suitable for Promela due to the lack of function definition. Even Promela does not have stack in its data structures, increasing the difficulty to do quicksort. This paper proposes a variation of quicksort for Promela without using recursion and stack. The variation of quicksort can be applied to SPIN-based model checking requiring a quicksort algorithm. Other computer programs can also use this variation, if recursion, function definition and stack are not available or banned.