How do i make the bottom function non-recursive, ive tried but by creating new functions which is not the point in this problem. The first function is given and the inplace_quicksort_non_recursive is created by me.
import random
def inplace_quick_sort(S, a, b):
"""Sort the list from S[a] to S[b] inclusive using the quick-sort algorithm."""
if a >= b: return # range is trivially sorted
pivot = S[b] # last element of range is pivot
left = a # will scan rightward
right = b-1 # will scan leftward
while left <= right:
# scan until reaching value equal or larger than pivot (or right marker)
while left <= right and S[left] < pivot:
left += 1
# scan until reaching value equal or smaller than pivot (or left marker)
while left <= right and pivot < S[right]:
right -= 1
if left <= right: # scans did not strictly cross
S[left], S[right] = S[right], S[left] # swap values
left, right = left + 1, right - 1 # shrink range
# put pivot into its final place (currently marked by left index)
S[left], S[b] = S[b], S[left]
# make recursive calls
inplace_quick_sort(S, a, left - 1)
inplace_quick_sort(S, left + 1, b)
return left
def inplace_quick_sort_nonrecursive(S):
stack = [] # create a stack for storing sublist start and end index
a = 0 # get the starting and ending index of a given list
b = len(S) - 1
pivot = S[b]
stack.append((a, b)) # push the start and end index of the array into the stack
while len(stack) > 0: # loop till stack is empty
a, b = stack.pop() # remove top pair from the list and get sublist starting and ending indices
pivot = inplace_quick_sort(S, a, b) # rearrange elements across pivot
if pivot - 1 > a: # push sublist indices containing elements that are less than the current pivot to stack
stack.append((a, pivot - 1))
if pivot + 1 < b: # push sublist indices containing elements that are more than the current pivot to stack
stack.append((pivot + 1, b))
origList = random.sample(range(100), 100)
origList2 = random.sample(range(100), 100)
origList.extend(origList2)
inplace_quick_sort_nonrecursive(origList)
errorIndices = []
for i in range(100):
ind1 = 2*i
ind2 = ind1+1
if origList[ind1] != i:
errorIndices.append(ind1)
if origList[ind2] != i:
errorIndices.append(ind2)
if len(errorIndices) == 0:
print("PASSED")
else:
print("Error in indices: " + str(errorIndices))
What do i need to create so the bottom function becomes non-recursive
Advertisement
Answer
The question is using a variation of Hoare partition scheme (but with issues). Example with classic Hoare partition scheme. Note Hoare splits partition into elements <= pivot and elements >= pivot; the pivot and elements == pivot can end up anywhere, so Hoare only splits partition into 2 parts (the pivot is not put into place and cannot be excluded from later partition steps).
import random
from time import time
def qsort(a):
if len(a) < 2: # if nothing to sort, return
return
stack = [] # initialize stack
stack.append([0, len(a)-1])
while len(stack) > 0: # loop till stack empty
lo, hi = stack.pop() # pop lo, hi indexes
p = a[(lo + hi) // 2] # pivot, any a[] except a[hi]
i = lo - 1 # Hoare partition
j = hi + 1
while(1):
while(1): # while(a[++i] < p)
i += 1
if(a[i] >= p):
break
while(1): # while(a[--j] < p)
j -= 1
if(a[j] <= p):
break
if(i >= j): # if indexes met or crossed, break
break
a[i],a[j] = a[j],a[i] # else swap elements
if(j > lo): # push indexes onto stack
stack.append([lo, j])
j += 1
if(hi > j):
stack.append([j, hi])
# test sort
a = [random.randint(0, 2147483647) for r in range(512*1024)]
s = time()
qsort(a)
e = time()
print e - s
# check to see if data was sorted
f = 0
for i in range (1 ,len(a)):
if(a[i-1] > a[i]):
f = 1
break
if(f == 0):
print("sorted")
else:
print("error")
In response to comment, a simple example in C++.
void QuickSort(uint64_t arr[], size_t lo, size_t hi)
{
uint64_t * stk = new size_t [hi+1-lo]; // allocate "stack"
size_t stki = 0; // stack index
stk[stki+1] = hi; // init stack
stk[stki+0] = lo;
stki += 2;
while(stki != 0){
stki -= 2;
lo = stk[stki+0];
hi = stk[stki+1];
if(lo >= hi)
continue;
uint64_t pivot = arr[lo + (hi - lo) / 2];
size_t i = lo - 1;
size_t j = hi + 1;
while (1)
{
while (arr[++i] < pivot);
while (arr[--j] > pivot);
if (i >= j)
break;
std::swap(arr[i], arr[j]);
}
stk[stki+3] = hi;
stk[stki+2] = j+1;
stk[stki+1] = j;
stk[stki+0] = lo;
stki += 4;
}
delete [] stk; // free "stack"
}
The original version of quicksort limited stack space to 2*ceil(log2(size)) by pushing indexes of larger partition onto stack, and looping on smaller partition. Hoare used the term “nest” instead of stack in his original paper.
void QuickSort(uint64_t arr[], size_t lo, size_t hi)
{
if(lo >= hi)return; // if less than 2 elements, return
// allocate stack
size_t s = 2*(size_t)(ceil(log2(hi+1-lo)));
uint64_t * stk = new size_t [s];
s = 0; // stack index
stk[s++] = hi; // init stack
stk[s++] = lo;
while(s != 0){ // while more partitions
lo = stk[--s];
hi = stk[--s];
while(lo < hi){ // while partion size > 1
uint64_t pivot = arr[lo+(hi-lo)/2];
size_t i = lo-1; // Hoare parttion
size_t j = hi+1;
while (1)
{
while (arr[++i] < pivot);
while (arr[--j] > pivot);
if (i >= j)
break;
std::swap(arr[i], arr[j]);
}
i = j++; // i = last left, j = first right
if(i - lo > hi - j){ // push larger partition indexes to stack,
if (lo < i) { // loop on smaller
stk[s++] = i;
stk[s++] = lo;
}
lo = j;
continue;
} else {
if (j < hi) {
stk[s++] = hi;
stk[s++] = j;
}
hi = i;
continue;
}
}
}
delete [] stk; // free "stack"
}