Help with Quicksort (choosing middle element as pivot)

help
, ,
1

I need to choose middle element as pivot. What should I do. I tried changing pivot to a[mid],
but there’s something I am missing, which I can’t seem to find out.

int partition(int a[], int l, int h, int n)
{
	int pivot = a[l];
	int i = l, j = h;
	while (i < j)
	{
		while (i < n && a[i] <= pivot)i++;
		while (j >= 0 && a[j] > pivot)j--;
		if (i < j)swap(a[i], a[j]);
	}
	swap(a[l], a[j]);
	return j;
}
void quicksort(int a[], int l, int h, int n)
{
	if (l < h)
	{
		int j = partition(a, l, h, n);
		quicksort(a, l, j - 1, n);
		quicksort(a, j + 1, h, n);
	}
}

This code works fine but I’m having issues with the one below:

int partition(int a[], int l, int h, int n)
{
	int mid = (l + h) / 2;
	int pivot = a[mid];
	int i = l, j = h;
	while (i < mid && j > mid)
	{
		while (i < mid && a[i] <= pivot)i++;
		while (j > mid && a[j] > pivot)j--;
		if (i < mid && j > mid)swap(a[i], a[j]);
	}
	swap(a[mid], a[j]);
	return j;
}
void quicksort(int a[], int l, int h, int n)
{
	if (l < h)
	{
		int j = partition(a, l, h, n);
		quicksort(a, l, j - 1, n);
		quicksort(a, j + 1, h, n);
	}
}

Any help would be appreciated!

1 Like
2

Its merge sort i guess,( special case of quick sort when middle element is set as pivot)

3

I think merge sort is different. In merge sort you don’t need to choose a pivot and perform swaps to correctly position the pivot, you just need to recursively merge two sorted arrays. It works because at the base of the stack you get arrays with just one element, which is obviously always sorted, and thus you go upwards building sorted arrays of length 2…4…8 and eventually the whole array.
However, In quicksort any element in the array can be chosen as pivot. But all the implementations I can find online seem to take either the first element or the last element as pivot, whereas I need the pivot to be middle element always (For better time complexity when the array is sorted, that is, from O(N*N) to O(NlogN)).

2 Likes
4

once try
while (j >= mid && a[j] > pivot) j–;
instead of
while (j > mid && a[j] > pivot)j–;
and then chk fo test cases

1 2 3 4 5 6 7
7 6 5 4 3 2 1
1 2 4 4 2 1
7 7 3 3 2 2 1
hope it may work