-2

I'm testing some case of quick sort in visual studio but I got and error and I'm not sure what's wrong with my code.

Here's my code.

#include <iostream>
#include <cstdlib>
#include <ctime>


using namespace std;
void Swap(int *arr, int a, int b) {
    int temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}

void BubbleSort(int *arr, int len) {
    for (int i = 0; i < len - 1; i++) {
        for (int j = 0; j < len - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                Swap(arr, j, j + 1);
            }
        }
    }
}

void QuickSort(int *arr, int left, int right) {
    if (left >= right) {
        return;
    }
    int pivot = arr[left];
    int low = left;
    int high = right + 1;

    while (low <= high) {
        while (arr[++low] <= pivot && low <= right);
        while (arr[--high] >= pivot && high > left);
            if (low > high) {
                Swap(arr, left, high);
            }
            else {
                Swap(arr, low, high);
            }
    }
    QuickSort(arr, left, high - 1);
    QuickSort(arr, high + 1, right);
}




int main() {
    srand((unsigned)time(NULL));
    int *arr = new int[10000];

    for (int i = 0; i < 10000; i++) {
        arr[i] = rand() % 10000;
    }

    BubbleSort(arr, 10000);
    QuickSort(arr, 0, 9999);

    delete[] arr;
    return 0;
}

It doesn't matter if I allocate little size of memory but this code's case got an error with my QuickSort() function.

FlowORemi
  • 67
  • 1
  • 8
  • 5
    Error *how*? What happens? What is supposed to happen? Please take some time to refresh [how to ask good questions](http://stackoverflow.com/help/how-to-ask), as well as [this question checklist](https://codeblog.jonskeet.uk/2012/11/24/stack-overflow-question-checklist/). – Some programmer dude Jul 24 '19 at 04:36
  • 1
    Please see https://ericlippert.com/2014/03/05/how-to-debug-small-programs/ – eesiraed Jul 24 '19 at 04:44
  • 1
    Well the first thing you should try to is to sort less than 10000 items. Try 2 for instance, or 3 or the smallest number you can find that fails. Also temporarily remove the call to `srand` so that you get consistent results. Then use your debugger to trace through the execution of your code and find where it goes wrong. Learning how to use a debugger is the single biggest advance you can make in your productivity as a programmer. Far more efficient than asking SO to debug your programs for you. So this is a good opportunity. – john Jul 24 '19 at 04:51
  • 1
    A little clue, I'd bet a penny to a pound that the problem is that somewhere you have an out of bounds array access. – john Jul 24 '19 at 04:52
  • 1
    I recommend using one sort technique at a time. You are using BubbleSort and Quicksort in the same code, so you need to remove one of the sorting techniques and just focus on that code. As @john said, reduce the size of your data to a small number of items. – ManLaw Jul 24 '19 at 05:06
  • Thank you guys for making me realize that I was immature about asking and Thank you for valuable links! – FlowORemi Jul 25 '19 at 02:52

1 Answers1

3

When the pivot is the largest element, the first inner while loop will run until ++low is > right, causing an array out of bounds access. You have to check low < right before accessing arr[++low]. Same thing applies for the 2nd loop.

Also, use std::swap instead of rolling your own, use std::size_t for array indices, and the C++ <random> library instead of the C rand() function. And don't do using namespace std.

Erlkoenig
  • 2,664
  • 1
  • 9
  • 18