Я нашел этот вопрос в Интернете.
Учитывая стек S, напишите программу C для сортировки стека (по возрастанию заказ). Нам не позволяют делать какие-либо предположения о том, как реализован стек. Единственными функциями, которые необходимо использовать, являются:
Push
Pop
Top
IsEmpty
IsFull
Я думаю, мы можем построить кучу и отсортировать ее. Какое оптимальное решение для этого?
Предполагая, что единственной структурой данных, разрешенной здесь, является Stack, тогда вы можете использовать 2 стека.
Итерация до тех пор, пока исходный стек не станет пустым, и на каждой итерации поместите элемент из исходного стека, в то время как верхний элемент во втором стеке больше, чем удаленный элемент, вытащите второй стек и вставьте его в исходный стек. Теперь вы можете нажать элемент, который вы первоначально выскочили из исходного стека во второй стек.
Временная сложность этого подхода O (N ^ 2).
C-код для реализации этого алгоритма будет (извините мои ржавые навыки C):
void SortStack(struct Stack * orig_stack)
{
struct Stack helper_stack;
while (!IsEmpty(orig_stack))
{
int element = Pop(orig_stack);
while (!IsEmpty(&helper_stack) && Top(&helper_stack) < element)
{
Push(orig_stack, Pop(&helper_stack));
}
Push(&helper_stack, element);
}
while (!IsEmpty(&helper_stack))
{
Push(orig_stack, Pop(&helper_stack));
}
}
С учетом этих операций стека вы можете написать рекурсивную сортировку вставки.
void sort(stack s) {
if (!IsEmpty(s)) {
int x = Pop(s);
sort(s);
insert(s, x);
}
}
void insert(stack s, int x) {
if (!IsEmpty(s)) {
int y = Top(s);
if (x < y) {
Pop(s);
insert(s, x);
Push(s, y);
} else {
Push(s, x);
}
} else {
Push(s, x);
}
}
Это можно сделать рекурсивно, используя один и тот же стек. O (N ^ 2) Я закодировал его на С++, но преобразование в C тривиально. Мне просто нравятся шаблоны, и вы отметили свой вопрос как С++
template<typename T>
void Insert(const T& element, Stack<T>& stack)
{
if(element > stack.Top())
{
T top = stack.Pop();
Insert(element, stack);
stack.Push(top);
}
else
{
stack.Push(element);
}
}
template<typename T>
void StackSort(Stack<T>& stack)
{
if(!stack.IsEmpty())
{
T top = stack.Pop();
StackSort(stack);
Insert(top, stack);
}
}
Отредактировано, чтобы вернуть мой голос!:))
Сорт блин - еще один интересный способ сделать это: http://en.wikipedia.org/wiki/Pancake_sorting#cite_note-4.
Это должен быть самый быстрый способ реализовать сортировку из трех стеков. Цель состоит в том, чтобы получить последовательность по возрастанию, поскольку элементы извлекаются из отсортированного стека.
Статья вики для многофазной сортировки слиянием (с использованием массивов):
http://en.wikipedia.org/wiki/Polyphase_merge_sort
Пример кода C++ для трехфазной сортировки стека с использованием указателей, указателя в качестве указателя стека для каждого стека и указателя на конец каждого прогона и конец каждого стека. Указатель размера серии используется для отслеживания того, когда размер серии увеличивается или уменьшается в середине стека. Флаг нисходящей последовательности используется для отслеживания, являются ли последовательности нисходящими или восходящими при передаче данных между стеками. Он инициализируется в начале, а затем чередуется после объединения каждой пары прогонов.
typedef unsigned int uint32_t;
static size_t fibtbl[48] =
{ 0, 1, 1, 2, 3, 5,
8, 13, 21, 34, 55, 89,
144, 233, 377, 610, 987, 1597,
2584, 4181, 6765, 10946, 17711, 28657,
46368, 75025, 121393, 196418, 317811, 514229,
832040, 1346269, 2178309, 3524578, 5702887, 9227465,
14930352, 24157817, 39088169, 63245986, 102334155, 165580141,
267914296, 433494437, 701408733,1134903170,1836311903,2971215073};
// binary search: return index of largest fib() <= n
size_t flfib(size_t n)
{
size_t lo = 0;
size_t hi = sizeof(fibtbl)/sizeof(fibtbl[0]);
while((hi - lo) > 1){
size_t i = (lo + hi)/2;
if(n < fibtbl[i]){
hi = i;
continue;
}
if(n > fibtbl[i]){
lo = i;
continue;
}
return i;
}
return lo;
}
// poly phase merge sort array using 3 arrays as stacks, a is source
uint32_t * ppmrg3s(uint32_t a[], uint32_t b[], uint32_t c[], size_t n)
{
if(n < 2)
return a+n;
uint32_t *asp = a; // a stack ptr
uint32_t *aer; // a end run
uint32_t *aes = a + n; // a end
uint32_t *bsp = b + n; // b stack ptr
uint32_t *ber; // b end run
uint32_t *bes = b + n; // b end
uint32_t *csp = c + n; // c stack ptr
uint32_t *ces = c + n; // c end
uint32_t *rsp = 0; // run size change stack ptr
size_t ars = 1; // run sizes
size_t brs = 1;
size_t scv = 0-1; // size change increment / decrement
bool dsf; // == 1 if descending sequence
{ // block for local variable scope
size_t f = flfib(n); // fibtbl[f+1] > n >= fibtbl[f]
dsf = ((f%3) == 0); // init compare flag
if(fibtbl[f] == n){ // if exact fibonacci size, move to b
for(size_t i = 0; i < fibtbl[f-1]; i++)
*(--bsp) = *(asp++);
} else { // else move to b, c
// update compare flag
dsf ^= (n - fibtbl[f]) & 1;
// move excess elements to b
aer = a + n - fibtbl[f];
while (asp < aer)
*(--bsp) = *(asp++);
// move dummy count elements to c
aer = a + fibtbl[f - 1];
while (asp < aer)
*(--csp) = *(asp++);
rsp = csp; // set run size change ptr
}
} // end local variable block
while(1){ // setup to merge pair of runs
if(asp == rsp){ // check for size count change
ars += scv; // (due to dummy run size == 0)
scv = 0-scv;
rsp = csp;
}
if(bsp == rsp){
brs += scv;
scv = 0-scv;
rsp = csp;
}
aer = asp + ars; // init end run ptrs
ber = bsp + brs;
while(1){ // merging pair of runs
if(dsf ^ (*asp <= *bsp)){ // if a <= b
*(--csp) = *(asp++); // move a to c
if(asp != aer) // if not end a run
continue; // continue back to compare
do // else move rest of b run to c
*(--csp) = *(bsp++);
while (bsp < ber);
break; // and break
} else { // else a > b
*(--csp) = *(bsp++); // move b to c
if(bsp != ber) // if not end b run
continue; // continue back to compare
do // else move rest of a run to c
*(--csp) = *(asp++);
while (asp < aer);
break; // and break
}
} // end merging pair of runs
dsf ^= 1; // toggle compare flag
if(bsp == bes){ // if b empty
if(asp == aes) // if a empty, done
break;
std::swap(bsp, csp); // swap b, c
std::swap(bes, ces);
brs += ars; // update run size
} else { // else b not empty
if(asp != aes) // if a not empty
continue; // continue back to setup next merge
std::swap(asp, csp); // swap a, c
std::swap(aes, ces);
ars += brs; // update run size
}
}
return csp; // return ptr to sorted array
}
Пример кода Java для сортировки с использованием пользовательского стекового класса (xstack), который включает функцию подкачки.
static final int[] FIBTBL =
{ 0, 1, 1, 2, 3, 5,
8, 13, 21, 34, 55, 89,
144, 233, 377, 610, 987, 1597,
2584, 4181, 6765, 10946, 17711, 28657,
46368, 75025, 121393, 196418, 317811, 514229,
832040, 1346269, 2178309, 3524578, 5702887, 9227465,
14930352, 24157817, 39088169, 63245986, 102334155, 165580141,
267914296, 433494437, 701408733,1134903170,1836311903};
// return index of largest fib() <= n
static int flfib(int n)
{
int lo = 0;
int hi = 47;
while((hi - lo) > 1){
int i = (lo + hi)/2;
if(n < FIBTBL[i]){
hi = i;
continue;
}
if(n > FIBTBL[i]){
lo = i;
continue;
}
return i;
}
return lo;
}
// poly phase merge sort using 3 stacks
static void ppmrg3s(xstack a, xstack b, xstack c)
{
if(a.size() < 2)
return;
int ars = 1; // init run sizes
int brs = 1;
int asc = 0; // no size change
int bsc = 0;
int csc = 0;
int scv = 0-1; // size change value
boolean dsf; // == 1 if descending sequence
{ // block for local variable scope
int f = flfib(a.size()); // FIBTBL[f+1] > size >= FIBTBL[f]
dsf = ((f%3) == 0); // init compare flag
if(FIBTBL[f] == a.size()){ // if exact fibonacci size,
for (int i = 0; i < FIBTBL[f - 1]; i++) { // move to b
b.push(a.pop());
}
} else { // else move to b, c
// update compare flag
dsf ^= 1 == ((a.size() - FIBTBL[f]) & 1);
// i = excess run count
int i = a.size() - FIBTBL[f];
// j = dummy run count
int j = FIBTBL[f + 1] - a.size();
// move excess elements to b
do{
b.push(a.pop());
}while(0 != --i);
// move dummy count elements to c
do{
c.push(a.pop());
}while(0 != --j);
csc = c.size();
}
} // end block
while(true){ // setup to merge pair of runs
if(asc == a.size()){ // check for size count change
ars += scv; // (due to dummy run size == 0)
scv = 0-scv;
asc = 0;
csc = c.size();
}
if(bsc == b.size()){
brs += scv;
scv = 0-scv;
bsc = 0;
csc = c.size();
}
int arc = ars; // init run counters
int brc = brs;
while(true){ // merging pair of runs
if(dsf ^ (a.peek() <= b.peek())){
c.push(a.pop()); // move a to c
if(--arc != 0) // if not end a
continue; // continue back to compare
do{ // else move rest of b run to c
c.push(b.pop());
}while(0 != --brc);
break; // and break
} else {
c.push(b.pop()); // move b to c
if(0 != --brc) // if not end b
continue; // continue back to compare
do{ // else move rest of a run to c
c.push(a.pop());
}while(0 != --arc);
break; // and break
}
} // end merging pair of runs
dsf ^= true; // toggle compare flag
if(b.empty()){ // if end b
if(a.empty()) // if end a, done
break;
b.swap(c); // swap b, c
brs += ars;
if (0 == asc)
bsc = csc;
} else { // else not end b
if(!a.empty()) // if not end a
continue; // continue back to setup next merge
a.swap(c); // swap a, c
ars += brs;
if (0 == bsc)
asc = csc;
}
}
a.swap(c); // return sorted stack in a
}
Измененный код из Ответ T33C
(перед тем, как Сванте исправил языковой тег от С++ до c): stack.top() можно проверить только, если !stack.empty()
void insert(int element, stack<int> &stack) {
if (!stack.empty() && element > stack.top()) {
int top = stack.top();
stack.pop();
insert(element, stack);
stack.push(top);
}
else {
stack.push(element);
}
}
void sortStack(stack<int> & stack) {
if (!stack.empty()) {
int top = stack.top();
stack.pop();
sortStack(stack);
insert(top, stack);
}
}
Если у вас нет дополнительной информации о содержимом стека, вы в значительной степени застреваете, просто беря все данные, сортируя их и снова вставляя обратно. Heapsort будет здесь великолепно, как бы быстрая сортировка или интропорт.
Если нет ограничений на использование других структур данных, я бы сказал, что минимальная куча. при каждом появлении элемента из стека, помещенного в кучу. Когда выскакивание выполняется, беря элемент из вершины кучи (минимум остального) и вставляя его в стек. Повторение такого процесса до тех пор, пока куча не станет пустой.
Для создания кучи среднее время равно O (nlogn); для удаления элементов из кучи и возврата элементов в порядке возрастания среднее время равно O (nlogn).
Как это выглядит?
Обратите внимание, что ответ Майкл Дж. Барбер (см. выше) неверен, что заставляет его возвращать в стек, когда он пуст. Правильная версия выглядит следующим образом:
void sort(stack s) {
if (!IsEmpty(s)) {
int x = Pop(s);
sort(s);
insert(s, x);
}
}
void insert(stack s, int x) {
if (!IsEmpty(s)) {
int y = Top(s);
if (x < y) {
Pop(s);
insert(s, x);
Push(s, y);
} else {
Push(s, x);
}
} else {
Push(s, x); // !!! must step, otherwise, the stack will eventually be empty after sorting !!!
}
}
Вот решение в Javascript, основанное на ответе @OrenD
var org = [4,67,2,9,5,11,3];
var helper = [];
while(org.length > 0){
var temp = org.pop();
while((helper.length > 0) && (helper[helper.length-1] < temp)){
org.push(helper.pop());
}
helper.push(temp);
}
while(helper.length > 0){
org.push(helper.pop());
}
/* the basic idea is we go on
* popping one element (o) from the original stack (s) and we
* compare it with the new stack (temp)
* if o (the popped element from original stack)
* is < the peek element from new stack temp
* then we push the new stack element to original stack
* and recursively keep calling till temp is not empty
* and then push the element at the right place.
* else we push the element to the new stack temp
* (o >= new temp stack.
*
* Entire logic is recursive.
*/
public void sortstk( Stack s )
{
Stack<Integer> temp = new Stack<Integer>();
while( !s.isEmpty() )
{
int s1 = (int) s.pop();
while( !temp.isEmpty() && (temp.peek() > s1) )
{
s.push( temp.pop() );
}
temp.push( s1 );
}
// Print the entire sorted stack from temp stack
for( int i = 0; i < temp.size(); i++ )
{
System.out.println( temp.elementAt( i ) );
}
}
С тремя стеками S (исходный стек, стек с несортированными элементами), A, B вы можете начать игру, похожую на сортировку слияния.
Я думаю, что ясно, что если вы заказали элементы на A и B (в том же направлении, как по восходящему, так и по нисходящему), вы можете использовать S для объединения сортировки A и B, а затем переместить результат на, для пример, B.
Тот факт, что у вас есть некоторые элементы на A, B или S, не мешает вам использовать A, B или S для слияния (если вы используете маркер текущего размера A, B и S, чтобы вы не промахнулись). Если ваша процедура приносит упорядоченные элементы на S, мозг не должен использовать A и B, чтобы удалить отсортированную часть в или B в любом направлении, которое вам нравится: вы можете поместить его в обратном порядке к A или B напрямую или, например, поместите все элементы в и снова переверните на B.
Предположим, что у вас есть 4 отсортированных элемента на A, 16 на B и некоторые несортированные элементы на S.
A.push(S.pop) и теперь создайте 2-элементное сортированное слияние. Снова B.push(S.pop) и создайте еще одно 2-элементное сортированное слияние. Если слияния не разделены и/или не находятся в одном направлении, вы можете манипулировать элементами любым способом, пока не достигнете 4-элементного сортированного слияния на B (или даже S). Теперь объедините начальный 4-элементный сортированный слияние из A и этой части на B, пока вы не достигнете 8-элементного сортированного слияния.
Повторяйте все до тех пор, пока вы не создадите еще одно 8-элементное сортированное слияние. Вы размещаете его в правильном порядке на B (или S) и объединяете, чтобы получить сортировку с 16 элементами. Теперь вы поместите его на A (или S) и объедините с 16-элементным слиянием, которое у нас было на B все время.
Оптимизированная реализация сложна, так как вам нужно уменьшить перемещение (ревертирование) сортированного слияния из одного стека в другой. Однако, если вы исправите и решите, что вы собираетесь использовать A, B и S и, например, принудительно: A, чтобы содержать меньшую и большую объединенную часть в порядке убывания, тогда алгоритм проще.
Тот факт, что вам нужно переместить некоторые верхние элементы из одного стека в другой, добавляет постоянный фактор к сложности, но он никогда не превышает 2. Кроме того, сложность n * log (n) (вы достигаете Сортировка 2n-элементов слиянием путем слияния 2 n-элементов сортированных слияний, а для слияния требуется не более 2-х шагов.)
Реализация на С# (другие похожие языки очевидны)
void Stacking(Stack<int> sourceStack, Stack<int> mainStack, Stack<int> childStack, int n)
{
if (n == 0) return;
if (n == 1)
{
mainStack.Push(sourceStack.Pop());
return;
}
int mainSize = n/2;
int childSize = n - n/2;
Stacking(sourceStack, mainStack, childStack, mainSize);
Stacking(sourceStack, childStack, mainStack, childSize);
while (true)
{
while (mainSize > 0 && mainStack.Peek() >= childStack.Peek())
{
sourceStack.Push(mainStack.Pop());
mainSize--;
}
if (mainSize == 0) break;
while (childSize > 0 && childStack.Peek() >= mainStack.Peek())
{
sourceStack.Push(childStack.Pop());
childSize--;
}
if (childSize == 0) break;
}
while (mainSize > 0)
{
sourceStack.Push(mainStack.Pop());
mainSize--;
}
while (childSize > 0)
{
sourceStack.Push(childStack.Pop());
childSize--;
}
for (int i = 0; i < n; i++)
mainStack.Push(sourceStack.Pop());
}
void SortStack(Stack<int> sourceStack)
{
int n = sourceStack.Count();
// possible optimization: if (n < 2) return;
Stack<int> mainStack = new Stack<int>();
Stack<int> childStack = new Stack<int>();
Stacking(sourceStack, mainStack, childStack, n);
for (int i = 0; i < n; i++)
sourceStack.Push(mainStack.Pop());
}
Вышеупомянутая процедура может быть упрощена, если вам разрешено использовать не более log (n) стеков. Это количество стеков не означает, что вы когда-либо будете использовать дополнительное пространство, большее, чем порядок n. Вы просто отмечаете стеки, которые будут использоваться для слияния элементов 1, 2, 4.... В этом случае вы не заботитесь о порядке, так как слияние частей 2 ^ n всегда будет сортироваться в одном направлении. Однако это решение только обходит тот факт, что вы ограничены использованием push и pop; кроме того, что он эквивалентен сортировке слияния во всех аспектах. В сущности, если количество стеков не ограничено, вы также можете легко эмулировать быструю сортировку.
Я думаю, что сортировка пузырьков может работать в стеке с рекурсией.
void sortStack(stack<int>& st){
bool flag = true;
int n = st.size();
for(int i = 1; i <= n - 1 && flag; i++){
flag = false;
bubbleSortStack(st, flag, i);
}
}
void bubbleSortStack(stack<int>& st, bool& flag, int endSize){
if(st.size() == endSize)
return;
int val = st.top();
st.pop();
if(val > st.top()){
flag = true;
int tmp = st.top();
st.push(val);
val = tmp;
}
bubbleSortStack(st, flag);
st.push(val);
}
class Program
{
static void Main(string[] args)
{
Stack<int> stack = new Stack<int>();
stack.Push(8);
stack.Push(5);
stack.Push(3);
stack.Push(4);
stack.Push(7);
stack.Push(9);
stack.Push(5);
stack.Push(6);
Stack<int> tempStack = new Stack<int>();
while (stack.Count > 0)
{
int temp = stack.Pop();
while(tempStack.Count>0 && tempStack.Peek() > temp)
{
stack.Push(tempStack.Pop());
}
tempStack.Push(temp);
}
while (tempStack.Count > 0)
{
Console.Write(tempStack.Pop() + " ");
}
Console.ReadLine();
}
}