Форум программистов, компьютерный форум CyberForum.ru

Свой квиксорт с домино и буфетчицами! - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 10, средняя оценка - 4.80
Глупец
23 / 23 / 1
Регистрация: 17.05.2011
Сообщений: 141
18.06.2011, 21:03     Свой квиксорт с домино и буфетчицами! #1
Доброго времени суток!
В общем идея проста: сделать псевдо рекурсивную сортировку разделением, т.е. она будет работать на собственноручно созданом стеке.
Делается это потому что системный вылетает при большом количестве элементов.
Так вот проблема в том, что для 10 элемнов массива(так же для 30) она работает змечательно а вот уже для 40 работает аномально(не вылетает, но и не до конца сортирует), для 60 и дальше соответственно runtime улетает в поднебесье...
В чем косяк, вот код
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include<iostream>
#include<stdio.h> 
#include<stdlib.h> 
#include<time.h>
#include<windows.h>
struct cover{
    int offsetl;
    int offsetr;
    int mid;
    void operator =(cover& param){
        offsetl=param.offsetl;
        offsetr=param.offsetr;
        mid=param.mid;
    }
    cover(){
        offsetl=0;
        offsetr=0;
        mid=0;
    }
    cover(int i1,int i2,int i3){
        offsetl=i1;
        offsetr=i2;
        mid=i3;
    }
    friend std::ostream& operator <<(std::ostream& S,cover& param){
        S<<param.offsetl<<" "<<
            param.mid<<" "<<
            param.offsetr<<std::endl;
        return S;
    }
};
struct estak{
    cover dat;
    estak* next;
    estak(cover& val){
        dat.mid=val.mid;
        dat.offsetl=val.offsetl;
        dat.offsetr=val.offsetr;
        next=NULL;
    }
    ~estak(){;}
};
class stak{
    estak* head;
    int count;
public: 
    stak(){
        head=NULL;count=0;
    }
    void push(cover val){
        estak* tmp=new estak(val);
        tmp->next=head;
        head=tmp;
        count++;
    }
    cover pop(){
        cover tmp=head->dat;
        estak* tmp_p=head;
        head=head->next;
        tmp_p->next=NULL;
        delete tmp_p;
        count--;
        return tmp;
    }
    int good(){return count;}
    ~stak(){;}
};
void sort(char piece[],cover date){
    for(int i=date.offsetl,  j=date.offsetr;i <= j;){
        if (piece[i] < piece[date.mid]) {i++; continue;}
        if (piece[j] >= piece[date.mid]){j--; continue;}
        int c = piece[i];piece[i] = piece[j]; piece[j]=c;
        i++,j--;            
    }
}
int main(){
    long T0=clock();
    stak buf;
    char m_str[]="948372615094837261509483726150948372615094837261509483726150";
    std::cout<<m_str<<std::endl<<strlen(m_str)<<" -len"<<std::endl;
    buf.push(cover(0,strlen(m_str)-1,(strlen(m_str)-1)/2));
    while(buf.good()){
        cover tmp=buf.pop();
        sort(m_str,tmp);
        if(tmp.offsetr-tmp.mid>=2){
            buf.push(cover(tmp.mid,tmp.offsetr,tmp.mid+(tmp.offsetr-tmp.mid)/2));
            buf.push(cover(tmp.offsetl,tmp.mid,tmp.mid/2));
        }
    }
    std::cout<<m_str<<std::endl;
    std::cout<<clock()-T0<<" run_time"<<std::endl;
    return 0;
}
Если кто подскажет буду очень благодарен)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
18.06.2011, 21:03     Свой квиксорт с домино и буфетчицами!
Посмотрите здесь:

