Quicksort assistance

[4ET0pfjN]

Hi all, I am starting to understand how recursion works, but there are still
spots I am unsure, here is the code I have so far, the problems I have are:
1)how do I indicate last index when I call: quicksort(list, pivot+1, /*END of list*/) for partitioning upper sublist
2)for the 2 elems base case, how do I know what their indices are
3)for the conquer stage, how do I know the indices to add each merged list
from each recursive level call to a new final array?
4) is returning the list in the two base cases I have correct?

Any pointers (no pun intended) would be appreciated!

#include <iostream>
using namespace std;

//NB: need start and end to determine where to divide each level's lower and 
//	upper sublist
	int *quickSort(int *list, int start, int end)
	{
		int pivot;//set it to first index for each L,R sublist and for original list
		int smallIndex;//points to last elem in lower sublist
		int size = sizeof(list)/sizeof(int);
		
		//partition
		//determine pivot position first
		pivot = start;
		smallIndex = pivot;//end index of lower sublist initialized to pivot's index
		
		//Base case: 2 elems (just sort by swapping if needed and return list?)
		if ( size == 2 )
		{
			//*Q: what are the indices to compare elems?
			if ( /*HOW DO I KNOW INDICES TO COMPARE THE 2 elems*/ )//IF elems not sorted, swap
			{
			  /**NEED ASSISTANCE HERE!*/
			}
			return list;
		}
		//Base case: 1 elem (already sorted and return list)
		else if ( size == 1 )
			return list;
		//if more than 2 elems in cur level (recursive call) sublist then 
		//	partition
		else if ( size > 2 )
		{
			for ( int i = 0; i < size; i++ )//iterate cur level's sublist
			{
				if ( list[i] < list[pivot] )//"add" cur item to lower sublist
				{
					smallIndex+=1;//mov smallIndex forwrd by 1 to "grow" lower sublist
					int temp = list[smallIndex];//hold val > pivot to mov to list end
					list[smallIndex] = list[i];//mov val < pivot to front of list 
					list[i] = temp;
				}
			}
			
			//now mov pivot to its proper place(=>swap pivot w/ smallIndex)
			//	& update indx pivot
			int holder = list[pivot];
			list[pivot] = list[smallIndex];
			list[smallIndex] = holder;
			pivot = smallIndex;//update indx pivot
			
			//recursive call for partitioning lower sublist
			quickSort(list,0,pivot - 1);
			
			//recursive call for partioning upper sublist
			quickSort(list,pivot + 1,/*END index of sublist*/);
		}
	}//END quickSort 

[h9uest]

Hi:

I understand the confusion you might have about recursion. At least I had such confusion when I started learning.
I'd like to say that it probably indicates you don't have a clear mind when implementing the algorithm if you use a for loop and pick the first element as the pivot. You're making unnecessary troubles for yourself.

Check out the code here:
http://www.algolist.net/Algorithms/Sorting/Quicksort

It's pretty neat, in my opinion.

Particularly, note how they pick pivots and the two inner while loops in partition. The while loops are for finding pairs of "abnormal" elements. By abnormal, I mean that the element to the left of the pivot is greater than the pivot (and/or the element to the right of the pivot is less than the pivot).

Then, we swap the pair of "abnormal" elements in the array.

The outer while loop moves us forward until all pairs of abnormal elements are swapped.

Hope it helps.

[4ET0pfjN]

I will take a look at the link, but as for my code, as you can see after the for loop, I move the first elem to its proper place by exchanging places w/ first index and smallIndex(which points to the end of the lower sublist).