Lab 4.1 — Tagsort
The sorting techniques you’ve learned until now manipulate thearray of data — swapping, sliding, and in general, moving theelements around until they are in sorted order. This can beundesirable for two reasons:
- There are times we wish to preserve the original order of theelements, and this is lost as a result of the sort.
- If the elements are large, the data movement resulting from thesort can be time-consuming, and/or require additional space.
Tagsort is a sorting technique that avoids these two problems.The basic idea is to maintain a secondary array (sometimes calledan index or tag array) containing some sort of
OR
OR