Runtime error when running QuickSort using while loops in split function

Question

I implemented my QuickSort algorithm as follows. The sortArray function the entry point for sorting the array. It initializes the lower and upper bounds of the array and then calls the quicksort function. The quicksort recursively sorts the array by dividing it into smaller subarrays and sorting each subarray. It calls the split function to partition the array. The split function returns the index of the where the split has to be made. The code is as follows -

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        
        cout << "Running Code" << endl;
        int lower = 0;
        int upper = nums.size() - 1;
        

        quicksort(lower, upper, nums);
        return nums;
    }

    void quicksort(int lower, int upper, vector <int> &nums )
    {
        if(lower<upper)
        {
            int index = split(lower, upper, nums);
            cout << index << endl;
            quicksort(lower,index-1,nums);
            quicksort(index+1,upper,nums);
        }
        
    }

    int split(int lower, int upper, vector<int> &nums)
    {
        int base = nums[lower];
        int start = lower;
        int end = upper;

        printf("start: %d end: %d\n", start, end);
        
        while(start < end)
        {
                      
            while(nums[start] < base);
            start++;
          
            while(nums[end] > base);
            end--;

            if(start<end)
            swap(nums[start], nums[end]);

        }

        swap(nums[lower],nums[end]);

        return end;

       


    }
};

I want to recursively sort the array, but I get a runtime error as shown below-

=================================================================
==22==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x5020000000a0 at pc 0x558a0c57ac59 bp 0x7ffcb3489590 sp 0x7ffcb3489588
READ of size 4 at 0x5020000000a0 thread T0
    #4 0x7fa09395ed8f  (/lib/x86_64-linux-gnu/libc.so.6+0x29d8f) (BuildId: c289da5071a3399de893d2af81d6a30c62646e1e)
    #5 0x7fa09395ee3f  (/lib/x86_64-linux-gnu/libc.so.6+0x29e3f) (BuildId: c289da5071a3399de893d2af81d6a30c62646e1e)
0x5020000000a0 is located 0 bytes after 16-byte region [0x502000000090,0x5020000000a0)
allocated by thread T0 here:
    #6 0x7fa09395ed8f  (/lib/x86_64-linux-gnu/libc.so.6+0x29d8f) (BuildId: c289da5071a3399de893d2af81d6a30c62646e1e)
Shadow bytes around the buggy address:
  0x501ffffffe00: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x501ffffffe80: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x501fffffff00: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x501fffffff80: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x502000000000: fa fa fd fa fa fa fd fa fa fa fd fa fa fa fd fa
=>0x502000000080: fa fa 00 00[fa]fa fa fa fa fa fa fa fa fa fa fa
  0x502000000100: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x502000000180: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x502000000200: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x502000000280: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x502000000300: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07 
  Heap left redzone:       fa
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
  Left alloca redzone:     ca
  Right alloca redzone:    cb
==22==ABORTING

I spent a lot of time trying to debug the code but with no luck. Any help will be much appreciated. Thanks.

Recommendation: Turn on address Sanitizer and debugging information in your build. If you rebuild the program and feed in the same set of test inputs, you will get a much more complete diagnostic that tells you pretty much exactly what went wrong and where. This leaves only fixing the problem up to you. — user4581301
– user4581301, Commented Mar 6, 2024 at 20:11
Looks like you're trying to implement Hoare partitioning. Compare the implementation at the link to what you've written. The mistake will likely be in the differences between the two. — user4581301
– user4581301, Commented Mar 6, 2024 at 20:13
<Expletive deleted> Leetcode. Don't waste your time debugging via judge. They don't provide enough information BY DESIGN. Set up a build system on a computer under your control. You'll get MUCH better tool support. With a decent debugger at your fingertips you should be able to isolate the problem in under five minutes. — user4581301
– user4581301, Commented Mar 6, 2024 at 20:24
@blazingcannon -- and I dont have the premium version to debug the code -- Please read this comment concerning having to pay "premium" to use a debugger. You are getting swindled if leetcode is charging money for debugger usage. — PaulMcKenzie
– PaulMcKenzie, Commented Mar 6, 2024 at 21:37
Blazingcannon, perfectly usable development tools have been free (in varying meanings of free) for decades. Under many circumstances I prefer the open-source-free tools because they don't have the same motivation to force you into a vendor lock. — user4581301
– user4581301, Commented Mar 6, 2024 at 21:49

trincot · Accepted Answer · 2024-03-07 07:41:05Z

There are several issues:

while(nums[start] < base); is a loop with an empty body (notice the semicolon), so if the condition is true, the loop will never exit. You have the same error in the next while loop.

In your partitioning implementation, you're mixing concepts from the Lomuto scheme and the Hoare scheme. Here are some key differences (of split) between the two schemes:

Property	Lomuto	Hoare	Your code's intent
Is the returned index always the pivot's index?	yes	no	yes
Is the original pivot index excluded from the loop?	yes	no	no
Does the loop have two indices that walk towards eachother?	no	yes	yes

As you can see the intent of your code (ignoring the bugs) does not match with either scheme.

As Hoare's scheme performs significantly fewer swaps on average, I suggest you fix your code to align with that scheme:

As Hoare's scheme does not necessarily return the index of the pivot, and the pivot value could be anywhere at either side, the first recursive call of quicksort should not exclude that index. So change it to:
```
quicksort(lower,index,nums);
```
The final swap in split is not a step of Hoare's scheme, and it would not work either: the pivot value at lower might have been swapped to a different location, so it would bring havoc in that case. You should omit this swap.
To avoid more complex code, an implementation of Hoare's algorithm will actually always increment start and decrement end at least once per iteration of the loop. So change your inner while loops to do...while loops.

Here is the correction of your quicksort code, using Hoare's scheme:

    void quicksort(int lower, int upper, vector <int> &nums )
    {
        if(lower<upper)
        {
            int index = split(lower, upper, nums);
            quicksort(lower,index,nums); // Hoare's scheme cannot exclude index
            quicksort(index+1,upper,nums); 
        }
    }

    int split(int lower, int upper, vector<int> &nums)
    {
        int base = nums[lower];
        int start = lower - 1;  // Start one off
        int end = upper + 1;    // (idem)

        while(start < end)
        {
            do { // Always increment at least once
                start++;
            }
            while(nums[start] < base); 
          
            do { // Always decrement at least once
                end--;
            }
            while(nums[end] > base);

            if(start<end)
                swap(nums[start], nums[end]);
        }
        // Hoare's scheme does not attempt to swap the pivot value to nums[end] 
        return end;
    }

Collectives™ on Stack Overflow

Runtime error when running QuickSort using while loops in split function

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related