j0can
j0can

Reputation: 31

Describing QuickSort Algoritm

Im having a problem to understand this algorithm, how would you describe it, mostly the while loops. I understand that this i an iterative function, and the use of Hoare partition scheme. But what does the while loops do, and why does it use breaks.

def inplace_quick_sort_nonrecursive(S):
    if len(S) < 2:
      return S
    stack = []                          #initialize the stack
    stack.append([0, len(S) - 1])       
    while len(stack) > 0:               #loop till the stack is empty
      low, high = stack.pop()           #pop low and high indexes 
      pivot = S[(low + high) // 2]      #create pivot, of any S[] except S[high]
      i = low - 1                       #Hoare partition
      j = high + 1
      while True:
        while True:                     #while (S[++i] < pivot)
          i += 1
          if(S[i] >= pivot):
            break
        while True:                       #while(S[--j] < p)
          j -= 1
          if(S[j] <= pivot):
            break
        if (i >= j):                    #if indexes met or crossed, break
          break
        S[i], S[j] = S[j], S[i]         #else swap the elements
      if (j > low):                     #push the indexes into the stack
        stack.append([low, j])
      j += 1
      if (high > j):
        stack.append([j, high])

Upvotes: 0

Views: 36

Answers (0)

Related Questions