using System;
using System.Collections.Generic;
using System.Text;
namespace StackSort {
class Program {
static void SortCompareAndPush<T>(Stack<T> stack, ref T item)
where T: IComparable<T> {
if (stack.Count > 0) { // if(!stack.IsEmpty) {
do {
T next_item = stack.Pop();
if (item.CompareTo(next_item) == 1) { // if(item > next_item) {
T temp = item;
item = next_item;
next_item = temp;
}
SortCompareAndPush<T>(stack, ref next_item);
} while (item.CompareTo(stack.Peek()) == 1); // } while(item > stack.Top);
}
stack.Push(item);
}
static void SortStack<T>(Stack<T> stack)
where T : IComparable<T> {
if (stack.Count > 1) { // if(!stack.IsEmpty) {
T item = stack.Pop();
SortCompareAndPush<T>(stack, ref item);
}
}
static void PrintStack<T>(Stack<T> stack) {
foreach (T item in stack) {
Console.WriteLine(item);
}
}
static void Main(string[] args) {
Stack<int> stack = new Stack<int>();
Random rnd = new Random();
for (int i = 0; i < 20; ++i)
stack.Push(rnd.Next(100));
Console.WriteLine("Initial stack:");
PrintStack<int>(stack);
SortStack<int>(stack);
Console.WriteLine("Sorted stack:");
PrintStack<int>(stack);
Console.ReadKey();
}
}
}
Сортировка через стек
есть у кавонить алгоритм быстрой сортировки стека?
P.S. Не используя массивы и другие структуры данных, только стек, первоначальные данные вводятся в стек из файла.
P.S. Не используя массивы и другие структуры данных, только стек, первоначальные данные вводятся в стек из файла.
ну у Кнута должен быть
Цитата: Mendler
P.S. Не используя массивы и другие структуры данных, только стек, первоначальные данные вводятся в стек из файла.
Без использования дополнительных структур данных - невозможно.
Подозреваю, что нужно использовать "аппаратный" стек вызовов?
Необходимо использовать только команды Push, Pop, Top, IsEmpty :)
Цитата: Mendler
Необходимо использовать только команды Push, Pop, Top, IsEmpty :)
Хорошая задача.
Если хватит соображалки, то с C# переведете:
Код:
Модификатор ref перед параметрами означает передачу аргумента по ссылке. Аналог & в C/C++ и var в Pascal.
З.Ы. Временная сложность сортировки в худшем случае O(n ^ 2).
А теперь вся фишка...)) нужно сделать тоже тока для 50000 элементов...переполнение возникает:\Подскажи,плиз, как обойти?
Цитата: Lenujkee
А теперь вся фишка...)) нужно сделать тоже тока для 50000 элементов...переполнение возникает:\Подскажи,плиз, как обойти?
Купить квантовый компьютер. :D
Если вам ничего не говорит временная сложность алгоритма O(n ^ 2), где n = 50000, то вам прямая дорога идти учить матчасть.
Кроме того, глубина рекурсии будет равна количеству элементов в стеке. Секем? А это 50 000 вызовов. В CLR с дефолтным стеком такая рекурсия вызовет переполнение стека.
Код на C++
Все уже написано до нас :)
массив<int> из 10000 сортировал 2 сек.
Все уже написано до нас :)
Код:
#include "stdafx.h"
#include <stack>
#include <algorithm>
void main(){
stack<int> st;
//Заполнить стэк
sort(st.c.begin(),st.c.end());//Сортировка
};
#include <stack>
#include <algorithm>
void main(){
stack<int> st;
//Заполнить стэк
sort(st.c.begin(),st.c.end());//Сортировка
};
Цитата: sigmov
Код на C++
Все уже написано до нас :)
Все уже написано до нас :)
Дык, быстрая сортировка. Я тоже мог Array.Sort() вызвать.
Изначально задача была - без использования доп средств - структур данных, алгоритмов и прочего. Только операторы стека и рекурсия.
Цитата:
Купить квантовый компьютер. :D
Если вам ничего не говорит временная сложность алгоритма O(n ^ 2), где n = 50000, то вам прямая дорога идти учить матчасть.
Кроме того, глубина рекурсии будет равна количеству элементов в стеке. Секем? А это 50 000 вызовов. В CLR с дефолтным стеком такая рекурсия вызовет переполнение стека.
Если вам ничего не говорит временная сложность алгоритма O(n ^ 2), где n = 50000, то вам прямая дорога идти учить матчасть.
Кроме того, глубина рекурсии будет равна количеству элементов в стеке. Секем? А это 50 000 вызовов. В CLR с дефолтным стеком такая рекурсия вызовет переполнение стека.
пошла.. учить мат часть8{
Цитата: hardcase
Дык, быстрая сортировка. Я тоже мог Array.Sort() вызвать.
Изначально задача была - без использования доп средств - структур данных, алгоритмов и прочего. Только операторы стека и рекурсия.
Изначально задача была - без использования доп средств - структур данных, алгоритмов и прочего. Только операторы стека и рекурсия.
Алгоритм - это не массив и не структура данных. Что сказано в первоначальных условиях.
Lenujkee, не торопитесь учить матчасть.
Стек позволяет получить доступ к iму элементу операцией *(st.c.begin()+i).
Реализуйте алгоритм допустим всплытия, используя данное свойство.
Или это тоже против правил?
Цитата: sigmov
Алгоритм - это не массив и не структура данных. Что сказано в первоначальных условиях.
Lenujkee, не торопитесь учить матчасть.
Стек позволяет получить доступ к iму элементу операцией *(st.c.begin()+i).
Реализуйте алгоритм допустим всплытия, используя данное свойство.
Или это тоже против правил?
Lenujkee, не торопитесь учить матчасть.
Стек позволяет получить доступ к iму элементу операцией *(st.c.begin()+i).
Реализуйте алгоритм допустим всплытия, используя данное свойство.
Или это тоже против правил?
Стек в классике - как тому учат в университетах - не позволяет обращаться в i-му элементу, так как стек, формально, не поддерживает оператор индексации.
А как вы думаете, работает мой пример? Это простейший рекурсивный пузырек, протаскивающий каждый элемент на свое место через стек.
Цитата: hardcase
Стек в классике - как тому учат в университетах - не позволяет обращаться в i-му элементу, так как стек, формально, не поддерживает оператор индексации.
А как вы думаете, работает мой пример? Это простейший рекурсивный пузырек, протаскивающий каждый элемент на свое место через стек.
А как вы думаете, работает мой пример? Это простейший рекурсивный пузырек, протаскивающий каждый элемент на свое место через стек.
Согласен с вами. В классике стек именно то, что вы сказали.
Правда сортировать через стек - все равно, что вычерпывать воду из лодки пипеткой, а не ковшом.
Предлагаю свой метод:
Код:
int buf;
stack<int> st1;
stack<int> st2;
stack<int> st_final;
//Заполнить st1//
while(true){
if(st1.empty()&&st2.empty()) break;
buf=st1.top();
st1.pop();
while(!st1.empty()){
st2.push(min(buf,st1.top()));
buf=max(buf,st1.top());
st1.pop();
}
st_final.push(buf);
if(st1.empty()&&st2.empty()) break;
buf=st2.top();
st2.pop();
while(!st2.empty()){
st1.push(min(buf,st2.top()));
buf=max(buf,st2.top());
st2.pop();
}
st_final.push(buf);
};
while(!st_final.empty()){
cout<<st_final.top()<<endl;
st_final.pop();
}
stack<int> st1;
stack<int> st2;
stack<int> st_final;
//Заполнить st1//
while(true){
if(st1.empty()&&st2.empty()) break;
buf=st1.top();
st1.pop();
while(!st1.empty()){
st2.push(min(buf,st1.top()));
buf=max(buf,st1.top());
st1.pop();
}
st_final.push(buf);
if(st1.empty()&&st2.empty()) break;
buf=st2.top();
st2.pop();
while(!st2.empty()){
st1.push(min(buf,st2.top()));
buf=max(buf,st2.top());
st2.pop();
}
st_final.push(buf);
};
while(!st_final.empty()){
cout<<st_final.top()<<endl;
st_final.pop();
}
Цитата: sigmov
Согласен с вами. В классике стек именно то, что вы сказали.
Правда сортировать через стек - все равно, что вычерпывать воду из лодки пипеткой, а не ковшом.
Предлагаю свой метод:
Правда сортировать через стек - все равно, что вычерпывать воду из лодки пипеткой, а не ковшом.
Предлагаю свой метод:
Код:
int buf;
stack<int> st1;
stack<int> st2;
stack<int> st_final;
//Заполнить st1//
while(true){
if(st1.empty()&&st2.empty()) break;
buf=st1.top();
st1.pop();
while(!st1.empty()){
st2.push(min(buf,st1.top()));
buf=max(buf,st1.top());
st1.pop();
}
st_final.push(buf);
if(st1.empty()&&st2.empty()) break;
buf=st2.top();
st2.pop();
while(!st2.empty()){
st1.push(min(buf,st2.top()));
buf=max(buf,st2.top());
st2.pop();
}
st_final.push(buf);
};
while(!st_final.empty()){
cout<<st_final.top()<<endl;
st_final.pop();
}
stack<int> st1;
stack<int> st2;
stack<int> st_final;
//Заполнить st1//
while(true){
if(st1.empty()&&st2.empty()) break;
buf=st1.top();
st1.pop();
while(!st1.empty()){
st2.push(min(buf,st1.top()));
buf=max(buf,st1.top());
st1.pop();
}
st_final.push(buf);
if(st1.empty()&&st2.empty()) break;
buf=st2.top();
st2.pop();
while(!st2.empty()){
st1.push(min(buf,st2.top()));
buf=max(buf,st2.top());
st2.pop();
}
st_final.push(buf);
};
while(!st_final.empty()){
cout<<st_final.top()<<endl;
st_final.pop();
}
Его существенный плюс - на каждом шаге число прогоняемых элементов уменьшается на 1.
По моим подсчетам 50000 будет отсортировано за 4-5 часов.
Вот кстати для 50 000 элементов... в принципе же можно разделить один стек на 10(допустим в первый элементы до 5000 во второй от 5000 до 1000и тд) и каждый упорядочить как писал уважаемый hardcase. Отсюда вопрос тогда...В дев с++ можно обьявить около 9 стеков а в вижуале и того меньше штук 7. Может кто нибудь знает как можно увеличить размер памяти занимаемое программой...или количество стеков??Оо заранее спасибо за ответ
Цитата:
По моим подсчетам 50000 будет отсортировано за 4-5 часов.
мммм беда в том что за секунду надо..Это массив простите?? А если списочные элементы?:DDD
Цитата: Lenujkee
мммм беда в том что за секунду надо..Это массив простите?? А если списочные элементы?:DDD
Сортировать 50 000 элементов менее чем за секунду - это уж простите, нужно квиксортом по массиву утюжить. А не всякие там стеки придумывать.
Цитата:
Сортировать 50 000 элементов менее чем за секунду - это уж простите, нужно квиксортом по массиву утюжить. А не всякие там стеки придумывать.
Ммм, но это ж задали =>выполнимое задание...Тока низнаю как ешо... сейчас таким методом, как у меня выше описано с использованием указателей и 5 стеков перебирает массив за 19 секунд(естественно числа а не списки)...вот еслиб был способ увеличить количество стеков%)
Цитата: Lenujkee
Ммм, но это ж задали =>выполнимое задание...Тока низнаю как ешо... сейчас таким методом, как у меня выше описано с использованием указателей и 5 стеков перебирает массив за 19 секунд(естественно числа а не списки)...вот еслиб был способ увеличить количество стеков%)
Весьма выполнимое, если Oksford'ский Mainframe совместно со Стендсфордским запустить.:D
Цитата:
Весьма выполнимое, если Oksford'ский Mainframe совместно со Стендсфордским запустить.:D
Остроумно, но печально:(
Написал сортировку, чем то похожую на квиксорт:
Две проблемы:
1. Зацикливается на повторных элементах... т.е. надо изменить структуру проверки if( max == 1 ), if( min == 1 ), а вот на какую?
2. 31к элемент сортирует за 0.125 секунды
потом время увеличивается по экспоненте...
к 50к элементам приходим за 31.5 секунды, в чем может выражаться эта зависимость?
Код:
template <typename TElement>
int sort_stack(TStackMass<TElement> *stk, TStackMass<TElement> *stk1, TStackMass<TElement> *stk2, TStackMass<TElement> *fin)
{
TElement tmp;
int min = 0;
int max = 0;
tmp = stk->Top();
while( !stk->IsEmpty() )
{
if( tmp <= stk->Top() )
{
stk1->Push(stk->Pop());
max++;
}
else
{
stk2->Push(stk->Pop());
min++;
}
}
if( max == 1 )
fin->Push(stk1->Pop());
if( max > 1 )
sort_stack(stk1, stk, stk2, fin);
if( min == 1 )
fin->Push(stk2->Pop());
if( min > 1 )
{
while( !stk2->IsEmpty() && min != 0 )
{
stk->Push(stk2->Pop());
min--;
}
sort_stack(stk, stk1, stk2, fin);
}
}
int sort_stack(TStackMass<TElement> *stk, TStackMass<TElement> *stk1, TStackMass<TElement> *stk2, TStackMass<TElement> *fin)
{
TElement tmp;
int min = 0;
int max = 0;
tmp = stk->Top();
while( !stk->IsEmpty() )
{
if( tmp <= stk->Top() )
{
stk1->Push(stk->Pop());
max++;
}
else
{
stk2->Push(stk->Pop());
min++;
}
}
if( max == 1 )
fin->Push(stk1->Pop());
if( max > 1 )
sort_stack(stk1, stk, stk2, fin);
if( min == 1 )
fin->Push(stk2->Pop());
if( min > 1 )
{
while( !stk2->IsEmpty() && min != 0 )
{
stk->Push(stk2->Pop());
min--;
}
sort_stack(stk, stk1, stk2, fin);
}
}
Две проблемы:
1. Зацикливается на повторных элементах... т.е. надо изменить структуру проверки if( max == 1 ), if( min == 1 ), а вот на какую?
2. 31к элемент сортирует за 0.125 секунды
потом время увеличивается по экспоненте...
к 50к элементам приходим за 31.5 секунды, в чем может выражаться эта зависимость?