Функции, Домино, Как!!? C++
C++ Кости домино
Домино C++
Реализовать точки на костях домино C++
Как создать в оперативной или во внешней памяти некую структуру наподобие домино? C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ValeryS
Модератор
6374 / 4840 / 441
Регистрация: 14.02.2011
Сообщений: 16,040
18.06.2011, 22:53     Свой квиксорт с домино и буфетчицами! #2
Цитата Сообщение от Глупец Посмотреть сообщение
соответственно runtime улетает в поднебесье...
скорее всего что то с выделением памяти
потом обращение к невыделенной и досвидания
пройди под отладчиком
а лучше используй исключения

Добавлено через 9 минут
Цитата Сообщение от Глупец Посмотреть сообщение
tmp_p->next=NULL;
delete tmp_p;
вот это зачем??
обнуляешь поле у элемента который в следуюшей строчке удалишь???
тебе нужно обнулить поле у элемента который указывает на tmp_p
может так
C++
1
tmp_p->next->next=NULL;
извини серьезно в программе не разбирался
слишком сложно ты закрутил с указателями
разберись с ними
для начала задокументируй программу
Jupiter
Каратель
Эксперт C++
6542 / 3962 / 226
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
Завершенные тесты: 2
18.06.2011, 23:20     Свой квиксорт с домино и буфетчицами! #3
Цитата Сообщение от Глупец Посмотреть сообщение
void operator =(cover& param){
offsetl=param.offsetl;
offsetr=param.offsetr;
mid=param.mid;
}
оригинально
Глупец
23 / 23 / 1
Регистрация: 17.05.2011
Сообщений: 141
19.06.2011, 07:35  [ТС]     Свой квиксорт с домино и буфетчицами! #4
Цитата Сообщение от ValeryS Посмотреть сообщение
Добавлено через 9 минут
Сообщение от Глупец
tmp_p->next=NULL;
delete tmp_p;
вот это зачем??
обнуляешь поле у элемента который в следуюшей строчке удалишь???
это за тем, чтоб при удалении не было рекурсии...здесь все норм, т.е. мы занулили указатель на следующий, а потом удалили то, что сняли со стека...

ну, тогда хоть кинь чего-нибудь простого почитать про трай кетчи, а то я ток слышал про них, а как пользоваться не знаю...(
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
19.06.2011, 07:56     Свой квиксорт с домино и буфетчицами! #5
Что подразумевается под "большим массивом"? Скорее всего рекурсия реализована ошибочно.
Вариант с собственноручным стеком даже не смотрел...

Добавлено через 2 минуты
Посмотрел. Метод pop реализован с ошибкой. По идее, падение должно быть при первом же попе.
Глупец
23 / 23 / 1
Регистрация: 17.05.2011
Сообщений: 141
19.06.2011, 08:01  [ТС]     Свой квиксорт с домино и буфетчицами! #6
рекурсии там и нет, как бэ )
код который я кинул и работает на своем стэке.
большой массив-лимонов 10 указателей на строки...

А как по другому реализовать pop, или в чем там косяк?
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
19.06.2011, 08:07     Свой квиксорт с домино и буфетчицами! #7
Цитата Сообщение от Глупец Посмотреть сообщение
рекурсии там и нет, как бэ )
Я про исходный вариант, в котором возникла проблема.

Добавлено через 3 минуты
C++
1
2
3
4
5
6
7
8
9
       cover pop(){
                cover tmp=head->dat;
                estak* tmp_p=head;
   !!!!!!!!!   head=head->next;
                tmp_p->next=NULL;
                delete tmp_p;
                count--;
                return tmp;
        }
При выталкивании нужно указатель на предыдущий ставить, а ты на следующий, которого и нет.
Или я в названиях запуталсо.

