Hi, I need to do this problem for an assignment. We have not focused very much on this topc and that would be great if someone could help me get started. I am not asking for a complete solution or anything, just to head me in the right direction. The problem is: Problem: Rewrite quicksort so that there are no recursive calls. The technique is to use a stack to keep track of which portions of the array still need to be sorted. Whenever we identify a portion of the array that still needs to be sorted, we will push two items onto the stack: (1) the starting index of the array segment and (2) the length of the array segment. The entire quicksort can now work as follows (with no recursion): 1. Push 0 and n onto the stack (indicating that we mush sort the n-element array segment starting at data[0]). 2. while (the stack is not empty) a. Pop a size n and a starting index i off the stack. We must now sort the n-element array segment starting at data. To do this sort, first call partition(data+i, n, pivot_index) b. If the area before the pivot index has more than one element, then we must sort this area. This area begins at data and has pivot_index elements, so push i and pivot_index onto the stack. c. If the area after the pivot index has more than one element, then we must sort this area. This area begins at data[i + pivot_index + 1] and has (n-pivot_index-1) elements, so push (i+pivot_index+1) and (n-pivot_index-1) onto the stack. With this approach, in the worst case, the stack must be as big as the array that's being stored. This worst case occusr when we keep pushing two-element array segments onto the stack. However, there is a modification that reduces the maximum stack size. When you do steps 2b and 2c, make sure that the larger array segment gets pushed onto the stack first. With this modifictaion, the maximum necessary stack size is just 2log2n. WIth this in mind, you can use a stack witha fixed size - for example, a 100-element stack is enough to sort an array with 2^50 elements. Thanks!
