

クイックソートをスタックを使って書き直してみたいのですがどこをどうすればよいのかよくわからないです

[code]

    using System;
    using System.Collections;
    
    class Queue_int :IEnumerable {  
                            
        int[] data;     
        int max;        
        int front, back, count;
    
        public Queue_int(int n) {  
            data = new int[n];  
            max = n;            
            front = back = count = 0;   
        }
        
        public bool Enqueue(int n) {
            if (count==max) return false;   
            data[back] = n;
            back = (back+1)%max;
            count += 1;
            return true;    
        }
        
        public int Dequeue() {
            int  temp = front;
            front = (front+1)%max; 
            count -= 1;
            return data[temp];  
        }
        
        
        public int Front() {
            return data[front];
        }
    
        public bool isEmpty() {
            return (count==0);
        }
        
        public bool isFull() {
            return (count==max);
        }
    
        int Count() {
            return count;
        }
        
        public IEnumerator GetEnumerator() {
            
            int i=front;
            for ( int j=0; j<count; j++ ) {
                yield return data[i];
                i = (i+1)%max;
            }
        }
    
        public void List() {
            foreach (int k 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_int rangeq = 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, -10, -4, 9, 3, 0, 12, 0, 2, 100,-100,2};
            
            quickSort(s);
            for (int k=0; k<s.Length; k++) {
                Console.Write("{0} ", s[k]);
            }
            Console.WriteLine();
            return;
        }
        
        static void Main() {
            (new QuickSortQueue()).inOut();
        }   
    }
    
[/code]


CC BY-SA 4.0
2020-06-29T12:29:41.090
68115
2022-06-23T11:03:25.407
2020-06-29T12:33:38.810
3060
40863
question
c# sort
クイックソートをスタックを使って書き直す


> どこをどうすればよいのかよくわからないです

まず、`QuickSort` を 再帰を使ってちゃんと実装します。  
次に、末尾再帰はループを使って書き換え可能 なので `QuickSort` を再帰呼び出していてる場所  
の パラメータに設定する値を `Enqueue` して  
関数パラメータから値を取得する部分を `Dequeue` します。  
この時 Enqueue と `Dequeue` の順番を間違えないように。  
クラスを使って `first` と `last` の値をセットで `Enqueue` `Dequeue` すると読みやすいと思います。

少なくとも 質問のコードでは `Enqueue` と `Dequeue` で 格納する値と 取り出す変数の順番が逆になっているように見えます。

### 詳細を追記

時間が無くてちゃんと解析できていませんでしたが、質問のプログラムは `Queue` を使った  
クリックソートを正しく実装していたんですね。  
`Queue` を `Stack` にする場合は どうしたらいいか？ という質問だったんですね。

その場合は答えは簡単で `first` 変数と `last` 変数を Stack から取り出す順番を  
変えるだけで動作します。

Queue は 入れた順番に取り出し Stack は 最後に入れたものから取り出しますから・・

[code]

    using System.Collections.Generic;
    
        class IntStack : Stack<int>
        {
            public void List()
            {
                foreach (int k in this)
                    Console.Write("{0} ", k);
                Console.WriteLine();
            }
            public bool isEmpty()
            {
                return this.Count == 0;
            }
            public void Enqueue(int n)
            {
                Push(n);
            }
    
            public int Dequeue()
            {
                return Pop();
            }
        }
    
[/code]

とやると 下記のような最小限の修正で Stack を使って動作します

[code]

        var rangeq = new IntStack();
    
        last = rangeq.Dequeue();
        first = rangeq.Dequeue();
    
    
[/code]

もしかして Queue が独自実装だったので Stack も 独自で実装する予定だったのですか？

### 参考情報

[Javaで実装した QuickSort
の詳しい解説](http://www.ics.kagoshima-u.ac.jp/%7Efuchida/edu/algorithm/sort-
algorithm/quick-sort.html)  
[C++ で実装。 再帰しない QuickSort の例。性能についての解説。](https://programming-
place.net/ppp/contents/algorithm/sort/006.html)


CC BY-SA 4.0
2020-06-29T23:43:08.887
68125
2020-07-01T03:24:40.130
2020-07-01T03:24:40.130
18851
18851
68115
answer