Quick Sort won't sort an array that has 4385 or more elements

[AJ Wants Your Pizza]

I cannot get quick sort to work with an array that has more than 4384 elements. I have three slight variations of quick sort that I have been told work, and they all do on arrays that have less than 4385 elements, but not otherwise

I have been banging my head against this for hours. I have tried different data types and I do not understand what is happening.



Please help me

#include <iostream>

const short SIZE = 4390;

void swapInnanet(int* a, int* b);

int partitionInnanet(int arr[], int low, int high);

void quickSortInnanet(int arr[], int low, int high);

////////////////////////////////////////////////////////////

void swap(int a, int b);

int partition(int arr[], int low, int high);

void quickSort(int arr[], int low, int high);


//////////////////////////////////////////////////////////////

int Hpartition(int arr[], int low, int high);

void HquickSort(int arr[], int low, int high);

int main()
{
	int array[SIZE];

	for (int i = 0; i < SIZE; i++)
		array[i] = SIZE - i;

	for (int i = 0; i < SIZE; i++)
		std::cout << array[i] << std::endl;

	//quickSort(array, 0, SIZE);

	//quickSort(array, 0, SIZE - 1);

        //HquickSort(array, 0, SIZE - 1);

	HquickSort(array, 0, SIZE);

	for (int i = 0; i < SIZE; i++)
		std::cout << array[i] << std::endl;

	std::cin.get();
	std::cin.get();
	return 0;
}

// A utility function to swap two elements
void swapInnanet(int* a, int* b)
{
	int t = *a;
	*a = *b;
	*b = t;
}

/* This function takes last element as pivot, places
the pivot element at its correct position in sorted
array, and places all smaller (smaller than pivot)
to left of pivot and all greater elements to right
of pivot */
int partitionInnanet(int arr[], int low, int high)
{
	int pivot = arr[high];    // pivot
	int i = (low - 1);  // Index of smaller element

	for (int j = low; j <= high - 1; j++)
	{
		// If current element is smaller than or
		// equal to pivot
		if (arr[j] <= pivot)
		{
			i++;    // increment index of smaller element
			swapInnanet(&arr[i], &arr[j]);
		}
	}
	swapInnanet(&arr[i + 1], &arr[high]);
	return (i + 1);
}

/* The main function that implements QuickSort
arr[] --> Array to be sorted,
low  --> Starting index,
high  --> Ending index */
void quickSortInnanet(int arr[], int low, int high)
{
	if (low < high)
	{
		/* pi is partitioning index, arr[p] is now
		at right place */
		int pi = partitionInnanet(arr, low, high);

		// Separately sort elements before
		// partition and after partition
		quickSortInnanet(arr, low, pi - 1);
		quickSortInnanet(arr, pi + 1, high);
	}
}

void swap(int a, int b)
{
	int t = a;
	a = b;
	b = t;
}

void quickSort(int arr[], int low, int high)
{
	if (low < high)
	{
		int q = partition(arr, low, high);
		quickSort(arr, low, high - 1);
		quickSort(arr, q + 1, high);
	}
}

int partition(int arr[], int low, int high)
{
	int pivot = arr[high];

	int i = low - 1;
	int j = low;

	for (j; j < high; j++)
	{
		if (arr[j] <= pivot)
		{
			i++;
			swap(arr[i], arr[j]);
		}
	}

	i++;
	swap(arr[i], arr[j]);
	return i;
}

void HquickSort(int arr[], int low, int high)
{
	if (low < high)
	{
		int q = Hpartition(arr, low, high);
		HquickSort(arr, low, high);
		HquickSort(arr, q + 1, high);
	}
}

int Hpartition(int arr[], int low, int high)
{
	int pivot = arr[low];

	int i = low - 1;
	int j = high + 1;

	while (low)
	{
		do
		{
			i++;
		} while (arr[i] < pivot);

		do
		{
			j--;
		} while (arr[j] > pivot);

		if (i <= j)
			return j;

		swap(arr[i], arr[j]);
		
	}
}

[AJ Wants Your Pizza]

The one marked innanet is the only one working for me know. and it varies between not working at 4300 - 4380.

[TheIdeasMan]

Hi,

First step: see if it compiles - it doesn't.

In function 'int partition(int*, int, int)':
127:8: warning: statement has no effect [-Wunused-value]
In function 'int Hpartition(int*, int, int)':
176:1: warning: control reaches end of non-void function [-Wreturn-type]

