rewrite the quick sort using the stack

I'd like to rewrite the quick sort using the stack, but I'm not sure where and how to do it

using System;
using System.Collections;

classQueue_int:IEnumerable {  
                        
    int[]data;     
    int max;        
    int front, back, count;

    publicQueue_int(intn){  
        data = new int [n];  
        max = n;            
        front=back=count=0;   
    }
    
    publicboolEnqueue(intn){
        if(count==max)return false;   
        data [back] = n;
        back=(back+1)%max;
        count+=1;
        return true;    
    }
    
    public int Request() {
        int temp = front;
        front=(front+1)%max; 
        count-=1;
        return data [temp];  
    }
    
    
    public int Front() {
        return data [front];
    }

    public pool isEmpty(){
        return(count==0);
    }
    
    public pool isFull() {
        return(count==max);
    }

    int Count() {
        return count;
    }
    
    public IEnumerator GetEnumerator() {
        
        inti = front;
        for(int j=0;j<count;j++){
            yield return data [i];
            i=(i+1)%max;
        }
    }

    public void List() {
        foreach (int in this)
            Console.Write("{0}",k);
        Console.WriteLine();
    }
};

class QuickSortQueue
{
    public void quickSort(int[] s) {
        int N = s. Length;
        int first, last, pivot, i, j, temp;
        Queue_interrangeq = new Queue_int(100);

        rangeq.Enqueue(0);
        rangeq.Enqueue (N-1);
        
        while(!rangeq.isEmpty(){
            rangeq.List();
            first = rangeq.Dequeue();
            last = rangeq.Dequeue();
            if(first<last){
                pivot=s[last];
                i = first;
                j = last-1;
                while(true){
                    while((i<last)&(s[i]<pivot))i+=1;
                    while((j>=first)&(s[j]>pivot)j-=1;
                    if(i>=j)break;
                    temp=s[i]; s[i]=s[j]; s[j]=temp;
                    i+=1;
                    j - = 1;
                }
                temp=s[i]; s[i]=s[last]; s[last]=temp;
                rangeq.Enqueue(first); rangeq.Enqueue(i-1);
                rangeq.Enqueue(i+1); rangeq.Enqueue(last);
            }
        }
    }

    public void inOut(){
        int[]s = {4,5,2,8,7,10,8,1,-1,10,-4,9,3,0,12,0,2,100,-100,2};
        
        quickSort(s);
        for (intk=0;k<s.Length;k++) {
            Console.Write("{0}", s[k]);
        }
        Console.WriteLine();
        return;
    }
    
    static void Main() {
        (new QuickSortQueue()) .inOut();
    }   
}

c# sort

2022-09-29 21:48

1 Answers

I don't know where and what to do

First, implement QuickSort properly using recursion.
Next, where QuickSort is recursively called because the end recursive can be rewritten using a loop
Enqueue to set the value for the parameters in
Dequeue where you want to retrieve values from function parameters.
Do not mistake the order of Enqueue and Dequeue.
Using the class to set the values first and last should be easy to read.

At least the code in the question appears to have the opposite order of the values stored in Enqueue and Dequeue and the variables retrieved.

Add Details

I couldn't analyze it properly because I didn't have time, but I used Queue for the question program. You implemented click sorting correctly.
What should I do if Queue is set to Stack? That's the question.

In that case, the answer is simple: first and last variables are taken out of the stack. Just change it and it works.

I'll take out the Queue in the order you put it in, and I'll take out the Stack from the last one...

using System.Collections.General;

    class IntStack: Stack <int >
    {
        public void List()
        {
            foreach (int in this)
                Console.Write("{0}",k);
            Console.WriteLine();
        }
        public pool is Empty()
        {
            return this.Count == 0;
        }
        public void enqueue(intn)
        {
            Push(n);
        }

        public int Request()
        {
            return Pop();
        }
    }

Then it works with Stack with the following minimum modifications.

var rangeq=new IntStack();

    last = rangeq.Dequeue();
    first = rangeq.Dequeue();

Since Queue was implemented independently, did you plan to implement Stack independently?

References

Find out more about QuickSort implemented in Java
Implemented with C++. QuickSort example without recursion, performance discussion

2022-09-29 21:48

If you have any answers or tips

Popular Tags

python x 4647

android x 1593

java x 1494

javascript x 1427

c x 927

c++ x 878

ruby-on-rails x 696

php x 692

python3 x 685

html x 656