Эксперименты по быстрой сортировке в худших случаях. Это работает хорошо, но в худших случаях произошла ошибка UnKnown. думаю

Question

ошибка доступа к памяти (не определена).

Я экспериментирую с быстрой сортировкой для n различных элементов (n> 0). он работает правильно для перемешанного массива, даже если количество элементов превышает миллионы, но не работает в худших случаях, когда n> = 4000.

В чем проблема и как я могу это исправить?

это код Python

import random
import time as tm
import sys


def Quick_Sort(A,s,e):

    if s >= e:          
        return


    p = A[s]             #first # of the array is the povot
    i = s               
    j = e


    while i < j:
        while i < e and A[i] <= p:  #finding bigger numbers
            i = i+1
        while j > s and A[j] > p:   #finding smaller numbers
            j = j-1
        if i < j:                   
            A[i], A[j] = A[j], A[i]


    A[s], A[j] = A[j], A[s]         # sort the pivot



    Quick_Sort(A,s,j-1)           #subarray of smaller numbers
    Quick_Sort(A,j+1,e)           #subarray of bigger numbers


if __name__=='__main__':

    sys.setrecursionlimit(10**6) #for expanding recursion limit

    A=[]            
    size = 10000  #size of array
    r_tm = 0

    for i in range(1, size +1):  # n distinct elements
        A.append(i)             

    t=A[size-1]             #worst case
    A[1:size]=A[0:size-1]
    A[0] = t

    #random.shuffle(A)     #it works well


    s_tm = tm.time()
    Quick_Sort(A,0,size-1)
    e_tm = tm.time()

    for i in range(0,size-1):    #for checking array sorted well
        if A[i] > A[i+1]:
            print("Wrong, %d",i)
            break

    r_tm += round(e_tm - s_tm, 3)


    print("size: %d, time: %f" %(size, r_tm))

это код C ++

оболочка показывает 'Процесс завершен с кодом выхода -1073741571'

#include <iostream>
#include <vector>
#include <algorithm>
#include <random>

using namespace std;

void Quick_Sort(vector<int> &A, int s, int e);
int main() {
    vector<int> A;
    int c = 0;
    std::random_device rd;
    std::mt19937 g (rd());

    int size = 4000;

    A.push_back(size);

    for (int i = 1; i < size; i++) {
        A.push_back(i);
    }

    //shuffle(A.begin(),A.end(),g);  //it works well


    Quick_Sort(A, 0, size - 1);


    for (int i = 1; i < size; i++) { //for checking array sorted well
        if (A[i - 1] > A[i]) {
            cout << "Wrong" << endl;
            return 0;
        }
    }

}

void Quick_Sort(vector<int> &A, int s, int e) {
    if (s >= e)         
        return;

    int p = A[s];            //first # of array is the pivot
    int i = s;
    int j = e;
    int tmp = 0;           

    while (i < j) {

        while ((i < e) && (A[i] <= p))      //finding bigger numbers
            i = i + 1;

        while ((j > s) && (A[j] > p))       //finding smaller numbers
            j = j - 1;

        if (i < j) {            
            tmp = A[i];
            A[i] = A[j];
            A[j] = tmp;
        }
    }

    tmp = A[s];    //sort the pivot
    A[s] = A[j]; 
    A[j] = tmp; 


    Quick_Sort(A, s, j - 1);           //subarray of smaller numbers
    Quick_Sort(A, j + 1, e);           //subarray of bigger numbers

}

Answer 1

Вероятно, это связано с переполнением стека. В плохом случае ваша рекурсия занимает глубину O ( size ).

И кстати, это совершенно неправильный способ реализации быстрой сортировки в C ++.