Listing 1
#include "stdafx.h" #include "stdlib.h" #include "time.h" #include "math.h" int main(int argc, char* argv[]) { // Variable declarations const int ListLength = 100; int a[ListLength], b[ListLength], c[ListLength]; int x, y, HighestSeen, LowestSeen, EntryValue, EntryStep; int HighestBelow, HighestBelowPos, CurrentPosition, Buffer1; int Buffer2, HighestEntry, LowestEntry; bool IsLower, IsHigher, IsNotGreater; // The list would be read or otherwise accessed at this point // Sort list HighestEntry = 0; LowestEntry = ListLength + 1; HighestSeen = 0; LowestSeen = 0; for (x=0; x < ListLength; x++) { EntryValue = a[x]; IsLower = false; IsHigher = false; // Is it the lowest value so far? if (EntryValue < LowestEntry) { IsLower = true; b[x] = LowestSeen; LowestEntry = EntryValue; LowestSeen = x; } // Is it the highest value so far? if (EntryValue >= HighestEntry) { IsHigher = true; b[HighestSeen] = x; b[x] = 0; HighestEntry = EntryValue; HighestSeen = x; } // If not lowest or highest, find the next-lowest value if (!IsLower && !IsHigher) { // Jump through list to find any lower value EntryStep = 1 + (int)sqrt(x); HighestBelow = 0; for (y=0; y < x; y += EntryStep) { if (a[y] > HighestBelow && a[y] < EntryValue) { HighestBelow = a[y]; HighestBelowPos = y; } } // If lower value not found, use lowest value if (HighestBelow == 0) { HighestBelow = LowestEntry; HighestBelowPos = LowestSeen; } // Loop through list to find highest lower value IsNotGreater = true; CurrentPosition = HighestBelowPos; while(IsNotGreater) { Buffer1 = CurrentPosition; CurrentPosition = b[CurrentPosition]; if (a[CurrentPosition] > EntryValue) { IsNotGreater = false; Buffer2 = CurrentPosition; } } // Change list b[Buffer1] = x; b[x] = Buffer2; } } // Carry out sorting CurrentPosition = LowestSeen; for (x=0; x < ListLength; x++) { c[x] = a[CurrentPosition]; CurrentPosition = b[CurrentPosition]; } return 0; }