I used cpp.sh which you can get it with the gear icon at the top right of your code. I turned on all 3 warning levels

Warnings are your friend, they tell you what is wrong with your program.

Can you explain the purpose of line 3?

[keskiverto]

int main()
{
    int array[SIZE];
    // ...
}

Static array, allocated on stack memory. Why not:

int main()
{
    std::vector<int> array( some-large-number );
    // ...
}

Then you should have one less restriction.

[icy1]

HquickSort looks like the Hoare partition scheme. https://en.wikipedia.org/wiki/Quicksort#Hoare_partition_scheme

Yes, this is the good one, but you've made some mistakes. Look carefully at the pseudocode next time. See comments of your posted code. Corrected code block with vectors is below (I already had it laying around). Can of course continue to use basic arrays, but vectors are easier to work with and you don't have to carry around a SIZE variable.

int main()
{
    // ... stuff ...
    HquickSort(array, 0, SIZE);     // SIZE is invalid index of array!!!   SIZE-1 is correct here
}

//  Errors in bold; correct method shown below
// 1. (Minor) partition variable should be p and not q, as per wiki pseudocode
// 2. You used wrong upper bound for the low half (didn't use p).
// Some stylistic things: int[] turns into int* anyway; latter is just clearer for me
// Could use 'lo' and 'hi' var names just to be consistent with wiki pseudocode naming
void HquickSort(int arr[], int low, int high)
{
	if (low < high)
	{
		int q = Hpartition(arr, low, high);   // Prefer var name 'p' for partition
		HquickSort(arr, low, high);   // Wrong upper bound; should be 'p'
		HquickSort(arr, q + 1, high);   // p + 1
	}
}

int Hpartition(int arr[], int low, int high)
{
	int pivot = arr[low];

	int i = low - 1;
	int j = high + 1;

	// This will be false when low is 0, which will prob cause problems; should be
	//  'while(true)'  as per algorithm code in wiki
	while (low)  
	{
		do
		{
			i++;
		} while (arr[i] < pivot);

		do
		{
			j--;
		} while (arr[j] > pivot);

		// Your comparison is backwards here.  i is already expected to be lower than j
		//  because it's the left index while j is coming from the right.  Your version will
		//  exit long before the job is done.  Should be  ' if (i >= j) '
		if (i <= j)   
			return j;

		// By the way, why write your own swap method? there's std::swap
		swap(arr[i], arr[j]);  
		
	}
}

Corrected version with vectors and spaces instead of tabs ;D

#include <iostream>
#include <vector>
using namespace std;

int Partition(vector<int>& v, int lo, int hi)
{
    int pivot = v[lo];
    int i = lo-1;
    int j = hi+1;
    while (true)
    {
        do { ++i; } while (v[i] < pivot);
        do { --j; } while (v[j] > pivot);
        
        if (i >= j)
            return j;
        swap(v[i], v[j]);
    }
}

void QuickSort(vector<int>& v, int lo, int hi)
{
    if (lo < hi)
    {
        int p = Partition(v, lo, hi);
        QuickSort(v, lo, p);
        QuickSort(v, p+1, hi);
    }
}

// Slightly improved to add a newline every X elements printed
void Show(const vector<int>& v)
{
    int break_time = 20;
    int ct = 0;
    for (auto& n : v)
    {
        cout << n << " ";        
        if (++ct == break_time)
        {
            cout << endl;
            ct = 0;
        }
    }        
    cout << endl;
}

int main()
{
    const short SIZE = 4390;
    vector<int> v;
    v.reserve(SIZE);  // Optional; pre-allocate to expected final size to reduce allocations
    for (int i=0; i<SIZE; ++i)
        v.push_back( (SIZE-i) * 3 );
    Show(v);

    cout << endl << endl << "After sorting:\n";
    QuickSort(v, 0, v.size()-1);
    Show(v);
}

[icy1]

Also, your custom swap is erroneous. Please try to understand the difference between your version and "innanet" (internet?) version.

What is happening, step by step, starting with the parameters? Try to explain in your own words.

void swap(int a, int b)
{
	int t = a;
	a = b;
	b = t;
}

// I'll use different var names to differentiate
void swapInnanet(int* x, int* y)
{
	int u = *x;
	*x = *y;
	*y = u;
}