| 18 | } |
| 19 | |
| 20 | void sort(words::Words& words, size_t start, size_t end) |
| 21 | { |
| 22 | // start index must be less than end index for 2 or more elements |
| 23 | if (!(start < end)) |
| 24 | return; |
| 25 | |
| 26 | // Choose middle address to partition set |
| 27 | swap(words, start, (start + end) / 2); // Swap middle address with start |
| 28 | |
| 29 | // Check words against chosen word |
| 30 | size_t current {start}; |
| 31 | for (size_t i {start + 1}; i <= end; i++) |
| 32 | { |
| 33 | if (*words[i] < *words[start]) // Is word less than chosen word? |
| 34 | swap(words, ++current, i); // Yes, so swap to the left |
| 35 | } |
| 36 | |
| 37 | swap(words, start, current); // Swap chosen and last swapped words |
| 38 | |
| 39 | if (current > start) sort(words, start, current - 1); // Sort left subset if exists |
| 40 | if (end > current + 1) sort(words, current + 1, end); // Sort right subset if exists |
| 41 | } |