- #1

basePARTICLE

- 86

- 0

(1) When sorting large strings and many of them it is better to use a sort-lens. A sort-lens is an integer array indexing the source data.

string data [n]

int sort_lens[n]

The data is referenced by: data[sort_lens[COUNTER]] ;

(2) When you implement your quick sort, and the number of elements left to sort are five or less, which makes the number manageable, you can use a prefab-sort. Here is the solution for three elements. Given three elements {c,b,a} such that sorted means [a,b,c], here is the static transformation. The state A, gives an unsorted sequence and the solution B, gives the exchange sequence to take A to sorted-A.

state [a,b,c] solution [1,2,3]

state [a,c,b] solution [1,3,2]

state [b,a,c] solution [2,1,3]

state [b,c,a] solution [2,3,1]

state [c,a,b] solution [3,1,2]

state [c,b,a] solution [3,2,1]

For elements less than 50, according to Knuth, in line sorts are faster. So this technique is based on both the quick sort and the in-line sort. I have implemented up to a four element in-line sort, for both integers and strings. I will add the five element in-line sort as soon as I get the time.

So here is a great addition for your qs() objects (your quick sort object).