Why is Memory Limit Exceeded when I replace i<j in the while loop parentheses in quicksort with i<=j?

Viewed 61
#include<iostream>
int arr[100010] = { 0 };
void swap(int* a, int* b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
    return;
}
void q_sort(int* arr, int l, int r)
{
    if (l >= r)return;
    int i = l - 1, j = r + 1, k = arr[l + r + 1 >> 1];
    while (i < j)//In this position ,when I replace i<j with i<=j,the result is Memory Limit 
                   Exceeded?
    {
        do i++; while (arr[i] < k);
        do j--; while (arr[j] > k);
        if (i < j) swap(&arr[i], &arr[j]);
    }
    q_sort(arr, l, i - 1);
    q_sort(arr, i, r);
    return;
}

int main(void)
{
    int n = 0;
    scanf("%d", &n);
    for (int a = 0; a < n; a++) scanf("%d", &arr[a]);
    q_sort(arr, 0, n - 1);
    for (int a = 0; a < n; a++) printf("%d ", arr[a]);
    return 0;
}

If I choose the i<j,the result is right.I do understand if i=j ,I don't have to go through the loop.But if I use i<=j,it just do one more loop.why Why is this caused Memory Limit Exceeded? I think i<=j only cause one more loop,and it doesn't cause any other bad thing. For example ,arr[5]={1,2 3 4 5}k=3.if i<=j,at the end of the loop ,i=3,j=1,then when I call q_sort(arr,0,3-1) and q_sort(arr,3,4),these are both right. But why the final result is wrong.

0 Answers
Related