data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAKAAAAB4CAYAAAB1ovlvAAAAAXNSR0IArs4c6QAADMFJREFUeF7tnQlQlMkVxx8yXIoHKmhUdL1FwVtQcHFdoTwpddcNWTXRNbqVVFzFLBGDrhfeUeKVeK7HWlqF93rEW/E2eCEGFUGC9xHxiqtSoqT+nepmRtBRmbFn+d6r2qJm7K9f979/28fr7m+c8vLy8oiNFdCkgBMDqEl5disUYAAZBK0KMIBa5WfnhgLwzJkz9PDhQ6pevbrdW/7+/fu0f/9+ioqKsruvn7MDwwB46tQpKlWqFDk5ORHWXe/zNzf+E6pY0tlqe5du3JGuBg8Xfg4fPkwDBgyw+oxRExgGwG3btpGvr69o56ysLIqIiKCzZ89SQEAAbd68WX1esGABzZ07l0JCQqhZs2a0a9cuWrt2rXjOZ0lnKunipFgpNT6VclO2Us7a4QX4yfr1P9R3/v7+RuXLar0NA+DJkyeVGDExMTR16lRycXGhKlWq0NChQ+nmzZtiuDx9+jSNHTuWevfuTe7u7rRkyRI6ceKEeNZ3ZQ8LAJ1rB5OpWY9CAUz75QblDyCXKFHCamMYMYFhAEQvVrVqVTH05uTkUPv27enWrVtUuXJlSkpKIkAJIFu3bi3SdOzYUfSMkydPpgsXLtC9e/eo1uovLHvAcamUe7bwHvBfPVeroR55shWugGEAPHToEL148aJIHDTa1JfcTflD8OsyMzUMp39+9Bvxz0ePHqURI0YUyW9xftgwAKIRDxw4QJmZmaInlCYXI7b+jFXwwYMHac6cOcWZnyLXzVAAFlktzsDmClgAmJKSQo8ePRJxsvcJU7xveAPPXblyhcqUKUONGze2eSU5Q8dVQAGIIG3ZsmUFeNIkUB/yMwLFTZo0cVzFuGQ2VUABiPmR3CGoWbOmWCXu27eP1qxZI+Yxrq6u5OPjQ6tWrRLfI2SxceNGmxYGmaEnDA0NtXm+MsMdO3bQuXPnxEd7/g/m7e1NXbp0ofLly9utLsUhYwUgJufSunfvThAQwdqlS5dScHAwXbp0iWrUqCHiY6tXr6a+ffuKGJo9rFatWvbIljIyMoqU79zfdaYAj/tW8+g1Zz/9J9dNpEOwu2fPnlafMWoCBSAAcxSrXbu2zYuCOKCfn1+R5rYVF3e0iAO+qZBX+m1XPWzDhg1tXp/ikqECMD09XdXJt1o1Sj+XIgS0t718+ZJKeXlbuKlbt67N3WKHQ85vsTOBzw8ePKAtW7bQ4MGDRWhm8eLF1LVrV1q2bBnt3btXHCZAOk9PT3r8+DFV+SGiAIClYpPop0mBBcqb8eUm9R0WVrwTUniTKgAvXryoUiR8HUTDgkpTonsI+YZ9RV41Gqh/s1XcLGXXGgpJ/zu55D0n57FpdPXqVeWjXr16Ngdw+/bt5OXlJfLF/HXYsGFinjtq1ChauHAhJSQkUGRkJK1YsUJMNzp16qTSBQYG0u3bt6lmQi/LnZDYJHLyrECPYwv22KmfrVF1CAoKsnl9ikuGCsC0tDQ1ZByKDiHvpmHU+LdTVD3jBvQivwcXrNbbZCpBn69LpdTUVJW2QYN8gPElGhNWqVIlqjgvlDynXiFz//Xr17fq510TREdHE+a2RQkv1Vv/5VsPwckRq4SeWNV369btXYtrmPQKwPPnz4tKo4EO/6ktNf12BXlVr68a7M7vW1B5N+vbUAKsFf8m5IeFTG5urthjlQ2PoQ1hlidPnhB63bxryfT1uL+J9NL/q8DaqjUmTJhAbdq0ee/sAgL8ycfbx+rzlzIzxYkbDPHh4eEivslmZQhGaEKGJY7GhFK7vx4TTyA0g9BI9uBW5OWaD2Dd9bfoxcNsyvyqUYGcfX7IFBv4EkBn5/wzdAAQczAAiF4PW1Y4CGDu396T9g8xtzWPpzJ8r1dA9YDmQ+axEe0oNP6oeAqhl8uXL9O9bwItAKyTcIUyIgs/WSwBxCkQQGY+AQeAzZs3FwACUgCIzXpz/40aFYSaG7F4KqAARLxKWlJse2o7/bBFoPbB0NYWAL5Jjl+svCyAkj2geVoEsVu0aCEARK8HAGNjY0W8TBoOibIZQwEFIPaBpR0f+SkFTztooQB2QSpUqGBVladPn4r5z+sMACYnJ9PIkSNp69at4pwdVqLm/nk/2KrMxSaBAhBQSDv5XRi1nrLfopKb+gRSl6quViuOWaL34nNi2JY9IBYi0hITEwn7zuj1AGB2djaNHj1aQCmtadOmVv1wguKhgAIQAVdpp0aHU9DkRJo/f75YxSJQ+1P0xxZDcKVvZpNHg1aU9YeCq8oKS9MJgW0J4PPnz0XWmPwjuIu4GIZgDLsAcMyYMSLgKw2LFDZjKKAANL8zkTy2I7WcsEf0SgjOYiHxLOaTAosQSFTYQsTr+zQRzJUAPnv2TKkJABEKAYDoCe/evUvjx48nc/+YI7IZQwEFoLx4g2qfGdeJWsTtJsTjcDEHIOaMaP9KDziLPOq3oqzBwQWUehVAzAulAUAcbgCAyBcAxsXFqYs/SNeyZUtjqM+1zH81x/Hjx9WqN2V8Z2o2bqfF/dkXI8OpnPUpoJDUfW4y3bhxQ5wvhAE2GYjGMXVcecR3uKsLACdOnEjm/lu1asVNYxAFVA+Im2HSzsZ1oSZjtltIUKd2bcpKt74Vl/cyj16YXAuctZOZAUD0gLAjR47QnTt3xM0zc//Ye2UzhgIKwGPH/r/zAUud2I0Cvsu/WI3v7saEU53S1t8KgLSus0+JK49yDoj9UGkADnNKGPZ8ASTu6Jr752uMxoAPtVQA4vqgtHOTIsh/1FbCyWj0TliIOI3trOaApopVqWRAW/LwDyEXH1+69t0rBy6nHxPxPQkggs2vOwSwfv16mjZtmri+KK0o+7XGabriUVMFIN5hIu3ClO7k9+dNtHPnTrEPPHDgQHIe39VyL3jdTXp+K4v+e2QTZa+cbKHGy2lHxEY8hlocMkCo5XW2bt06mjFjhniHijTMEdmMoYACEBe3paVN7UENRvxooYAprttbb8VJAGUPiIWGNLzqAv/B8NIeLFTi4+PJ3H/btm2NoT7XMn8IxqUkael/+YzqDd9gsQpumHeX7s0YZF0yk4nuRm8QJ4ilIZRjPgTjngmsf//+hCF45syZ4tK4NHteSrJeAU7xIRVQPSDic9Iypn9OdaLXia2ysLAwsUBo166dzcuF7TrEH2fPni12SKTZw5fNC88Z2kQBBSAOCUjLjP+Cav1xjTjCXrp0abFlJmN6SINTLIVd8Ll27ZpY4Xbo0EHdvwBgWPniiqK54Qg+XpeGOSBeh2buH0fl2YyhgAWA8kAqAPwoKkFc2Jk1axbhPoXJZFJDMgAcMmQIzZs3T1zPxL4v7g1jsYGhFBd8cJBV5rdo0SIaNGiQ+gxQq1WrRvh7/FAizVm4RAAo0zOAxoAPtVQA7tmzRwGQNTOSTlfpTtfv3BOXdQAZAJKGE8seHh7k5uYmVrs4bICDq9j9KFeunAgw40I2QjG4Yol7vnjRIwxpcJ9Y/q2+I4rqT08lc//oQdmMoYACcPny5eqtUZdn/YoiG5ak7117kN/H9rtQk7RhMUWVOSYuJe3evVsofv36derXr58x1Oda5veAWATgxY2w+z9Ooq6e+W9KsLVOOXkmcnPKPyP45NsT6jwgelVehNhaccfNz+LtWIAQx6jM35/3oYqOng/DNcP3oRR3DD/8fkDHaAfDloIBNGzTO0bFGUDHaAfDloIBNGzTO0bFGUDHaAfDloIBNGzTO0bFGUDHaAfDloIBNGzTO0bFGUDHaAfDloIBNGzTO0bFGUDHaAfDloIBNGzTO0bFGUDHaAfDloIBNGzTO0bFGcDXtANekISfcujTp49jtFQxLQUD+IaGNf+JLfyUGX5tyR4/olNM2XqrajGAVmQq7Hfe8NJ1nB7HpS22oinAADKARSOoiE8zgO8wBOOna+3xM2JFbMOf9eMMIC9CtALMAGqVn50zgMyAVgUYQK3ys3MGkBnQqgADqFV+ds4AMgNaFWAAtcrPzhlAZkCrAgygVvnZOQPIDGhVgAHUKj87ZwCZAa0KMIBa5WfnDCAzoFUBBlCr/OycAWQGtCrAAGqVn50zgMyAVgUYQK3ys3MGkBnQqgADqFV+ds4AMgNaFWAAtcrPzhlAZkCrAgygVvnZOQPIDGhVgAHUKj87ZwCZAa0KMIBa5WfnDCAzoFUBBlCr/OycAWQGtCrAAGqVn50zgMyAVgUYQK3ys3MGkBnQqgADqFV+ds4AMgNaFWAAtcrPzhlAZkCrAgygVvnZOQPIDGhVgAHUKj87ZwCZAa0KMIBa5WfnDCAzoFUBBlCr/OycAWQGtCrAAGqVn50zgMyAVgUYQK3ys3MGkBnQqgADqFV+ds4AMgNaFWAAtcrPzhlAZkCrAgygVvnZ+f8Aev42An30UsoAAAAASUVORK5CYII=data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAeAAAAFoCAYAAACPNyggAAAAAXNSR0IArs4c6QAADoVJREFUeF7t1cEJAAAIxDDdf2m3sJ+4wEEQuuMIECBAgACBd4F9XzRIgAABAgQIjAB7AgIECBAgEAgIcIBukgABAgQICLAfIECAAAECgYAAB+gmCRAgQICAAPsBAgQIECAQCAhwgG6SAAECBAgIsB8gQIAAAQKBgAAH6CYJECBAgIAA+wECBAgQIBAICHCAbpIAAQIECAiwHyBAgAABAoGAAAfoJgkQIECAgAD7AQIECBAgEAgIcIBukgABAgQICLAfIECAAAECgYAAB+gmCRAgQICAAPsBAgQIECAQCAhwgG6SAAECBAgIsB8gQIAAAQKBgAAH6CYJECBAgIAA+wECBAgQIBAICHCAbpIAAQIECAiwHyBAgAABAoGAAAfoJgkQIECAgAD7AQIECBAgEAgIcIBukgABAgQICLAfIECAAAECgYAAB+gmCRAgQICAAPsBAgQIECAQCAhwgG6SAAECBAgIsB8gQIAAAQKBgAAH6CYJECBAgIAA+wECBAgQIBAICHCAbpIAAQIECAiwHyBAgAABAoGAAAfoJgkQIECAgAD7AQIECBAgEAgIcIBukgABAgQICLAfIECAAAECgYAAB+gmCRAgQICAAPsBAgQIECAQCAhwgG6SAAECBAgIsB8gQIAAAQKBgAAH6CYJECBAgIAA+wECBAgQIBAICHCAbpIAAQIECAiwHyBAgAABAoGAAAfoJgkQIECAgAD7AQIECBAgEAgIcIBukgABAgQICLAfIECAAAECgYAAB+gmCRAgQICAAPsBAgQIECAQCAhwgG6SAAECBAgIsB8gQIAAAQKBgAAH6CYJECBAgIAA+wECBAgQIBAICHCAbpIAAQIECAiwHyBAgAABAoGAAAfoJgkQIECAgAD7AQIECBAgEAgIcIBukgABAgQICLAfIECAAAECgYAAB+gmCRAgQICAAPsBAgQIECAQCAhwgG6SAAECBAgIsB8gQIAAAQKBgAAH6CYJECBAgIAA+wECBAgQIBAICHCAbpIAAQIECAiwHyBAgAABAoGAAAfoJgkQIECAgAD7AQIECBAgEAgIcIBukgABAgQICLAfIECAAAECgYAAB+gmCRAgQICAAPsBAgQIECAQCAhwgG6SAAECBAgIsB8gQIAAAQKBgAAH6CYJECBAgIAA+wECBAgQIBAICHCAbpIAAQIECAiwHyBAgAABAoGAAAfoJgkQIECAgAD7AQIECBAgEAgIcIBukgABAgQICLAfIECAAAECgYAAB+gmCRAgQICAAPsBAgQIECAQCAhwgG6SAAECBAgIsB8gQIAAAQKBgAAH6CYJECBAgIAA+wECBAgQIBAICHCAbpIAAQIECAiwHyBAgAABAoGAAAfoJgkQIECAgAD7AQIECBAgEAgIcIBukgABAgQICLAfIECAAAECgYAAB+gmCRAgQICAAPsBAgQIECAQCAhwgG6SAAECBAgIsB8gQIAAAQKBgAAH6CYJECBAgIAA+wECBAgQIBAICHCAbpIAAQIECAiwHyBAgAABAoGAAAfoJgkQIECAgAD7AQIECBAgEAgIcIBukgABAgQICLAfIECAAAECgYAAB+gmCRAgQICAAPsBAgQIECAQCAhwgG6SAAECBAgIsB8gQIAAAQKBgAAH6CYJECBAgIAA+wECBAgQIBAICHCAbpIAAQIECAiwHyBAgAABAoGAAAfoJgkQIECAgAD7AQIECBAgEAgIcIBukgABAgQICLAfIECAAAECgYAAB+gmCRAgQICAAPsBAgQIECAQCAhwgG6SAAECBAgIsB8gQIAAAQKBgAAH6CYJECBAgIAA+wECBAgQIBAICHCAbpIAAQIECAiwHyBAgAABAoGAAAfoJgkQIECAgAD7AQIECBAgEAgIcIBukgABAgQICLAfIECAAAECgYAAB+gmCRAgQICAAPsBAgQIECAQCAhwgG6SAAECBAgIsB8gQIAAAQKBgAAH6CYJECBAgIAA+wECBAgQIBAICHCAbpIAAQIECAiwHyBAgAABAoGAAAfoJgkQIECAgAD7AQIECBAgEAgIcIBukgABAgQICLAfIECAAAECgYAAB+gmCRAgQICAAPsBAgQIECAQCAhwgG6SAAECBAgIsB8gQIAAAQKBgAAH6CYJECBAgIAA+wECBAgQIBAICHCAbpIAAQIECAiwHyBAgAABAoGAAAfoJgkQIECAgAD7AQIECBAgEAgIcIBukgABAgQICLAfIECAAAECgYAAB+gmCRAgQICAAPsBAgQIECAQCAhwgG6SAAECBAgIsB8gQIAAAQKBgAAH6CYJECBAgIAA+wECBAgQIBAICHCAbpIAAQIECAiwHyBAgAABAoGAAAfoJgkQIECAgAD7AQIECBAgEAgIcIBukgABAgQICLAfIECAAAECgYAAB+gmCRAgQICAAPsBAgQIECAQCAhwgG6SAAECBAgIsB8gQIAAAQKBgAAH6CYJECBAgIAA+wECBAgQIBAICHCAbpIAAQIECAiwHyBAgAABAoGAAAfoJgkQIECAgAD7AQIECBAgEAgIcIBukgABAgQICLAfIECAAAECgYAAB+gmCRAgQICAAPsBAgQIECAQCAhwgG6SAAECBAgIsB8gQIAAAQKBgAAH6CYJECBAgIAA+wECBAgQIBAICHCAbpIAAQIECAiwHyBAgAABAoGAAAfoJgkQIECAgAD7AQIECBAgEAgIcIBukgABAgQICLAfIECAAAECgYAAB+gmCRAgQICAAPsBAgQIECAQCAhwgG6SAAECBAgIsB8gQIAAAQKBgAAH6CYJECBAgIAA+wECBAgQIBAICHCAbpIAAQIECAiwHyBAgAABAoGAAAfoJgkQIECAgAD7AQIECBAgEAgIcIBukgABAgQICLAfIECAAAECgYAAB+gmCRAgQICAAPsBAgQIECAQCAhwgG6SAAECBAgIsB8gQIAAAQKBgAAH6CYJECBAgIAA+wECBAgQIBAICHCAbpIAAQIECAiwHyBAgAABAoGAAAfoJgkQIECAgAD7AQIECBAgEAgIcIBukgABAgQICLAfIECAAAECgYAAB+gmCRAgQICAAPsBAgQIECAQCAhwgG6SAAECBAgIsB8gQIAAAQKBgAAH6CYJECBAgIAA+wECBAgQIBAICHCAbpIAAQIECAiwHyBAgAABAoGAAAfoJgkQIECAgAD7AQIECBAgEAgIcIBukgABAgQICLAfIECAAAECgYAAB+gmCRAgQICAAPsBAgQIECAQCAhwgG6SAAECBAgIsB8gQIAAAQKBgAAH6CYJECBAgIAA+wECBAgQIBAICHCAbpIAAQIECAiwHyBAgAABAoGAAAfoJgkQIECAgAD7AQIECBAgEAgIcIBukgABAgQICLAfIECAAAECgYAAB+gmCRAgQICAAPsBAgQIECAQCAhwgG6SAAECBAgIsB8gQIAAAQKBgAAH6CYJECBAgIAA+wECBAgQIBAICHCAbpIAAQIECAiwHyBAgAABAoGAAAfoJgkQIECAgAD7AQIECBAgEAgIcIBukgABAgQICLAfIECAAAECgYAAB+gmCRAgQICAAPsBAgQIECAQCAhwgG6SAAECBAgIsB8gQIAAAQKBgAAH6CYJECBAgIAA+wECBAgQIBAICHCAbpIAAQIECAiwHyBAgAABAoGAAAfoJgkQIECAgAD7AQIECBAgEAgIcIBukgABAgQICLAfIECAAAECgYAAB+gmCRAgQICAAPsBAgQIECAQCAhwgG6SAAECBAgIsB8gQIAAAQKBgAAH6CYJECBAgIAA+wECBAgQIBAICHCAbpIAAQIECAiwHyBAgAABAoGAAAfoJgkQIECAgAD7AQIECBAgEAgIcIBukgABAgQICLAfIECAAAECgYAAB+gmCRAgQICAAPsBAgQIECAQCAhwgG6SAAECBAgIsB8gQIAAAQKBgAAH6CYJECBAgIAA+wECBAgQIBAICHCAbpIAAQIECAiwHyBAgAABAoGAAAfoJgkQIECAgAD7AQIECBAgEAgIcIBukgABAgQICLAfIECAAAECgYAAB+gmCRAgQICAAPsBAgQIECAQCAhwgG6SAAECBAgIsB8gQIAAAQKBgAAH6CYJECBAgIAA+wECBAgQIBAICHCAbpIAAQIECAiwHyBAgAABAoGAAAfoJgkQIECAgAD7AQIECBAgEAgIcIBukgABAgQICLAfIECAAAECgYAAB+gmCRAgQICAAPsBAgQIECAQCAhwgG6SAAECBAgIsB8gQIAAAQKBgAAH6CYJECBAgIAA+wECBAgQIBAICHCAbpIAAQIECAiwHyBAgAABAoGAAAfoJgkQIECAgAD7AQIECBAgEAgIcIBukgABAgQICLAfIECAAAECgYAAB+gmCRAgQICAAPsBAgQIECAQCAhwgG6SAAECBAgIsB8gQIAAAQKBgAAH6CYJECBAgIAA+wECBAgQIBAICHCAbpIAAQIECAiwHyBAgAABAoGAAAfoJgkQIECAgAD7AQIECBAgEAgIcIBukgABAgQICLAfIECAAAECgYAAB+gmCRAgQICAAPsBAgQIECAQCAhwgG6SAAECBAgIsB8gQIAAAQKBgAAH6CYJECBAgIAA+wECBAgQIBAICHCAbpIAAQIECAiwHyBAgAABAoGAAAfoJgkQIECAgAD7AQIECBAgEAgIcIBukgABAgQICLAfIECAAAECgYAAB+gmCRAgQICAAPsBAgQIECAQCAhwgG6SAAECBAgIsB8gQIAAAQKBgAAH6CYJECBAgIAA+wECBAgQIBAICHCAbpIAAQIECAiwHyBAgAABAoGAAAfoJgkQIECAgAD7AQIECBAgEAgIcIBukgABAgQICLAfIECAAAECgYAAB+gmCRAgQICAAPsBAgQIECAQCAhwgG6SAAECBAgIsB8gQIAAAQKBgAAH6CYJECBAgIAA+wECBAgQIBAICHCAbpIAAQIECByxcQFpoRMBzwAAAABJRU5ErkJggg==Test and analyze for each of the sort algorithms: * What is the relationship between COMPS and SWAPS? * Use the > predicate instead * Change the size of the list * Instead of scrambling, sort an already-sorted list, or a reverse-sorted list.

