I have implemented quick sort in c++. Following is my code .
#include <iostream>
using namespace std;
template <typename T>
void swap(T *a, T *b)
{
T temp;
temp = *a;
*a = *b;
*b = temp;
}
template <typename T>
void PrintArray(T arr[], int n)
{
cout << "---------- Array ----------" << endl;
for (int i=0; i<n ; i++)
{
cout << arr[i] <<'\t';
}
cout << endl;
}
template <typename T>
int partition(T arr[], int low, int high)
{
T pivot = arr[low];
int i = low+1, j = high;
do
{
while (pivot >= arr[i])
{
i += 1;
}
while (pivot < arr[j])
{
j -= 1;
}
if (i<j)
{
swap<T>(arr[i], arr[j]);
}
}while( i < j);
swap<T>(arr[low], arr[j]);
return j;
}
template <typename T>
void quick_sort(T arr[], int low, int high)
{
if (low < high)
{
int parition_index;
parition_index = partition<T>(arr, low, high);
quick_sort<T>(arr, low, parition_index-1);
quick_sort<T>(arr, parition_index+1, high);
}
}
int main()
{
// Array creation
int n = 8;
int a[] ={4, 3,2, 1, 18, -1, 89, -200};
// Array sorting
quick_sort<int>(a,0, n);
PrintArray<int>(a, n);
return 0;
}
It gives sorted array i.e -200, -1, 1, 2, 3, 4, 18, 89 most of the times. However, re-running the code may gives garbage values at some indices (for ex: -968225408, -200, -1, 1, 2, 3, 4, 18). To check, I replaced all the functions in the code above with the functions from blocks in the post https://www.geeksforgeeks.org/quick-sort/ . Nonetheless, the problem persists.
What could be the problem with the code and what is the solution to the problem.
@FrançoisAndrieux comments were very useful in finding out the problem.
As he pointed out that j is taking 8 as value which is out of bounds.
To solve the problem
step 1: quick_sort<int>(a,0, n-1); in the int main().
steps 2: knock off the custom swap function