| 1721 | |
| 1722 | |
| 1723 | void Sort::quick(SLONG size, SORTP** pointers, ULONG length) |
| 1724 | { |
| 1725 | /************************************** |
| 1726 | * |
| 1727 | * Sort an array of record pointers. The routine assumes the following: |
| 1728 | * |
| 1729 | * a. Each element in the array points to the key of a record. |
| 1730 | * |
| 1731 | * b. Keys can be compared by auto-incrementing unsigned longword |
| 1732 | * compares. |
| 1733 | * |
| 1734 | * c. Relative array positions "-1" and "size" point to guard records |
| 1735 | * containing the least and the greatest possible sort keys. |
| 1736 | * |
| 1737 | * *************************************************************** |
| 1738 | * * Boy, did the assumption below turn out to be pretty stupid! * |
| 1739 | * *************************************************************** |
| 1740 | * |
| 1741 | * Note: For the time being, the key length field is ignored on the |
| 1742 | * assumption that something will eventually stop the comparison. |
| 1743 | * |
| 1744 | * WARNING: THIS ROUTINE DOES NOT MAKE A FINAL PASS TO UNSCRAMBLE |
| 1745 | * PARTITIONS OF SIZE TWO. THE POINTER ARRAY REQUIRES ADDITIONAL |
| 1746 | * PROCESSING BEFORE IT MAY BE USED! |
| 1747 | * |
| 1748 | **************************************/ |
| 1749 | SORTP** stack_lower[50]; |
| 1750 | SORTP*** sl = stack_lower; |
| 1751 | |
| 1752 | SORTP** stack_upper[50]; |
| 1753 | SORTP*** su = stack_upper; |
| 1754 | |
| 1755 | *sl++ = pointers; |
| 1756 | *su++ = pointers + size - 1; |
| 1757 | |
| 1758 | while (sl > stack_lower) |
| 1759 | { |
| 1760 | |
| 1761 | // Pick up the next interval off the respective stacks |
| 1762 | |
| 1763 | SORTP** r = *--sl; |
| 1764 | SORTP** j = *--su; |
| 1765 | |
| 1766 | // Compute the interval. If two or less, defer the sort to a final pass. |
| 1767 | |
| 1768 | const SLONG interval = j - r; |
| 1769 | if (interval < 2) |
| 1770 | continue; |
| 1771 | |
| 1772 | // Go guard against pre-ordered data, swap the first record with the |
| 1773 | // middle record. This isn't perfect, but it is cheap. |
| 1774 | |
| 1775 | SORTP** i = r + interval / 2; |
| 1776 | swap(i, r); |
| 1777 | |
| 1778 | // Prepare to do the partition. Pick up the first longword of the |
| 1779 | // key to speed up comparisons. |
| 1780 | |