Quicksort issues

[4ET0pfjN]

I didn't look at the actual code, just general algorithm of variables to use from a C book, but when I try to write my quicksort using the idea of pivot, lo and hi variables, program is in infinite loop. The Else block does all the real work of sorting around current sublist's pivot.

void r_quick_sort(int* list, int size, int pivot, int lo, int hi)//Initially, pivot is indx 0, lo is indx 0, hi is indx (size - 1)
{
   cout << "hey" << endl;
   if ( lo == hi )	//base case: if one elem, it's sorted => when lo, hi, pivot pt to same indx
	return;
	
   //ELSE sort L, R sublist around current list's pivot
   //ALL THE REAL SORTING done is this ELSE block
   else
   {
	while ( lo != hi )
	{
	   if ( hi >= pivot )//"grow" R sublist, i.e. move elems to R sublist by increasing indx hi
		hi = hi - 1;
			
	   else //else hi < pivot since !(>=) => <, so "grow" L sublist ( we need to swap pivot elem w/ elem @ hi which is < pivot)
	   {
		int tmp = list[hi];
		list[hi] = list[pivot];
		list[pivot] = tmp;
		lo = lo + 1;
	   }
	}
   }
	
   //set up next level's L sublist to be sorted so now array is reduced to 0 to pivot - 1 so everything from front and up to but not   including this pivot
   r_quick_sort(list, size, 0, 0, pivot - 1);
	
   //set up next level's R sublist to be sorted so now array is reduced to pivot + 1 to (size - 1) so up to last indx
   r_quick_sort(list, size, pivot + 1, pivot + 1, size - 1);
}

int main()
{
   int quickList[] = {1,2,3,4,5};
   int qSize = 5;
   int pivot = 0; 
   int lo = 0;
   int hi = qSize - 1;
	
   r_quick_sort(&quickList[0], qSize, pivot, lo, hi);
	
   print_list(&quickList[0], qSize);
   return 0;
}

B/c based on the algorithms, this is how I see it:

Initially indx lo, indx pivot point to the first indx, and indx hi points to last indx.

