nonrecursive quick sort

This is a discussion on nonrecursive quick sort within the C Programming forums, part of the General Programming Boards category; Hello, I'm implementing different sort algorithms as an excercise. However, I'm not sure how to implement quick sort algorithm. Here's ...

  1. #1
    Registered User Micko's Avatar
    Join Date
    Nov 2003
    Posts
    712

    nonrecursive quick sort

    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:
    Code:
    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!

  2. #2
    Gawking at stupidity
    Join Date
    Jul 2004
    Location
    Oregon, USA
    Posts
    3,167
    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.
    If you understand what you're doing, you're not learning anything.

  3. #3
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    itsme86 quicksort is a type of sorting. qsort() is a function that can use any sort method. The two are differenet.

  4. #4
    Gawking at stupidity
    Join Date
    Jul 2004
    Location
    Oregon, USA
    Posts
    3,167
    Ahh...well er...*cough*. Here you go then: http://linux.wku.edu/~lamonml/algor/sort/quick.html


    Sorry about that.
    If you understand what you're doing, you're not learning anything.

  5. #5
    Registered User Micko's Avatar
    Join Date
    Nov 2003
    Posts
    712
    All I found is this:
    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

  6. #6
    Registered User Micko's Avatar
    Join Date
    Nov 2003
    Posts
    712
    Quote Originally Posted by itsme86
    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!

  7. #7
    Gawking at stupidity
    Join Date
    Jul 2004
    Location
    Oregon, USA
    Posts
    3,167
    What browser might that be? It works fine in Firefox. I just tested it in IE also.

    Get a real browser.
    Last edited by itsme86; 12-29-2004 at 04:55 PM.
    If you understand what you're doing, you're not learning anything.

  8. #8
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >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.
    My best code is written with the delete key.

  9. #9
    Registered User Micko's Avatar
    Join Date
    Nov 2003
    Posts
    712
    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?

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. recursive quick sort - stack overflow
    By Micko in forum C Programming
    Replies: 9
    Last Post: 01-01-2005, 04:51 PM
  2. nonrecursive quick sort
    By Micko in forum C++ Programming
    Replies: 2
    Last Post: 12-30-2004, 11:05 AM
  3. Help On A Quick Sort Program
    By nick4 in forum C++ Programming
    Replies: 11
    Last Post: 12-06-2004, 09:51 AM
  4. Questions on basic Quick Sort
    By Weng in forum C++ Programming
    Replies: 4
    Last Post: 12-16-2003, 09:06 AM
  5. Shell Sort vs Heap Sort vs Quick Sort
    By mackol in forum C Programming
    Replies: 6
    Last Post: 11-22-2002, 07:05 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21