-- card: 5428 from stack: in -- bmap block id: 5908 -- flags: 4000 -- background id: 2685 -- name: Sort ----- HyperTalk script ----- on openCard if (debugging() = true) then pass openCard set cursor to watch set the scroll of card field "Input" to 0 set the scroll of card field "Output" to 0 -- create groups of radio buttons get newRadio("sortBy", "card", "Items,Spaces,Lines") if (it = empty) then get newRadio("sortInput", "card", "Random,Presort") if (it = empty) then get newRadio("sortRules", "card", "Exact,Ignorecase,International,Numeric") if (it ≠ empty) then answer("openCard: " & errorstring(it)) pass openCard end openCard on closeCard if (debugging() = true) then pass closeCard get disposeRadio("sortBy") get disposeRadio("sortRules") get disposeRadio("sortInput") pass closeCard end closeCard -- Handler called to demonstrate a sorting method on doSort method -- method is quicksort, shellsort, or treesort set cursor to watch put cd fld "input" into data -- get separator to sort on if (hilite of button "Lines" = true) then put return into separator put the number of lines of data into size put "Input: (lines=" & size & ")" into cd fld "InputTitle" else if (hilite of button "Spaces" = true) then put space into separator put the number of words of data into size put "Input: (words=" & size & ")" into cd fld "InputTitle" else if (hilite of button "Items" = true) then put "," into separator put the number of items of data into size put "Input: (items=" & size & ")" into cd fld "InputTitle" end if put hilite of button "Presort" into presort -- make sure size isn't so big we'll spend a year waiting for sort if (method = "treesort" and presort and size > 256) then answer "Sort may take a very very long time." with "Continue" or "Cancel" if (it = "Cancel") then exit doSort end if -- get method for comparing items put the short name of selectedRadio("sortRules") into compare -- presort data if necessary if (hilite of button "Presort" = true) then put listSort(data, compare, separator, false) into data end if -- sort using appropriate method put the ticks into start if (method = "shellsort" or method = "quicksort") then get listSort(data, compare, separator, false, method) else if (method = "treesort") then get treeSort(data, compare, separator, false) else -- error end if put the ticks - start into start put it into card field "Output" put "Sort took " & start / 60.0 & " seconds." end doSort -- part 16 (field) -- low flags: 00 -- high flags: 0007 -- rect: left=260 top=174 right=234 bottom=509 -- title width / last selected line: 0 -- icon id / first selected line: 0 / 0 -- text alignment: 0 -- font id: 3 -- text size: 9 -- style flags: 0 -- line height: 12 -- part name: Input -- part 17 (field) -- low flags: 01 -- high flags: 0007 -- rect: left=260 top=253 right=315 bottom=509 -- title width / last selected line: 0 -- icon id / first selected line: 0 / 0 -- text alignment: 0 -- font id: 3 -- text size: 9 -- style flags: 0 -- line height: 12 -- part name: Output -- part 18 (field) -- low flags: 01 -- high flags: 0000 -- rect: left=262 top=57 right=72 bottom=318 -- title width / last selected line: 0 -- icon id / first selected line: 0 / 0 -- text alignment: 0 -- font id: 3 -- text size: 10 -- style flags: 256 -- line height: 13 -- part name: -- part 19 (field) -- low flags: 01 -- high flags: 0000 -- rect: left=262 top=76 right=91 bottom=318 -- title width / last selected line: 0 -- icon id / first selected line: 0 / 0 -- text alignment: 0 -- font id: 3 -- text size: 10 -- style flags: 256 -- line height: 13 -- part name: -- part 22 (field) -- low flags: 01 -- high flags: 0002 -- rect: left=260 top=238 right=254 bottom=509 -- title width / last selected line: 0 -- icon id / first selected line: 0 / 0 -- text alignment: 0 -- font id: 3 -- text size: 10 -- style flags: 256 -- line height: 13 -- part name: -- part 29 (button) -- low flags: 00 -- high flags: C006 -- rect: left=317 top=75 right=91 bottom=385 -- title width / last selected line: 0 -- icon id / first selected line: 0 / 0 -- text alignment: 1 -- font id: 3 -- text size: 10 -- style flags: 256 -- line height: 13 -- part name: Random ----- HyperTalk script ----- on mouseUp clickRadio sortInput, the name of the target end mouseUp -- part 30 (button) -- low flags: 00 -- high flags: 8006 -- rect: left=384 top=75 right=91 bottom=451 -- title width / last selected line: 0 -- icon id / first selected line: 0 / 0 -- text alignment: 1 -- font id: 3 -- text size: 10 -- style flags: 256 -- line height: 13 -- part name: Presort ----- HyperTalk script ----- on mouseUp clickRadio sortInput, the name of the target end mouseUp -- part 32 (button) -- low flags: 00 -- high flags: 8006 -- rect: left=450 top=56 right=72 bottom=505 -- title width / last selected line: 0 -- icon id / first selected line: 0 / 0 -- text alignment: 1 -- font id: 3 -- text size: 10 -- style flags: 256 -- line height: 13 -- part name: Lines ----- HyperTalk script ----- on mouseUp clickRadio sortBy, the name of the target end mouseUp -- part 33 (button) -- low flags: 00 -- high flags: C006 -- rect: left=317 top=56 right=72 bottom=385 -- title width / last selected line: 0 -- icon id / first selected line: 0 / 0 -- text alignment: 1 -- font id: 3 -- text size: 10 -- style flags: 256 -- line height: 13 -- part name: Items ----- HyperTalk script ----- on mouseUp clickRadio sortBy, the name of the target end mouseUp -- part 34 (button) -- low flags: 00 -- high flags: 8006 -- rect: left=384 top=56 right=72 bottom=451 -- title width / last selected line: 0 -- icon id / first selected line: 0 / 0 -- text alignment: 1 -- font id: 3 -- text size: 10 -- style flags: 256 -- line height: 13 -- part name: Spaces ----- HyperTalk script ----- on mouseUp clickRadio sortBy, the name of the target end mouseUp -- part 36 (button) -- low flags: 00 -- high flags: A003 -- rect: left=327 top=130 right=149 bottom=445 -- title width / last selected line: 0 -- icon id / first selected line: 0 / 0 -- text alignment: 1 -- font id: 3 -- text size: 10 -- style flags: 256 -- line height: 13 -- part name: Make Random Data ----- HyperTalk script ----- on mouseUp ask "How many random numbers?" with 512 if (it = empty) then exit mouseUp put it into count set cursor to watch repeat with i=1 to count put random(9999) & "," after list end repeat delete last char of list put list into card field "Input" clickRadio "sortRules", the name of card button "Numeric" end mouseUp -- part 37 (button) -- low flags: 00 -- high flags: A003 -- rect: left=262 top=25 right=47 bottom=339 -- title width / last selected line: 0 -- icon id / first selected line: 0 / 0 -- text alignment: 1 -- font id: 0 -- text size: 12 -- style flags: 0 -- line height: 16 -- part name: Quicksort ----- HyperTalk script ----- on mouseUp doSort quicksort end mouseUp -- part 38 (button) -- low flags: 00 -- high flags: A003 -- rect: left=344 top=25 right=47 bottom=416 -- title width / last selected line: 0 -- icon id / first selected line: 0 / 0 -- text alignment: 1 -- font id: 0 -- text size: 12 -- style flags: 0 -- line height: 16 -- part name: Shellsort ----- HyperTalk script ----- on mouseUp doSort shellsort end mouseUp -- part 42 (button) -- low flags: 00 -- high flags: C006 -- rect: left=317 top=94 right=110 bottom=385 -- title width / last selected line: 0 -- icon id / first selected line: 0 / 0 -- text alignment: 1 -- font id: 3 -- text size: 10 -- style flags: 256 -- line height: 13 -- part name: Exact ----- HyperTalk script ----- on mouseUp clickRadio sortRules, the name of the target end mouseUp -- part 43 (button) -- low flags: 00 -- high flags: 8006 -- rect: left=384 top=94 right=110 bottom=483 -- title width / last selected line: 0 -- icon id / first selected line: 0 / 0 -- text alignment: 1 -- font id: 3 -- text size: 10 -- style flags: 256 -- line height: 13 -- part name: Ignorecase ----- HyperTalk script ----- on mouseUp clickRadio sortRules, the name of the target end mouseUp -- part 44 (button) -- low flags: 00 -- high flags: 8006 -- rect: left=384 top=109 right=125 bottom=483 -- title width / last selected line: 0 -- icon id / first selected line: 0 / 0 -- text alignment: 1 -- font id: 3 -- text size: 10 -- style flags: 256 -- line height: 13 -- part name: International ----- HyperTalk script ----- on mouseUp clickRadio sortRules, the name of the target end mouseUp -- part 45 (button) -- low flags: 00 -- high flags: 8006 -- rect: left=317 top=109 right=125 bottom=385 -- title width / last selected line: 0 -- icon id / first selected line: 0 / 0 -- text alignment: 1 -- font id: 3 -- text size: 10 -- style flags: 256 -- line height: 13 -- part name: Numeric ----- HyperTalk script ----- on mouseUp clickRadio sortRules, the name of the target end mouseUp -- part 46 (button) -- low flags: 00 -- high flags: A003 -- rect: left=422 top=25 right=47 bottom=494 -- title width / last selected line: 0 -- icon id / first selected line: 0 / 0 -- text alignment: 1 -- font id: 0 -- text size: 12 -- style flags: 0 -- line height: 16 -- part name: Treesort ----- HyperTalk script ----- on mouseUp doSort treesort end mouseUp -- part 47 (field) -- low flags: 00 -- high flags: 0000 -- rect: left=262 top=95 right=110 bottom=318 -- title width / last selected line: 0 -- icon id / first selected line: 0 / 0 -- text alignment: 0 -- font id: 3 -- text size: 10 -- style flags: 256 -- line height: 13 -- part name: -- part 48 (field) -- low flags: 01 -- high flags: 0002 -- rect: left=260 top=159 right=175 bottom=509 -- title width / last selected line: 0 -- icon id / first selected line: 0 / 0 -- text alignment: 0 -- font id: 3 -- text size: 10 -- style flags: 256 -- line height: 13 -- part name: InputTitle -- part contents for background part 9 ----- text ----- DemoStack 0.9 -- part contents for background part 1 ----- text ----- Sort -- part contents for background part 12 ----- text ----- Card #6 -- part contents for card part 18 ----- text ----- Sort By: -- part contents for card part 19 ----- text ----- Input: -- part contents for card part 22 ----- text ----- Output: -- part contents for background part 14 ----- text ----- This card demonstrates the sorting functions of ArrayList and BinaryTree. ArrayList can sort using one of two algorithms: quick sort or shell sort. BinaryTree sorts by inserting the data and then traversing the tree in in-order. At the end of this description are results from some benchmarks comparing each method. For random data, you will notice that quick sort is always the best algorithm to use. Even though tree sort uses nearly the same amount of key comparisons as quick sort does, it is slower due to the time needed to traverse the tree after inserting the items and due to other overhead incurred while maintaing the tree. Shell sort is excellent for presorted data, while quick sort will be much slower than on random data. Finally, the current version of BinaryTree is horrendous when called with presorted data. Remember that ArrayList implements several enhancements to the basic quick sort algorithm, so that even if it is called on presorted data it will not degenerate to quadratic behavior. • Tip: To get the items in a list in reverse order use the top function of ArrayList. ________________________________ Trying it out The buttons "Quicksort" and "Shellsort" and "Treesort" execute a sort on the data in the "Input" field. The "Input" field contains the data to be sorted, while the "Output" field contains the sorted output. The time taken by each sort is displayed in the message box. Notice that this time includes the work done to insert the items into the list or tree; if you weren't just sorting the data, but preparing it for further processing, then you'd only have to insert the data into the list once. ___________________ Sorting by different things The set of radio buttons labeled "Sort By" is used to select the character that separates items. When "Lines" is selected items are separated by the return character; when "Spaces" is selected the space character separates items, and when "Items" is selected the comma character is used as the separator. Thus you can sort data by lines, words, or HyperCard items. • Note: The "Sort By" options specify the separator character used for the sort. In the case of a sort by spaces, words may not be sorted correctly, since some words will include return characters or tabs. __________________ Sorted vs. Unsorted Input The set of radio buttons labeled "Input" control the form of the input. If the "Random" button is selected then the input is sorted as is, without doing any preprocessing. If the "Presort" button is selected then the input is sorted once before the timed sort is run, and then the timed sort sorts this already sorted data. This is supposed to demonstrate that shell sort is better than quick sort if the data are already sorted. __________________ Different sorting methods The comparison buttons control the rules for comparing items. The exact option sorts items according to their precise ASCII ordering. Ignorecase sorts items so that letters are grouped properly in the sort. Numeric compares items as numbers. Finally, International will sort items so that letters with diacritics are in their correct positions (instead of sorting them by their ASCII values). An international sort results in slower execution. ____________ Input and Output The "Make Random Data" button replaces the input with randomly generated integers. _______________________________ Following are timing results from some tests (run on a standard Macintosh Plus). -- Quick sort, 512 random integers: Exact 2.8 seconds. Ignorecase 3.48 seconds. Numeric 4.53 International 19.43 -- Quick sort, 512 presorted integers: Exact 8.52 seconds. Ignorecase 14.1 seconds. Numeric 19.85 seconds. International148.65 seconds. -- Shell sort, 512 random integers: Exact 5.15 Ignorecase 6.33 International 34.87 seconds. -- Shell sort, 512 presorted integers: Exact 2.77 seconds. Ignorecase 3.87 seconds. International 15.7 seconds. -- part contents for background part 13 ----- text ----- Description -- part contents for card part 47 ----- text ----- Method: -- part contents for card part 48 ----- text ----- Input: (items=512) -- part contents for card part 17 ----- text ----- 34,73,73,96,124,134,144,167,202,205,223,227,285,296,298,329,342,348,378,402,416,418,443,466,476,496,516,517,556,572,573,578,592,616,642,643,647,647,653,653,666,677,681,699,726,730,752,753,753,758,762,833,844,860,861,867,878,905,908,914,928,937,962,985,1001,1007,1037,1065,1085,1097,1111,1116,1164,1205,1233,1236,1236,1260,1266,1339,1353,1355,1378,1391,1396,1396,1412,1416,1459,1497,1518,1524,1537,1551,1556,1559,1572,1597,1621,1634,1636,1638,1645,1676,1691,1697,1698,1724,1730,1733,1742,1746,1773,1786,1791,1815,1831,1841,1850,1869,1901,1901,1906,1927,1928,1935,1949,1968,1993,1993,2020,2026,2031,2044,2045,2071,2074,2086,2112,2151,2161,2164,2168,2183,2186,2206,2216,2222,2230,2234,2281,2296,2298,2302,2307,2314,2325,2343,2346,2376,2380,2433,2433,2451,2456,2491,2513,2517,2518,2542,2547,2547,2583,2599,2617,2646,2647,2654,2655,2659,2660,2666,2682,2698,2707,2744,2793,2832,2840,2905,2931,2940,2950,2965,2976,2976,2979,2980,2999,3041,3073,3086,3087,3093,3101,3173,3231,3251,3257,3333,3355,3373,3397,3417,3430,3456,3501,3543,3576,3601,3606,3607,3673,3676,3733,3770,3798,3801,3845,3921,3922,3939,3945,3956,3957,3992,4014,4072,4078,4097,4100,4121,4127,4191,4194,4195,4200,4216,4237,4241,4274,4287,4305,4305,4339,4356,4376,4385,4387,4423,4429,4462,4503,4542,4560,4609,4638,4651,4654,4657,4685,4696,4786,4787,4804,4807,4831,4831,4904,4944,4963,4982,5012,5036,5038,5055,5079,5084,5104,5167,5198,5202,5208,5215,5241,5287,5377,5396,5398,5401,5444,5446,5466,5473,5526,5527,5529,5547,5550,5583,5593,5598,5611,5725,5726,5798,5833,5847,5851,5862,5873,5884,5924,5974,5998,6002,6005,6024,6049,6063,6064,6076,6108,6117,6121,6124,6293,6332,6376,6378,6404,6419,6472,6485,6547,6584,6593,6594,6608,6614,6620,6633,6635,6644,6644,6648,6651,6654,6688,6729,6746,6767,6810,6876,6909,6912,6922,6939,7005,7011,7018,7024,7071,7072,7080,7091,7093,7101,7118,7129,7131,7166,7212,7234,7264,7313,7319,7325,7407,7440,7451,7484,7502,7514,7564,7574,7580,7582,7585,7601,7673,7682,7720,7734,7744,7765,7783,7806,7816,7853,7912,7912,7925,7936,7945,7969,7970,8000,8002,8011,8013,8042,8049,8066,8110,8162,8171,8175,8231,8233,8254,8292,8353,8375,8377,8422,8438,8440,8447,8449,8471,8479,8494,8532,8534,8535,8556,8570,8667,8680,8727,8733,8749,8751,8773,8787,8878,8882,8897,8928,8938,8949,8959,8966,9011,9012,9014,9018,9029,9029,9056,9072,9074,9092,9098,9106,9109,9182,9203,9214,9224,9234,9236,9247,9280,9366,9375,9418,9420,9543,9550,9577,9596,9620,9677,9677,9757,9778,9795,9798,9806,9814,9815,9858,9871,9936,9936,9941,9951,9973,9989,9995 -- part contents for card part 16 ----- text ----- 7484,2044,5012,9029,1645,9815,4097,2206,7816,1949,5862,9806,4696,2161,1236,8773,752,3845,3543,7072,7673,3801,1636,6654,3093,202,5444,1537,9092,5466,2045,3676,2617,6644,2660,4654,329,2682,647,1236,296,7118,3957,9871,5398,5055,4305,4194,7925,2234,9989,2547,9543,1266,5215,2832,6002,2164,9951,8375,9973,2965,9677,9012,6594,9182,2071,7682,7969,2950,9936,2296,5598,6293,9280,8447,5079,7234,8002,2583,5167,861,908,3601,2020,2376,9018,4831,7564,4376,6729,6124,6614,4542,1037,1698,285,7093,1416,753,1518,9798,6633,134,8897,6049,7970,1233,4685,205,8727,124,1497,8556,73,6024,8751,2659,3945,1869,476,7601,2302,1730,4904,1001,962,9418,5529,6912,8787,1412,937,2980,1085,6939,6767,4100,4339,1116,5833,6419,3087,7502,7582,7018,416,6922,4982,5526,5401,8882,96,3607,2183,517,572,4385,2707,2547,9014,2698,666,699,5798,8110,2168,985,5974,6746,7440,1993,9814,4237,4387,378,9072,7574,5583,9420,833,9224,9995,4241,8011,4127,7166,7101,3173,1906,6404,6064,6620,8570,4786,167,4944,8042,1205,2646,2456,1097,1339,8449,2979,7325,8162,878,6909,1396,5924,9941,4305,9106,1786,8966,7783,1935,6635,1556,2666,6608,8959,6121,4462,9620,4072,6332,9056,4195,1901,9375,3257,2433,7129,5593,753,9234,4121,3733,4560,1524,1065,3086,5446,6584,8928,2517,2112,3231,8171,9029,2647,8479,1111,8471,2151,2314,3992,5998,3956,2999,5241,4078,4356,5473,1773,867,7912,7313,1742,1691,5611,1559,5084,573,4831,9858,2518,758,9366,9757,2298,2343,1791,1697,1850,8494,8292,2281,844,3922,418,7720,7319,3576,4287,516,2346,2655,4657,6063,4638,762,7806,2222,2976,6593,914,1901,7912,5851,1459,4014,348,7131,6485,7407,1007,2940,9098,3417,9778,6117,9795,2542,7005,3798,3673,5038,4423,2216,298,2186,3921,8667,5287,2086,496,5725,905,8175,3251,9203,2491,466,7264,7585,677,7212,3333,7514,1927,4963,2840,681,6108,2433,9550,2905,6005,1621,3939,8422,5036,4191,653,9936,9109,1164,9577,2976,3041,928,8254,6644,4609,1638,3355,8231,1353,223,7451,5198,8680,1355,6648,6472,2931,7945,7091,4807,5550,3501,4216,1634,643,34,7580,7080,6378,8878,5873,1815,1928,8013,2513,8749,8949,3770,2380,4804,8733,8377,1746,7024,3101,6810,653,7011,9596,5396,5104,1378,4429,8438,227,8440,4651,5726,8532,8535,556,6876,402,1831,2307,9247,3456,1551,642,3606,144,5527,647,860,1676,4787,3430,6651,9677,1968,6688,7071,616,7734,592,73,1993,7744,2793,5547,3073,730,5847,2325,2026,342,2654,7765,1841,5202,6076,8066,1733,4274,9236,2451,5884,1597,5377,2744,7853,5208,9214,8534,9074,8353,4503,1391,9011,1396,2074,3397,8000,1260,578,6376,443,2031,726,6547,2599,3373,7936,8049,2230,1724,1572,4200,8938,8233