QuickStack

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
abc

QuickStack

#1

投稿記事 by abc » 4日前

//このクイックソートをスタックを使って書き直す方法がいまいちわかりません
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+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 < pivot) ) i += 1;
while ( (j >= first) && (s[j] > pivot) ) j -= 1;
if (i >= j) break;
temp = s; s = s[j]; s[j] = temp;
i += 1;
j -= 1;
}
temp = s; s = 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();
}
}

“C言語何でも質問掲示板” へ戻る