Then we start from hi and move to the left whenever list[h] > list[pivot], otherwise we swap list[h] w/ list[pivot] (to move elem < pivot's elem to L sublist (lower, left sublist I mean), then advance indx lo by 1. Once lo and hi meet up @ same indx, this current level's L, R sublist is sorted, so now we recursively call to sort next level's L, R sublist. So each next level's L sublist has pivot = 0, lo = 0, hi = pivot - 1. And each next level's R sublist has pivot = pivot + 1, lo = pivot + 1, hi = (size - 1)(so last indx I mean).

(lo, pivot)->[1][2][3][4][5]<-hi

[cire]

To begin with you should revise your function signature to look something like:

void r_quick_sort(int*list, unsigned size)
or
void r_quick_sort(int*beg, int*end)

A sub-section of an array can be treated as an array.

[4ET0pfjN]

Here is my updated code, I had to alternate b/t checking lo and hi whenever either list[lo] >= list[pivot] or list[hi] < list[pivot], and to check for this I needed a boolean type: was_swap_done_for_hi and I also had to update where index pivot was.

void r_quick_sort(int* list, int size, int pivot, int lo, int hi, bool was_swap_done_for_hi)//Initially, pivot is indx 0, lo is indx 0, hi is indx (size - 1)
{
	cout << "hey" << endl;
	if ( lo == hi )	//base case: if one elem, it's sorted => when lo, hi, pivot pt to same indx
		return;
	
	//ELSE sort L, R sublist around current list's pivot BEFORE we sort next level's L, R sublist (the two recursive calls that come after this ELSE-block)
	//ALL THE REAL SORTING done is this ELSE block
	else
	{
		while ( lo != hi )
		{
			//deal w/ hi when no swap needed yet, so when all elems encountered > pivot
			if ( !was_swap_done_for_hi )
			{
				if ( list[hi] >= list[pivot] )
					hi = hi - 1;
				else//else list[hi] < list[pivot]
				{
					int r_tmp = list[hi];//right sublist tmp
					list[hi] = list[pivot];
					list[pivot] = r_tmp;
					lo = lo + 1;
					pivot = hi;
					was_swap_done_for_hi = true;
				}
			}
			
			else if ( was_swap_done_for_hi )
			{
				if ( list[lo] < list[pivot] )
					lo = lo + 1;
				else//else list[lo] >= list[pivot]
				{
					int l_tmp = list[lo];//left sublist tmp
					list[lo] = list[pivot];
					list[pivot] = l_tmp;
					hi = hi - 1;
					pivot = lo;//keep track of indx of pivot
					was_swap_done_for_hi = false;
				}
			}
		}
	}
	
	//set up next level's L sublist to be sorted so now array is reduced to 0 to pivot - 1 so everything from front and up to but not including this pivot
	r_quick_sort(list, size, 0, 0, pivot - 1, was_swap_done_for_hi);//NB: I'm pretty sure last param: pivot - 1 which reps next's L sublist's hi indx will eventually reach 0 so lo = 0 == hi = 0
	
	//set up next level's R sublist to be sorted so now array is reduced to pivot + 1 to (size - 1) so up to last indx
	r_quick_sort(list, size, pivot + 1, pivot + 1, size - 1, was_swap_done_for_hi);//likewise...
}

int main()
{
  int quickList[] = {4,1,2,3,7};
  int qSize = 5;
  int pivot = 0; 
  int lo = 0;
  int hi = qSize - 1;
	
  r_quick_sort(&quickList[0], qSize, pivot, lo, hi, false);
	
  print_list(&quickList[0], qSize);
  return 0;
}

[o1vk4iN6]

You are sending more information than you need to through the function. You don't need to know the size of the array you simply need to know the address of the end point. You can set the pivot as the last variable of the array so:

void quick_sort( int * first, int * last )
{

    if( first != last )
    {

        int * pivot = last--;

        // ...

    }
}

you can also do a test between the first, middle and last value and pick the best pivot of the three (the median).

[4ET0pfjN]

Does someone mind going into detail using stack or attach a better detailed/clear diagram b/c when I work it out diagramtically, it makes sense, but when I try it w/ a diagram, there are so many sub levels of indices lo, hi, pivot that I get lost. This is haunting me, same w/ Towers of Hanoi, so basically I've become much more familiar w/ recursive functions that make sone call to itself and I can draw the stack and so forth, but more multiple recursive calls within the recursive function, I'm having a hard time getting it worked out...

I just traced it and I know the base case is wrong, b/c I want the lo index for each next level's R sublist to be pivot + 1, but when I traced that code, index: pivot + 1 was pointing to the previous level's pivot.

I used the same e.g array: {4,1,2,3,7}

So I manage to solve the first level's L, R sublist to be: 3,1,2,4,7 so now the next level's L, R sublist should be elems: 3,1,2 and 7, respectively. 7 is just one elem so lo is @ same indx as hi, but for 3,1,2, once I solve it to:
2,1,3, for the next level's R sublist, it is: pivot + 1 which is though: elem 4 (the original pivot)...I'm stuck...

[o1vk4iN6]

You don't need the if statement with the bool, that looks completely wrong that shouldn't be there.

Why not look at some quicksort pseudo code ? I mean this is well known and well documented.

[cire]

Perhaps running the following will help. It shows the (sub)array before and after the partition. Feel free to change the quickList size to see it work on smaller or lengthier arrays.

#include <iostream>
#include <iomanip>
#include <random>
#include <algorithm>
#include <functional>

namespace my {

	unsigned indention = 0 ;

	struct Indenter
	{
		Indenter() { indention += 2 ; }
		~Indenter() { indention -= 2 ; }
	};
	std::ostream& operator<<(std::ostream&os, const Indenter& i)
		{return os << std::setw(indention) << " " ;}

	template <class T>
	std::ostream& print( std::ostream& os, T array[], unsigned size, unsigned pivot )
	{
		os << "{ " ;
		unsigned i ;
		for (i = 0;  i<pivot;  ++i )
			os << array[i] << ' ' ;
		os << '<' << array[i++] << "> " ;
		for ( ; i<size; ++i )
			os << array[i] << ' ' ;
		return os << "}\n" ;
	}

	template <class T>
	void quicksort( T* left, T* right )
	{
		Indenter indent ;

		if ( left >= right)
			return ;

		std::cout << '\n' << indent << "Partitioning on pivot.\n" ;
		std::cout << indent ;
		print(std::cout, left, right-left+1, (right-left)/2) ;  

		// Pick a pivot value
		std::swap( *(right), *(left + (right-left)/2 ) ) ;


		// Find final position of pivot
		unsigned pivot_idx = 0 ;
		for ( unsigned i=0; i < right-left; ++i )
			if ( left[i] < *right )
				std::swap(left[i], left[pivot_idx++]) ;

		std::swap(left[pivot_idx], *right) ; 

		std::cout << indent << "After partitioning:\n" ;
		std::cout << indent ; 
		print(std::cout, left, right-left+1, pivot_idx) ;

		// sort subarrays
		quicksort(left, left+pivot_idx-1) ;
		quicksort(left+pivot_idx+1, right) ;
	}


	template <class T>
	std::ostream& print( std::ostream& os, T array[], unsigned size )
	{
		os << "{ " ;
		for ( unsigned i=0; i<size; ++i )
			os << array[i] << ' ' ;
		return os << "}\n" ;
	}
}

struct counting_seq
{
	int n ;
	counting_seq() : n(1) {}

	int operator()() { return n++; }
};

int main()
{
	std::srand(std::random_device()()) ;
	int quickList[7] ;
	unsigned size = sizeof(quickList) / sizeof(quickList[0]) ;

	std::generate(quickList, quickList+size, counting_seq()) ;
	std::random_shuffle(quickList, quickList+size) ;

	std::cout << "Before sort " ;
	my::print(std::cout, quickList, size ) ;

	my::quicksort(quickList, quickList+size-1) ;

	std::cout << "After sort " ;
	my::print(std::cout, quickList, size ) ;
}

[4ET0pfjN]

Does anyone know good sites or examples to practice binary recursion or multiple recursive calls within a function, I'm rewriting quick sort but I am having a hard time getting it to work. It seems to me that I understand how the sorting works, but the actual implementing it is frustrating me. I hope someone can give some examples that would hopefully let me understand the binary recursive calls in quick sort better.

this is what I coded so far, that is infinite loop. The reason for the conditions after the big else block (which does all the real work of moving elems <= pivot elem to the L sublist (so left of pivot) and elems > pivot elem to R sublist (so right of pivot). For a sorted list, the pivot is already in place, so that's why I added a boolean to only sort the R sublist. I wish universities taught recursion more properly as I literally only had one lab where we practiced 2 - 4 examples and it wasn't even on any exams. I'm pretty comfortable with a single recursive call within a recursion function, but multiple recursive calls gets me...

void r_quick_sort_v2(int* list, int size, int pivot, int lo, int hi, bool was_moving_pivot_needed)
{
	if ( lo == hi )//base case: when we have one elem => lo == hi 
		return;
	// Else if ( !sort_needed ) return;//base case: *Q:can I add base case like use bb_sort to return bool to test if list is sorted w/ flag like if 1000000 itms so no need to waste memory w/ recursion and should check on current sublist rather than entire list again
	else//Else sort L, R sublist, then move the pivot in place (Don't forget to update index of pivot)
	{
		while ( lo != hi || hi > lo)//go thru current list, do I really need this outer while loop?
		{
			while ( lo != hi )//search rightwards for a large elem or until end of this L sublist (=> no large elem found)	
				if ( list[lo] <= list[pivot] )
					lo = lo + 1;
			
			while ( hi != pivot )//search leftwards for a small elem, but if hi crosses lo, do last step: move pivot in place
			{
				if ( list[hi] > list[pivot] )
					hi = hi - 1;
				
				if ( list[hi] <= list[pivot] && (hi > lo) )//once we found the itm to swap w/ lo and hi hasn't crossed lo, then swap
				{
					int tmp = list[hi];
					list[hi] = list[lo];
					list[lo] = tmp; break;
				}
				
				if ( list[hi] <= list[pivot] && (hi <= lo))//if we found a smaller itm to replace w/ itm @ lo, BUT indx hi <= lo, then do last step: move pivot in place
				{
					if ( hi != pivot )//to prevent redundant moving pivot in place when it's already in place
					{
						int temporary = list[hi];
						list[hi] = list[pivot];
						list[pivot] = temporary;
						pivot = hi; break;
						was_moving_pivot_needed = true;
					}
				}
			}
		}
	}//END else
	
	//only sort L sublist if:
	if ( was_moving_pivot_needed )
		r_quick_sort_v2(list, size, 0, 0, pivot - 1, was_moving_pivot_needed);//break up list to a smaller R sublist to be sorted
	
	//only sort R sublist if: pivot didn't have to move in place, i.e. pivot already in place so sort R sublist
	else if ( !was_moving_pivot_needed )
		r_quick_sort_v2(list, size, pivot + 1, pivot + 1, size - 1, was_moving_pivot_needed);//break up list to a smaller R sublist to be sorted
	
	else//else there is a L, R sublist to sort
	{
		r_quick_sort_v2(list, size, 0, 0, pivot - 1, was_moving_pivot_needed);//break up list to a smaller L sublist to be sorted
		r_quick_sort_v2(list, size, pivot + 1, pivot + 1, size - 1, was_moving_pivot_needed);//break up list to a smaller R sublist to be sorted
	}
}

int main()
{
  int quickList[] = {1,2};
  int qSize = sizeof(quickList)/sizeof(int);
  int pivot = 0;
  int lo = 0;
  int hi = qSize - 1;
	
  r_quick_sort_v2(&quickList[0], qSize, pivot, lo, hi, false);
  return 0;
}

This is also an algorithm where I would never have thought of, I mean to use a lo, hi and traverse the list as such.

[4ET0pfjN]

Here is updated code...again, I'm now having trouble understanding how to update what each next recursive call's pivot, lo, hi is.

NB: I use i for lo indx, k for hi indx, and p for pivot indx in diagram of trace.
NB: I'm using in-place quick sort

Here is the tracing I did and got stuck. I know for the original L, R sublists, the i, p = 0, k = (p - 1) and for R sublists: i, p = (p + 1), k = (size - 1), but after this I don't know what to use for next level's L sublist's i,p and next level's R sublist's k (hi indx).

Diagram of trace where I'm stuck w/ determining 2nd levels and higher for their i, p, k indices:
http://i45.tinypic.com/35a6grc.png



Updated code:
==========

void r_quick_sort_v2(int* list, int size, int pivot, int lo, int hi)
{
	if ( hi <= 0 )//base case: when we have one elem or no elems (i.e. when hi < lo, it means p, lo: 0 and hi is (p - 1) which is < lo BUT hi needs be > lo)
		return;
	else//Else sort L, R sublist, then move the pivot in place (Don't forget to update index of pivot)
	{
		while ( lo != hi || hi > lo)//go thru current list, do I really need this outer while loop?
		{
			while ( lo != hi )//search rightwards for a large elem or until end of this L sublist (=> no large elem found)	
				if ( list[lo] <= list[pivot] )
					lo = lo + 1;
			
			while ( hi != pivot )//search leftwards for a small elem, but if hi crosses lo, do last step: move pivot in place
			{
				if ( list[hi] > list[pivot] )
					hi = hi - 1;
				
				if ( list[hi] <= list[pivot] && (hi > lo) )//once we found the itm to swap w/ lo and hi hasn't crossed lo, then swap
				{
					int tmp = list[hi];
					list[hi] = list[lo];
					list[lo] = tmp; break;
				}
				
				if ( list[hi] <= list[pivot] && (hi <= lo))//if we found a smaller itm to replace w/ itm @ lo, BUT indx hi <= lo, then do last step: move pivot in place
				{
					if ( hi != pivot )//to prevent redundant moving pivot in place when it's already in place
					{
						int temporary = list[hi];
						list[hi] = list[pivot];
						list[pivot] = temporary;
						pivot = hi; break;
					}
				}
			}//END WHILE: leftwards search for a small elem
		}//END BIG WHILE: to traverse current list to relatively sort elems to L, R sublist
	}//END else
	
	/*line A*/r_quick_sort_v2(list, size, 0, 0, pivot - 1);//break up list to a smaller L sublist to be sorted
	/*line B*/r_quick_sort_v2(list, size, pivot + 1, pivot + 1, size - 1);//break up list to a smaller R sublist to be sorted
}

int main()
{
   int quickList[] = {100,20,3009,4};
   int qSize = sizeof(quickList)/sizeof(int);
   int pivot = 0;
   int lo = 0;
   int hi = qSize - 1;
	
  r_quick_sort_v2(&quickList[0], qSize, pivot, lo, hi);
  print_list(&quickList[0], qSize);

 return 0;
}

[o1vk4iN6]

if ( hi != pivot )//to prevent redundant moving pivot in place when it's already in place 

it'll probably be faster to allow one redundant move than continually forcing the cpu to decode the potentially wrong batch of code.

[4ET0pfjN]

My mistake, here is the correct tracing diagram:
http://i49.tinypic.com/726gpf.png

[4ET0pfjN]

I finally solved it myself...thanks me