Non Recursive Quicksort..

This is a discussion on Non Recursive Quicksort.. within the C++ Programming forums, part of the General Programming Boards category; Anyone have a Non Recursive Quicksort using stacks that can show, or anywhere I can get the code for one?...

  1. #1
    Unregistered
    Guest

    Post Non Recursive Quicksort..

    Anyone have a Non Recursive Quicksort using stacks that can show, or anywhere I can get the code for one?

  2. #2
    Unregistered
    Guest

    Unhappy help

    Found this code but it doesn't seem to work anyone know why?
    ------------------------------------------------------------------------------------
    //NON RECURSIVE QUICKSORT//

    //Libraries
    #include<iostream.h>
    #include<conio.h>
    #include<stdlib.h>


    //Global Definitions
    const int depthofstack = 20;
    struct stackelement{
    int low;
    int high;
    };
    typedef stackelement slisttype[depthofstack];
    struct stacktype{
    unsigned int top;
    slisttype Slist;
    };
    stacktype Stack;

    //Functions
    void QuickSortNon(listtypeA,int N);
    void initializeStack(stacktype& stack);
    void Push(stacktype& stack,int lowtemp,int highttemp,int& OK) ;
    void Pop(stacktype& stack,stackelementtype& selement, int& OK);
    void isStackFull(stacktype stack);
    void isStackEmpty(stacktype stack);


    //Main Program
    int main()
    {
    int list[20]={17 3 5 22 11 88 99 101 222 33
    4 2 7 12 53 66 33 25 299 101};
    for(int i;i<20;i++)
    {
    cout list[i];
    i++;
    }
    QuickSortNon(list,20)
    for(int i;i<20;i++)
    {
    cout list[i];
    i++;
    }


    int wait;
    cin >> wait;
    return 0;
    }

    void QuickSortNon(listtypeA,int N);
    {
    stackelementtype selement;
    int s,i,j,left,right;
    datatype mid,temp;
    int OKPUSH,OKPOP;
    stacktype stackA;

    initializeStack(stackA);

    Push(stackA,0,N-1,OKPUSH);
    do
    {
    Pop(stackA,selement,OKPOP);
    left=selement.low;
    right=selement.high;
    if(OKPOP)
    {
    do
    {
    i=left;
    j=right;
    mid=A[(left+right)/2];

    do
    {
    while(A[i]<mid)
    i++;
    while(mid<A[j])
    j--;
    if(i<=j
    {
    temp=A[i];
    A[i]=A[j];
    A[j]=temp;
    i++;
    j--;
    };
    }while(i<=j);

    if(i<right)
    right=j;
    }while(left<right);
    }while(OKPOP);
    return;
    }


    void Push(stacktype& stack,int lowtemp,int highttemp,int& OK)
    {
    stackelementtype tempelement;
    unsigned int toptemp;
    if(isStackFull(stack))
    OK=0
    else
    {
    OK=1;
    stack.top=stack.top-1;
    toptemp=stack.top;
    tempelement.low=lowtemp;
    tempelement.high=hightemp;
    stack.Slist[toptemp]=tempelement;
    }
    return;

    void Pop(stacktype& stack,stackelementtype& selement, int& OK)
    {
    if(isStackEmpty(stack));
    OK=0;
    else
    {
    OK=1;
    selement=stack.Slist[stack.top];
    stack.top=stack.top+1;
    };
    return
    };

    void isStackFull(stacktype stack)
    {
    if(stack.top==0)
    return 1;
    else
    return 0;
    };

    void isStackEmpty(stacktype stack);
    {
    if(stack.top==depthofstack)
    return 1;
    else
    return 0;
    };

  3. #3
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >Anyone have a Non Recursive Quicksort using stacks that can show
    Here's the quicksort part of the algorithm, I didn't bother putting in the stack functions since you can find those anywhere.
    Code:
    #define push2(A, B) push(B); push(A);
    
    void quickSort( Item a[], int l, int r )
    {
      int i;
      stackInit();
      push2( l, r );
      while( !stackempty() ) {
        l = pop();
        r = pop();
        if( r <= l )
          continue;
        i = partition( a, l, r );
        if( i - l > r - i ) {
          push2( l, i - 1 );
          push2( i + 1, r );
        }
        else {
          push2( i + 1, r );
          push2( l, i - 1 );
        }
      }
    }
    
    int partition( Item a[], int l, int r )
    {
      int i = l - 1,
          j = r;
      Item v = a[r];
      for( ; ; )
      {
        while( less( a[++i], v ) )
          ;
        while( less( v, a[--j] ) )
          if( j == l )
            break;
        exch( a[i], a[r] );
      }
      exch( a[i], a[r] );
      return i;
    }
    -Prelude
    My best code is written with the delete key.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Scalability problems with Quicksort
    By hbejkosa in forum C++ Programming
    Replies: 3
    Last Post: 12-26-2008, 11:26 PM
  2. recursive function
    By technosavvy in forum C Programming
    Replies: 1
    Last Post: 02-29-2008, 05:42 AM
  3. difference between recursive and iterative
    By Micko in forum C Programming
    Replies: 33
    Last Post: 07-06-2004, 10:34 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  5. How to change recursive loop to non recursive loop
    By ooosawaddee3 in forum C Programming
    Replies: 1
    Last Post: 06-24-2002, 09:15 AM

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