Các lớp tăng gấp đôi-kết thúc danh sách được gọi là FirstLastList. Như đã thảo luận, có hai mục dữ liệu, đầu tiên và cuối cùng, mà chỉ mục đầu tiên và mục cuối cùng trong danh sách. Nếu chỉ có một mục trong Đối với vấn đề ban đầu của chúng tôi với một loạt các 100, | The number of levels in the table shows that with 12 data items the machine stack needs enough space for 5 sets of arguments and return values one for each recursion level. This is as we ll see later somewhat greater than the logarithm to the base 2 of the number of items log2N. The size of the machine stack is determined by your particular system. Sorting very large numbers of data items using recursive procedures may cause this stack to overflow leading to memory errors. Things to Notice Here are some details you may notice as you run the quickSort1 Workshop applet. You might think that a powerful algorithm like quicksort would not be able to handle subarrays as small as 2 or 3 items. However this version of the quicksort algorithm is quite capable of sorting such small subarrays leftScan and rightScan just don t go very far before they meet. For this reason we don t need to use a different sorting scheme for small subarrays. Although as we ll see later handling small subarrays differently may have advantages. At the end of each scan the leftScan variable ends up pointing to the partition that is the left element of the right subarray. The pivot is then swapped with the partition to put the pivot in its proper place as we ve seen. As we noted in steps 3 and 9 of Figure leftScan ends up pointing to the pivot itself so the swap has no effect. This may seem like a wasted swap you might decide that leftScan should stop one bar sooner. However it s important that leftScan scan all the way to the pivot otherwise a swap would unsort the pivot and the partition. Be aware that leftScan and rightScan start at left-1 and right. This may look peculiar on the display especially if left is 0 then leftScan will start at -1. Similarly rightScan initially points to the pivot which is not included in the partitioning process. These pointers start outside the subarray being partitioned because they will be incremented and decremented respectively before they re used the first
