Welcome, I have to code Quicksort Lomuto and Hoare variation in C++ using MinGW.
So, I have done it. Algorithms works fine for arrays[N] where N is small number like 5, 20, 100 but I need to do it on N = 200 000. And there is exception. I don't know why. Other algorithms(Insertion, Selection, Heapsort etc. works fine for N = 200 000).
Here is my code:
int PartitionLomuto(int A[], int p, int r)
{
int x = A[r],
i = p - 1,
temp;
for (int j = p; j <= r - 1; j++)
if (A[j] <= x) {
i++;
temp = A[i];
A[i] = A[j];
A[j] = temp;
}
temp = A[i + 1];
A[i + 1] = A[r];
A[r] = temp;
return i + 1;
}
void Lomuto (int A[], int p, int r)
{
if (p < r) {
int q = PartitionLomuto(A, p, r);
Lomuto(A, p, q - 1);
Lomuto(A, q + 1, r);
}
}
//* **************************************************
int PartitionHoare(int A[], int p, int r)
{
int x = A[p],
i = p,
j = r,
temp;
while(true) {
while(A[j] > x)
j--;
while(A[i] < x)
i++;
if(i < j) {
temp = A[i];
A[i] = A[j];
A[j] = temp;
i++;
j--;
}
else
return j;
}
}
void Hoare(int A[], int p, int r)
{
if(p < r) {
int q = PartitionHoare(A, p, r);
Hoare(A, p, q);
Hoare(A, q + 1, r);
}
}
I'm creating arrays in that way:
int const arraySize = 200000;
int *ascending = new int[arraySize],
*descending = new int[arraySize],
*random = new int[arraySize];
And call function in that way:
Hoare(random,0, arraySize - 1);
Exception is in Partition function.
I really don't know what is going. I think algorithm is written right.