非递归快速排序

Question

我如何使底层函数成为非递归的，我试过了，但是通过创建新函数，这不是这个问题的重点。第一个函数给出了，inplace_quicksort_non_recursive是我创建的。

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))

我需要创建什么才能使底部函数变为非递归

Answer 1

在您的 inplace_quick_sort_nonrecursive 函数中，您计算枢轴的方式没有任何意义。当您根据枢轴的值将子数组 A[start, end] 分成三个部分时（可以随机或有意选择，就像最初在这里您选择最后一个元素作为枢轴）：
A[start, p − 1], A[p], and A[p + 1...end], 其中 p 是枢轴位于。枢轴的左右部分满足以下条件：
• A[i] ≤ A[p], i ∈ [start, p − 1],
• A[i] > A[p], i ∈ [p + 1, end]

使用这个进行分区：

def partition(array, lo, hi):
    pivot = array[hi]
    i = lo - 1
    for j in range(lo, hi):
        if array[j] < pivot:
            i += 1
            temp = array[i]
            array[i] = array[j]
            array[j] = temp
    temp = array[i + 1]
    array[i + 1] = array[hi]
    array[hi] = temp
    return i + 1

阅读 Lomuto 的分区 方法以更好地理解代码。

Answer 2

问题是使用 Hoare 分区方案的变体（但有问题）。经典 Hoare 分区方案示例。注意 Hoare 将分区拆分为 elements <= pivot 和 elements >= pivot; pivot 和 elements == pivot 可以在任何地方结束，所以 Hoare 只将分区分成两部分（pivot 没有放置到位，不能从后面的分区步骤中排除）。

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")

回复评论，一个简单的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"
}

快速排序的原始版本通过将较大分区的索引推入堆栈并在较小分区上循环，将堆栈 space 限制为 2*ceil(log2(size))。 Hoare 在他的原始论文中使用术语“巢”而不是堆栈。

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"
}

非递归快速排序

Non-recursive Quicksort

python

pivot

quicksort

non-recursive