Добавлено через 2 минуты
Скорее всего, у тебя в рекурсивном варианте создаётся слишком много больших стековых переменных. Ведь std::sort работает без проблем, а у тебя просто ошибка в алгоритме. Была.
Глупец
23 / 23 / 1
Регистрация: 17.05.2011
Сообщений: 141
19.06.2011, 08:13  [ТС]     Свой квиксорт с домино и буфетчицами! #8
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void sort(int in[], int a, int b){
 int i,j,mode;
 double sr=0;
 if (a>=b) return;                      // Размер части =0
 for (i=a; i<=b; i++) sr+=in[i];
 sr=sr/(b-a+1);
 for (i=a, j=b; i <= j;)
    {
    if (in[i]< sr) { i++; continue; }   // Слева - меньше, пропустить
    if (in[j]>=sr) { j--; continue; }   // Справа - больше, пропустить
    int c = in[i]; in[i] = in[j]; in[j]=c;
    i++,j--;                            // Поменять местами и пропустить
    }
 if (i==a) return;                      // все равны и в правой части
 sort(in,a,j); sort(in,i,b);}
вот рекурсивный код.
и здесь на мой взгляд нет косяка-работает отлично)

повторю еще раз, до этого сообщения ни где рекурсию я не использовал-как в первом сообщении, так и в последующия

Добавлено через 1 минуту
head
|
V
next
|
V
next
|
V
NULL

Как-то так стэк выглядит...
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
19.06.2011, 08:13     Свой квиксорт с домино и буфетчицами! #9
Цитата Сообщение от Глупец Посмотреть сообщение
Делается это потому что системный вылетает при большом количестве элементов.
Как ты умудрился использовать системный стек без рекурсии?
Глупец
23 / 23 / 1
Регистрация: 17.05.2011
Сообщений: 141
19.06.2011, 08:19  [ТС]     Свой квиксорт с домино и буфетчицами! #10
да где ты увидел рекурсию в первом сообщении темы, и использование системного стека?!O_O

Цитата Сообщение от Глупец Посмотреть сообщение
В общем идея проста: сделать псевдо рекурсивную сортировку разделением, т.е. она будет работать на собственноручно созданом стеке.
Делается это потому что системный вылетает при большом количестве элементов.
Я сразу и предоставил вариант на своем стеке.
И собственно спрашиваю где косяк?
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
19.06.2011, 08:41     Свой квиксорт с домино и буфетчицами! #11
Цитата Сообщение от Deviaphan Посмотреть сообщение
Цитата Сообщение от Глупец Посмотреть сообщение
Делается это потому что системный вылетает при большом количестве элементов.
Как ты умудрился использовать системный стек без рекурсии?
Глупец
23 / 23 / 1
Регистрация: 17.05.2011
Сообщений: 141
19.06.2011, 09:07  [ТС]     Свой квиксорт с домино и буфетчицами! #12
Всем кто принимал участие спасибо-заработала.
ValeryS
Модератор
6374 / 4840 / 441
Регистрация: 14.02.2011
Сообщений: 16,040
19.06.2011, 09:11     Свой квиксорт с домино и буфетчицами! #13
Цитата Сообщение от Глупец Посмотреть сообщение
это за тем, чтоб при удалении не было рекурсии...здесь все норм, т.е. мы занулили указатель на следующий, а потом удалили то, что сняли со стека...
не занулил ты его
ты занулил указатель последнего элемента,который так указывает в ноль
а занулить тебе надо указатель на тот элемент который ты будешь удалять
пройди в отладчике и посмотри какой указатель на что у тебя указывает
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
19.06.2011, 09:17     Свой квиксорт с домино и буфетчицами!
Еще ссылки по теме:

Задача про Домино-2 C++
Определить, соответствует ли последовательность чисел ряду костей домино C++
Квиксорт на стеке отложенных заданий C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Глупец
23 / 23 / 1
Регистрация: 17.05.2011
Сообщений: 141
19.06.2011, 09:17  [ТС]     Свой квиксорт с домино и буфетчицами! #14
Цитата Сообщение от ValeryS Посмотреть сообщение
а занулить тебе надо указатель на тот элемент который ты будешь удалять
как бэ он верхний, на него ни чего не указывает...
head->next->next->next->next->next->NULL
Вот так стек мой и выглядит...
Yandex
Объявления
19.06.2011, 09:17     Свой квиксорт с домино и буфетчицами!
Ответ Создать тему
Опции темы

Текущее время: 05:45. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru