Randomly Shuffle an array and using quick sort algorithm

Question

I have been trying to write a code to randomly shuffle the array elements, and then use the quick sort algorithm on the array elements. This is the code I wrote:

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
void swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}
void randomise(int arr[], int s, int e)
{
    int j;
    srand(time(NULL));
    for (int i = e; i >= s; i--)
    {
        int j = rand() % (i + 1);
        swap(&arr[i], &arr[j]);
    }
}
int Partition(int arr[], int s, int e)
{
    int pivot = arr[e];
    int i = s - 1;
    int j;
    for (j = s; j <= e; j++)
    {
        if (arr[j] <= pivot)
        {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[e]);
    return i + 1;
}
void QuickSort(int arr[], int s, int e)
{
    if (s >= e)
        return;
    int x = Partition(arr, s, e);
    QuickSort(arr, s, x - 1);
    QuickSort(arr, x + 1, e);
}
int main()
{
    int b[] = {1, 2, 3, 4, 5};
    randomise(b, 0, 4);
    cout << "Elements of randomised array are:";
    for (int i = 0; i <= 4; i++)
    {
        cout << b[i] << endl;
    }
    QuickSort(b, 0, 4);
    cout << "Elements after quick sort are:";
    for (int i = 0; i <= 4; i++)
    {
        cout << b[i] << endl;
    }
    return 0;
}

However, on debugging on GDB, I found out that this program gives segmentation fault. On execution, this program gives the output as:

Elements of randomised array are:4
5
2
3
1

Can someone tell me what is the bug in this code (I have tried debugging it on GDB, but I am still clueless).

Answer 1

Basically, when the error is segmentation fault, you should be looking for a bug which you will feel like crashing your head into wall, after finding it. On line 26. change <=, to < . It's in your partition function. for (j = s; j < e; j++) A little explanation about quick sort; After each time quickSort function runs on a partiotion, the last element of the partition, called pivot, will reach its' real place in array. The partition function, returns the real place of the pivot in the array. Then the main array will be split into two more partitions, before the pivot place, and after that. Your bug is returning real-pivot-place + 1, as the output of partition function. So you will run quickSort on wrong partition; the partition that is already sorted but the program will keep trying to sort it over and over because of wrong partitioning. As you may know, each time you run a function, its' variables will be saved into a stack in computer. Since your calling a recursive function over and over(that isn't supposed to stop), this stack will get full and will overflow. After that, computer will represent some undefined behavior and maybe throw an exception that can not describe the problem correctly. This is why your getting segmentation fault. But why you return real-pivot-place + 1? Because in your for loop in partition function, you will visit the pivot too, which you shouldn't. Because pivot isn't supposed to be compared with itself. So you will increase i variable unnecessarily. https://en.wikipedia.org/wiki/Call_stack Check this link for additional information about stack and how a function runs in computer.