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.

Answer 1

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