//Sort.ci Functions for sorting arrays -- See Q3750 GLOBAL STRING gsSortArray[479]; //Contains strings to sort for InsertionSort, ShellSort, //ShellSortI, QuickSort, HeapSort, MergeSort, MergeSort2 GLOBAL STRING gsSortArray2[479]; //Contains 2nd list of strings to sort for MergeSort2 GLOBAL INT giSortArray[15359]; //Contains numbers to sort for CountingSort GLOBAL INT giSortOutput[15359]; //Contains the sorted numbers for CountingSort GLOBAL INT gnIndex[479]; //Index created by ShellSortIdx STRING msMergeTemp[479]; //Temporary storage for MergeSort and MergeSort2 STRING msMergeTemp2[479]; //Temporary storage for MergeSort2 INT miCount[15359]; //Temporary storage for CountingSort INT miQuickSortStack[16]; //Temporary storage for QuickSort STRING msSortArray1[479]; //Contains strings to sort for ShellSortEx STRING msSortArray2[479]; //Contains strings to sort for ShellSortEx STRING msSortArray3[479]; //Contains strings to sort for ShellSortEx STRING msSortArray4[479]; //Contains strings to sort for ShellSortEx STRING msSortArray5[479]; //Contains strings to sort for ShellSortEx STRING msSortArray6[479]; //Contains strings to sort for ShellSortEx STRING msSortArray7[479]; //Contains strings to sort for ShellSortEx STRING msSortArray8[479]; //Contains strings to sort for ShellSortEx STRING msSortArray9[479]; //Contains strings to sort for ShellSortEx STRING msSortArray10[479]; //Contains strings to sort for ShellSortEx STRING msSortArray11[479]; //Contains strings to sort for ShellSortEx STRING msSortArray12[479]; //Contains strings to sort for ShellSortEx STRING msSortArray13[479]; //Contains strings to sort for ShellSortEx STRING msSortArray14[479]; //Contains strings to sort for ShellSortEx STRING msSortArray15[479]; //Contains strings to sort for ShellSortEx STRING msSortArray16[479]; //Contains strings to sort for ShellSortEx STRING msSortArray17[479]; //Contains strings to sort for ShellSortEx STRING msSortArray18[479]; //Contains strings to sort for ShellSortEx STRING msSortArray19[479]; //Contains strings to sort for ShellSortEx STRING msSortArray20[479]; //Contains strings to sort for ShellSortEx INT mhCompareString = -1; //Handle for CompareString DLL function //Sorts gsSortArray from iFirst to iLast elements using bubble sort algorithm //Note: Stable, extremely slow FUNCTION BubbleSort(INT iFirst = 0, INT iLast = 478) INT i; INT j; STRING sTemp; FOR i = iFirst TO iLast DO FOR j = 0 TO iLast - 1 DO IF (gsSortArray[j] > gsSortArray[j + 1]) THEN sTemp = gsSortArray[j]; gsSortArray[j] = gsSortArray[j + 1]; gsSortArray[j + 1] = sTemp; END END END END //Sorts gsSortArray from iFirst to iLast elements using insertion sort algorithm //Note: Stable, best for short lists FUNCTION InsertionSort(INT iFirst = 0, INT iLast = 478) INT i, j, bExitLoop = FALSE; STRING sTemp; FOR i = iFirst + 1 TO iLast DO sTemp = gsSortArray[i]; j = i - 1; WHILE ((j >= 0) AND (bExitLoop = False)) DO IF (sTemp < gsSortArray[j]) THEN gsSortArray[j + 1] = gsSortArray[j]; j = j - 1; ELSE bExitLoop = True; END END gsSortArray[j + 1] = sTemp; bExitLoop = False; END END //Sorts gsSortArray from iFirst to iLast elements using shell sort algorithm //Note: Unstable, good for short or longer lists FUNCTION ShellSort(INT iFirst = 0, INT iLast = 478) INT i; INT iGapSize; INT iCurPos; INT bExit; INT nElements = iLast - iFirst + 1; STRING sTemp; WHILE (iGapSize <= nElements) DO iGapSize = iGapSize * 3 + 1; END WHILE (iGapSize > 1) DO iGapSize = iGapSize / 3; FOR i = (iGapSize + iFirst) TO iLast DO iCurPos = i; sTemp = gsSortArray[i]; bExit = FALSE; WHILE (bExit = FALSE) DO IF (gsSortArray[iCurPos - iGapSize] > sTemp) THEN gsSortArray[iCurPos] = gsSortArray[iCurPos - iGapSize]; iCurPos = iCurPos - iGapSize; IF ((iCurPos - iGapSize) < iFirst) THEN bExit = TRUE; END ELSE bExit = TRUE; END END gsSortArray[iCurPos] = sTemp; END END END //Sorts gsSortArray from iFirst to iLast elements using quick sort algorithm //Note: Unstable, extremely fast for any size list, uses additional array and supporting function FUNCTION QuickSort(INT iFirst = 0, INT iLast = 478) INT i; INT s = 0; miQuickSortStack[s] = iFirst; s = s + 1; miQuickSortStack[s] = iLast; s = s + 1; WHILE (s > 0) DO s = s - 1; iLast = miQuickSortStack[s]; s = s - 1; iFirst = miQuickSortStack[s]; IF (iFirst < iLast) THEN i = Partition(iFirst, iLast); IF (i - iFirst > iLast - i) THEN miQuickSortStack[s] = iFirst; s = s + 1; miQuickSortStack[s] = i - 1; s = s + 1; miQuickSortStack[s] = i + 1; s = s + 1; miQuickSortStack[s] = iLast; s = s + 1; ELSE miQuickSortStack[s] = i + 1; s = s + 1; miQuickSortStack[s] = iLast; s = s + 1; miQuickSortStack[s] = iFirst; s = s + 1; miQuickSortStack[s] = i - 1; s = s + 1; END END END END // Supporting function for QuickSort() PRIVATE INT FUNCTION Partition(INT iFirst, INT iLast) STRING sTemp; STRING sPivot; INT iUp; INT iDown; sPivot = gsSortArray[iFirst]; iUp = iFirst; iDown = iLast; WHILE (iUp < iDown) DO WHILE ((gsSortArray[iUp] <= sPivot) AND (iUp < iLast)) DO iUp = iUp + 1; END WHILE (gsSortArray[iDown] > sPivot) DO iDown = iDown - 1; END IF (iUp < iDown) THEN sTemp = gsSortArray[iUp]; gsSortArray[iUp] = gsSortArray[iDown]; gsSortArray[iDown] = sTemp; END END sTemp = gsSortArray[iFirst]; gsSortArray[iFirst] = gsSortArray[iDown]; gsSortArray[iDown] = sTemp; RETURN iDown; END //Sorts gsSortArray from iFirst to iLast elements using heap sort algorithm //Note: Unstable, good for very long lists. Uses additional array and supporting function FUNCTION HeapSort(INT iFirst = 0, INT iLast = 478) INT nElement = (iLast + iFirst) / 2; STRING sTemp; WHILE (nElement >= iFirst) DO Heapify(nElement, iFirst, iLast); nElement = nElement - 1; END nElement = iLast; WHILE (nElement >= iFirst + 1) DO sTemp = gsSortArray[iFirst]; gsSortArray[iFirst] = gsSortArray[nElement]; gsSortArray[nElement] = sTemp; Heapify(iFirst, iFirst, nElement - 1); nElement = nElement - 1; END END // Supporting function for HeapSort() PRIVATE FUNCTION Heapify(INT nNode, INT iFirst, INT iLast) INT nLeaf; STRING sTemp; WHILE (TRUE) DO nLeaf = nNode + nNode - (iFirst - 1); IF (nLeaf > iLast) THEN RETURN; END IF (nLeaf < iLast) THEN IF (gsSortArray[nLeaf] < gsSortArray[nLeaf + 1]) THEN nLeaf = nLeaf + 1; END END IF (gsSortArray[nLeaf] < gsSortArray[nNode]) THEN RETURN; END sTemp = gsSortArray[nNode]; gsSortArray[nNode] = gsSortArray[nLeaf]; gsSortArray[nLeaf] = sTemp; nNode = nLeaf; END END //Sorts gsSortArray from iFirst to iLast elements using merge sort algorithm //Note: Stable, nearly as fast as quick sort FUNCTION MergeSort(INT iFirst = 0, INT iLast = 478) INT i; INT m = 1; INT n = iLast - iFirst + 1; WHILE m <= n DO i = iFirst; WHILE i < n - m DO Merge(i, i + m - 1, Min(i + 2 * m - 1, n - 1)); i = i + 2 * m; END m = m * 2; END END // Supporting function for MergeSort() PRIVATE FUNCTION Merge(INT iFirst, INT iMiddle, INT iLast) INT i; INT j; INT k; FOR i = iFirst TO iMiddle DO msMergeTemp[i] = gsSortArray[i]; END FOR j = iMiddle + 1 TO iLast DO msMergeTemp[iMiddle + 1 + iLast - j] = gsSortArray[j]; END i = iFirst; k = iFirst; j = iLast; WHILE k <= iLast DO IF msMergeTemp[j] < msMergeTemp[i] THEN gsSortArray[k] = msMergeTemp[j]; j = j - 1; ELSE gsSortArray[k] = msMergeTemp[i]; i = i + 1; END k = k + 1; END END //Sorts giSortArray from iFirst to iLast elements using counting sort algorithm //and writes output to giSortOutput. Min and max values in array are calculated if not specified // //Note: Unstable, fastest algorithm for sorting integers, uses extra arrays and supporting function // Max value - min value must be under 15358 or an error is returned INT FUNCTION CountingSort(INT iFirst = 0, INT iLast = 15358, INT nMin = 0, INT nMax = 0) INT cErrArrayOverrun = 259; INT iIndex; INT iOutputIndex; IF (nMin = nMax) THEN nMin = giSortArray[iFirst]; nMax = giSortArray[iFirst]; FOR iIndex = iFirst + 1 TO iLast DO IF (giSortArray[iIndex] < nMin) THEN nMin = giSortArray[iIndex]; ELSE IF (giSortArray[iIndex] > nMax) THEN nMax = giSortArray[iIndex]; END END END END IF ((nMax - nMin) >= 15359) THEN RETURN cErrArrayOverrun; END FOR iIndex = nMin TO nMax DO miCount[iIndex - nMin] = 0; END FOR iIndex = iFirst TO iLast DO miCount[giSortArray[iIndex] - nMin] = miCount[giSortArray[iIndex] - nMin] + 1; END FOR iIndex = nMin + 1 TO nMax DO miCount[iIndex - nMin] = miCount[iIndex - nMin] + miCount[iIndex - 1 - nMin]; END iIndex = iLast; WHILE (iIndex >= iFirst) DO iOutputIndex = miCount[giSortArray[iIndex] - nMin] - 1; giSortOutput[iOutputIndex] = giSortArray[iIndex]; miCount[giSortArray[iIndex] - nMin] = miCount[giSortArray[iIndex] - nMin] - 1; iIndex = iIndex - 1; END RETURN 0; END //Sorts gsSortArray or gsSortArray2 from iFirst to iLast elements using shell sort algorithm //Specify array number to sort (1=gsSortArray, 2=gsSortArray2) and the other array is kept in sync // //Note: Stable, good for short or longer lists FUNCTION MergeSort2(INT iFirst, INT iLast, INT nArray = 1) INT i; INT m = 1; INT n = iLast - iFirst + 1; WHILE m <= n DO i = iFirst; WHILE i < n - m DO Merge2(i, i + m - 1, Min(i+2*m-1,n-1), nArray); i = i + 2 * m; END m = m * 2; END END // Supporting function for MergeSort2() PRIVATE FUNCTION Merge2(INT iFirst, INT iMiddle, INT iLast, INT nArray = 1) INT i, j, k; FOR i = iFirst TO iMiddle DO msMergeTemp[i] = gsSortArray[i]; msMergeTemp2[i] = gsSortArray2[i]; END FOR j = iMiddle + 1 TO iLast DO msMergeTemp[iMiddle + 1 + iLast - j] = gsSortArray[j]; msMergeTemp2[iMiddle + 1 + iLast - j] = gsSortArray2[j]; END i = iFirst; k = iFirst; j = iLast; WHILE k <= iLast DO IF ((nArray = 1) AND (msMergeTemp[j] < msMergeTemp[i])) OR ((nArray = 2) AND (msMergeTemp2[j] < msMergeTemp2[i])) THEN gsSortArray[k] = msMergeTemp[j]; gsSortArray2[k] = msMergeTemp2[j]; j = j - 1; ELSE gsSortArray[k] = msMergeTemp[i]; gsSortArray2[k] = msMergeTemp2[i]; i = i + 1; END k = k + 1; END END //Sorts gsSortArray from iFirst to iLast elements using shell sort algorithm //and uses Windows locale settings for non-English characters // //Note: Unstable, good for short or longer lists, slower because of StrCompare function FUNCTION ShellSortI(INT iFirst = 0, INT iLast = 478) INT i; INT iGapSize; INT iCurPos; INT nElements; INT bExit; STRING sTemp; nElements = iLast - iFirst + 1; WHILE (iGapSize <= nElements) DO iGapSize = iGapSize * 3 + 1; END WHILE (iGapSize > 1) DO iGapSize = iGapSize / 3; FOR i = (iGapSize + iFirst) TO iLast DO iCurPos = i; sTemp = gsSortArray[i]; bExit = FALSE; WHILE (bExit = FALSE) DO IF (StrCompare(gsSortArray[iCurPos - iGapSize], sTemp) = 3) THEN gsSortArray[iCurPos] = gsSortArray[iCurPos - iGapSize]; iCurPos = iCurPos - iGapSize; IF ((iCurPos - iGapSize) < iFirst) THEN bExit = TRUE; END ELSE bExit = TRUE; END END gsSortArray[iCurPos] = sTemp; END END END //Compare two sString1 and sString2 using Windows Locale settings // //iMode Sort mode // 0x1 Ignore case (default) // 0x10000 Corresponding Hiragana and Katakana characters compare as equal // 0x2 Ignore nonspacing characters // 0x4 Ignore symbols // 0x1000 Treat punctuation the same as symbols // // Returns 0 compare failed // 1 string1 < string2 // 2 string1 = string2 // 3 string1 > string2 // // NOTE: Requires Citect 6.10 or higher for DllCallEx support INT FUNCTION StrCompare(STRING sString1, STRING sString2, INT iMode = 0) INT cLocaleSystemDefault = 0x400, cNullTerminated = -1; IF (mhCompareString = -1) THEN mhCompareString = DLLOpen("kernel32", "CompareStringA", "JJJCJCJ"); END RETURN DLLCallEx(mhCompareString, cLocaleSystemDefault, iMode, sString1, cNullTerminated, sString2, cNullTerminated); END //The following Version of StrCompare will work in older versions of Citect. To use it, remove the //comment marks from each line below and delete the above version of StrCompare //PRIVATE //INT //FUNCTION StrCompare(STRING sString1, STRING sString2) // INT iResult, iLength1, iLength2, cMaxLength = 118, cStringEqualTo = 2; // // iLength1 = StrLength(sString1); // iLength2 = StrLength(sString2); // // IF (mhCompareString = -1) THEN // mhCompareString = DLLOpen("kernel32", "CompareStringA", "JJJCJCJ"); // END // // iResult = DLLCall(mhCompareString, "1024,0,^"" + StrLeft(sString1, cMaxLength) + "^",-1,^"" + StrLeft(sString2, cMaxLength) + "^",-1"); // // IF ((iResult = cStringEqualTo) AND (iLength1 > cMaxLength) AND (iLength2 > cMaxLength)) THEN // sString1 = StrMid(sString1, cMaxLength, iLength1 - cMaxLength); // sString2 = StrMid(sString2, cMaxLength, iLength2 - cMaxLength); // iResult = DLLCall(mhCompareString, "1024,0,^"" + sString1 + "^",-1,^"" + sString2 + "^",-1"); // END // // RETURN iResult; //END //Sorts gsSortArray from iFirst to iLast elements using shell sort algorithm //new element order is written to gnIndex and gsSortArray is not modified // //Note: Unstable, good for short or longer lists FUNCTION ShellSortIdx(INT nFirst = 0, INT nLast = 478) INT i, iGapSize, iCurPos, bExit, nElements = nLast - nFirst + 1; INT nTemp; FOR i = nFirst TO nLast DO gnIndex[i] = i; END WHILE (iGapSize <= nElements) DO iGapSize = iGapSize * 3 + 1; END WHILE (iGapSize > 1) DO iGapSize = iGapSize / 3; FOR i = (iGapSize + nFirst) TO nLast DO iCurPos = i; nTemp = gnIndex[i]; bExit = FALSE; WHILE (bExit = FALSE) DO IF (gsSortArray[gnIndex[iCurPos - iGapSize]] > gsSortArray[nTemp]) THEN gnIndex[iCurPos] = gnIndex[iCurPos - iGapSize]; iCurPos = iCurPos - iGapSize; IF ((iCurPos - iGapSize) < nFirst) THEN bExit = TRUE; END ELSE bExit = TRUE; END END gnIndex[iCurPos] = nTemp; END END END //Sorts multiple arrays with up to 10059 elements in total using shell sort algorithm //Uses Windows locale settings for non-English characters if bInternational = TRUE // //Note: Unstable, good for extremely long lists, slower because of multiple arrays and // international support. Use SortItemGet and SortItemSet to read and write elements // //Returns TRUE if successful or FALSE if the iFirst or iLast parameter is out of range. // //To increase the number of possible elements, add more arrays after msSortArray20. Modify //SortItemGet() and SortItemSet() to use the additional arrays, and set the cMaxElement //constant in this function to: (479 * Number of arrays) - 1 INT FUNCTION ShellSortEx(INT iFirst = 0, INT iLast = 10058, INT bInternational = FALSE) INT cCmpGreaterThan = 3; INT cMaxElement = 10058; INT i; INT iGapSize; INT iCurPos INT nElements; INT bExit; INT bIsGreater; STRING sTemp; IF (iFirst < 0) OR (iFirst > cMaxElement - 1) OR (iLast <= iFirst) OR (iLast > cMaxElement) THEN RETURN FALSE; END nElements = iLast - iFirst + 1; WHILE iGapSize <= nElements DO iGapSize = iGapSize * 3 + 1; END WHILE iGapSize > 1 DO iGapSize = iGapSize / 3; FOR i = (iGapSize + iFirst) TO iLast DO iCurPos = i; sTemp = SortItemGet(i); bExit = FALSE; WHILE bExit = FALSE DO IF bInternational = TRUE THEN bIsGreater = (StrCompare(SortItemGet(iCurPos - iGapSize), sTemp) = cCmpGreaterThan); ELSE bIsGreater = (SortItemGet(iCurPos - iGapSize) > sTemp); END IF bIsGreater THEN SortItemSet(iCurPos, SortItemGet(iCurPos - iGapSize)); iCurPos = iCurPos - iGapSize; IF (iCurPos - iGapSize) < iFirst THEN bExit = TRUE; END ELSE bExit = TRUE; END END SortItemSet(iCurPos, sTemp); END END RETURN TRUE; END //Returns the value of the specified element number (0 to 10058) or "" if out of range //Used with ShellSortEx STRING FUNCTION SortItemGet(INT iElement) INT cElementsPerArray = 479; INT iArray; INT iArrayElement; iArrayElement = iElement MOD cElementsPerArray; iArray = (iElement - iArrayElement) / cElementsPerArray; SELECT CASE iArray CASE 0 RETURN gsSortArray[iArrayElement]; CASE 1 RETURN msSortArray1[iArrayElement]; CASE 2 RETURN msSortArray2[iArrayElement]; CASE 3 RETURN msSortArray3[iArrayElement]; CASE 4 RETURN msSortArray4[iArrayElement]; CASE 5 RETURN msSortArray5[iArrayElement]; CASE 6 RETURN msSortArray6[iArrayElement]; CASE 7 RETURN msSortArray7[iArrayElement]; CASE 8 RETURN msSortArray8[iArrayElement]; CASE 9 RETURN msSortArray9[iArrayElement]; CASE 10 RETURN msSortArray10[iArrayElement]; CASE 11 RETURN msSortArray11[iArrayElement]; CASE 12 RETURN msSortArray12[iArrayElement]; CASE 13 RETURN msSortArray13[iArrayElement]; CASE 14 RETURN msSortArray14[iArrayElement]; CASE 15 RETURN msSortArray15[iArrayElement]; CASE 16 RETURN msSortArray16[iArrayElement]; CASE 17 RETURN msSortArray17[iArrayElement]; CASE 18 RETURN msSortArray18[iArrayElement]; CASE 19 RETURN msSortArray19[iArrayElement]; CASE 20 RETURN msSortArray20[iArrayElement]; CASE ELSE // Invalid element number RETURN ""; END SELECT END //Writes sValue to the specified element number (0 to 10058) //Returns 0 if successful, or 257 if element number is out of range //Used with ShellSortEx INT FUNCTION SortItemSet(INT iElement, STRING sValue) INT cElementsPerArray = 479; INT cErrOutOfRange = 257; INT iArray; INT iArrayElement; iArrayElement = iElement MOD cElementsPerArray; iArray = (iElement - iArrayElement) / cElementsPerArray; SELECT CASE iArray CASE 0 gsSortArray[iArrayElement] = sValue; CASE 1 msSortArray1[iArrayElement] = sValue; CASE 2 msSortArray2[iArrayElement] = sValue; CASE 3 msSortArray3[iArrayElement] = sValue; CASE 4 msSortArray4[iArrayElement] = sValue; CASE 5 msSortArray5[iArrayElement] = sValue; CASE 6 msSortArray6[iArrayElement] = sValue; CASE 7 msSortArray7[iArrayElement] = sValue; CASE 8 msSortArray8[iArrayElement] = sValue; CASE 9 msSortArray9[iArrayElement] = sValue; CASE 10 msSortArray10[iArrayElement] = sValue; CASE 11 msSortArray11[iArrayElement] = sValue; CASE 12 msSortArray12[iArrayElement] = sValue; CASE 13 msSortArray13[iArrayElement] = sValue; CASE 14 msSortArray14[iArrayElement] = sValue; CASE 15 msSortArray15[iArrayElement] = sValue; CASE 16 msSortArray16[iArrayElement] = sValue; CASE 17 msSortArray17[iArrayElement] = sValue; CASE 18 msSortArray18[iArrayElement] = sValue; CASE 19 msSortArray19[iArrayElement] = sValue; CASE 20 msSortArray20[iArrayElement] = sValue; CASE ELSE // Invalid element number RETURN cErrOutOfRange; END SELECT RETURN 0; END