Replaces the ith and jth items in the list with each other. No bounds checking

Use the bubble sort algorithm to sort a list of any kind of object, using a comparator (1-input reporter that reports whether the first input belongs before the second). For a 'normal' increasing sort of numbers or strings, use the regular < operator. Upvars ncomps and nswaps return a count of the number of calls to the comparator, and the number of times an out-of-order bubble is swapped.

If this comparator returns true, then items i and i+1 are out of ordern-1 passes pass 1: i=1...n-1 pass 2: i=1...n-2 ...

Scramble a list into a random order

Put a list into reverse order

Use the quicksort algorithm to sort a list of any kind of object, using a comparator (1-input reporter that reports whether the first input belongs before the second). For a 'normal' increasing sort of numbers or strings, use the regular < operator. Upvars ncomps and nswaps return a count of the number of calls to the comparator, and the number of times a pair of items is swapped.

This is the real quicksort implementation, which: * picks item[lo] as the 'pivot' * swaps within the range lo...hi to become (<pivot)pivot(>pivot) * recursively sorts subranges (<pivot) and (>pivot) The main quicksort wrapper just calls this on the range of the full list

2For a larger range, we pick a pivot and reorder the range < and > the pivot. Note there is no if for n=0 or 1, so for those base cases the function do nothing and return. nc1We just called the comparator once, and swapped once. ns1

1Recursively sort the subrange less than the pivot ncompsnswaps

ncns

1ncompsnswapsRecursively sort the subrange greater than the pivot

ncns

2,9,2033