nonrecursive quick sort

[Micko]

Hello, I'm implementing different sort algorithms as an excercise. However, I'm not sure how to implement quick sort algorithm.
Here's recursive implementation:

void quick_sort(int* array,int l,int r)
 {
	 int j;
	 if(r<=l) return;
	 j=partition(array,l,r);
	 quick_sort(array,l,j-1);
	 quick_sort(array,j+1,r);
 }

 int partition(int* array, int l, int r)
 {
	 int pivot,i,j;

	 pivot=array[l];
	 i=l+1;
	 j=r;

	 for(;;)
	 {
		 while((array[i] <= pivot) && (i <= r))i++;
		 while((array[j] > pivot) && (j > l))j--;
		
		 if(i < j)
			 swap_in_array(array,i,j);
		 else 
			 break;
	 }
	 swap_in_array(array,j,l);

 }

 void swap_in_array(int* array, int i, int j)
 {
	 int tmp;
	 tmp=array[i];
	 array[i]=array[j];
	 array[j]=tmp;
 }

How to implement nonrecursive quick sort. I know I'll need stack,
and I manage to implement stack using single linked list.
Asssuming prototipes are:
void push(Stack* stack,int);
int pop(Stack*);
how code for quic sort would look like?
I don't need implamentation for stack, I've done that, but I need implementation for nonrecursive quick_sort.
I've searched the board, but found nothing to help me.
I hope you'll help me.
Thanks very much!

[itsme86]

You can implement a quicksort using a bubble sort, really. The C standard doesn't specify what the sorting method is, just that the function exists and actually sorts the data like it's supposed to. So I'm not sure what your question is.

[Thantos]

itsme86 quicksort is a type of sorting. qsort() is a function that can use any sort method. The two are differenet.

[itsme86]

Ahh...well er...*cough*. Here you go then: http://linux.wku.edu/~lamonml/algor/sort/quick.html


Sorry about that.

[Micko]

All I found is this:
http://cboard.cprogramming.com/showt...sive+quicksort
and that is C++ implementation but aside that it didn't help me much. If someone has an idea or sample code, it would be very valueable for me

[Micko]

Ahh...well er...*cough*. Here you go then: http://linux.wku.edu/~lamonml/algor/sort/quick.html


Sorry about that.

The page cannot be displayed in my browser!

[itsme86]

What browser might that be? It works fine in Firefox. I just tested it in IE also.

Get a real browser.

[Prelude]

>How to implement nonrecursive quick sort.
Start by removing the tail recursion. That's just about the easiest way to make quicksort half nonrecursive. Once you get that down you can start playing with stacks. It's best to take the smallest step possible, especially if you aren't very comfortable with the process.

[Micko]

Thanks for replying, but it's rather late here and I'm pretty tired to play with this step by step. Maybe function median3 in example I found on the board is not correct?