С Новым годом! Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 10, средняя оценка - 4.80
Глупец
23 / 23 / 1
Регистрация: 17.05.2011
Сообщений: 141
#1

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

18.06.2011, 21:03. Просмотров 1207. Ответов 13
Метки нет (Все метки)

Доброго времени суток!
В общем идея проста: сделать псевдо рекурсивную сортировку разделением, т.е. она будет работать на собственноручно созданом стеке.
Делается это потому что системный вылетает при большом количестве элементов.
Так вот проблема в том, что для 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;
}
Если кто подскажет буду очень благодарен)
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
18.06.2011, 21:03
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Свой квиксорт с домино и буфетчицами! (C++):

Квиксорт на стеке отложенных заданий - C++
Улучшаю квиксорт. Первый алгоритм - снятие хвостовой рекурсии, а второй - реализация квиксорта на стеке отложенных заданий. Вот код: ...

Домино - C++
нужна программа домино исходник для курсака

Кости домино - C++
Написать проект, в котором случайным образом рисуется кость домино, а затем все кости, которые к ней можно присоединить.

Набор домино - C++
Набор домино состоит из прямоугольных костяшек, каждая из которых разделена на две половинки линией, параллельной более короткой стороне....

Программа домино - C++
Здравствуйте , столкнулся со сложностью . мне нужно вывести числа как на фотке. Вот мой код. Пытался по всякому с циклом for,...

Задача про Домино-2 - C++
Пожалуйста, помогите срочно!! Желательно код, или помогите переделать задачу про домино ранее на этом сайте:...

13
ValeryS
Модератор
6729 / 5138 / 485
Регистрация: 14.02.2011
Сообщений: 17,247
18.06.2011, 22:53 #2
Цитата Сообщение от Глупец Посмотреть сообщение
соответственно runtime улетает в поднебесье...
скорее всего что то с выделением памяти
потом обращение к невыделенной и досвидания
пройди под отладчиком
а лучше используй исключения

Добавлено через 9 минут
Цитата Сообщение от Глупец Посмотреть сообщение
tmp_p->next=NULL;
delete tmp_p;
вот это зачем??
обнуляешь поле у элемента который в следуюшей строчке удалишь???
тебе нужно обнулить поле у элемента который указывает на tmp_p
может так
C++
1
tmp_p->next->next=NULL;
извини серьезно в программе не разбирался
слишком сложно ты закрутил с указателями
разберись с ними
для начала задокументируй программу
0
Jupiter
Каратель
Эксперт С++
6561 / 3982 / 227
Регистрация: 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;
}
оригинально
0
Глупец
23 / 23 / 1
Регистрация: 17.05.2011
Сообщений: 141
19.06.2011, 07:35  [ТС] #4
Цитата Сообщение от ValeryS Посмотреть сообщение
Добавлено через 9 минут
Сообщение от Глупец
tmp_p->next=NULL;
delete tmp_p;
вот это зачем??
обнуляешь поле у элемента который в следуюшей строчке удалишь???
это за тем, чтоб при удалении не было рекурсии...здесь все норм, т.е. мы занулили указатель на следующий, а потом удалили то, что сняли со стека...

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

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

А как по другому реализовать pop, или в чем там косяк?
0
Deviaphan
Делаю внезапно и красиво
Эксперт С++
1306 / 1221 / 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 работает без проблем, а у тебя просто ошибка в алгоритме. Была.
0
Глупец
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

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

Цитата Сообщение от Глупец Посмотреть сообщение
В общем идея проста: сделать псевдо рекурсивную сортировку разделением, т.е. она будет работать на собственноручно созданом стеке.
Делается это потому что системный вылетает при большом количестве элементов.
Я сразу и предоставил вариант на своем стеке.
И собственно спрашиваю где косяк?
0
Deviaphan
Делаю внезапно и красиво
Эксперт С++
1306 / 1221 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
19.06.2011, 08:41 #11
Цитата Сообщение от Deviaphan Посмотреть сообщение
Цитата Сообщение от Глупец Посмотреть сообщение
Делается это потому что системный вылетает при большом количестве элементов.
Как ты умудрился использовать системный стек без рекурсии?
0
Глупец
23 / 23 / 1
Регистрация: 17.05.2011
Сообщений: 141
19.06.2011, 09:07  [ТС] #12
Всем кто принимал участие спасибо-заработала.
0
ValeryS
Модератор
6729 / 5138 / 485
Регистрация: 14.02.2011
Сообщений: 17,247
19.06.2011, 09:11 #13
Цитата Сообщение от Глупец Посмотреть сообщение
это за тем, чтоб при удалении не было рекурсии...здесь все норм, т.е. мы занулили указатель на следующий, а потом удалили то, что сняли со стека...
не занулил ты его
ты занулил указатель последнего элемента,который так указывает в ноль
а занулить тебе надо указатель на тот элемент который ты будешь удалять
пройди в отладчике и посмотри какой указатель на что у тебя указывает
0
Глупец
23 / 23 / 1
Регистрация: 17.05.2011
Сообщений: 141
19.06.2011, 09:17  [ТС] #14
Цитата Сообщение от ValeryS Посмотреть сообщение
а занулить тебе надо указатель на тот элемент который ты будешь удалять
как бэ он верхний, на него ни чего не указывает...
head->next->next->next->next->next->NULL
Вот так стек мой и выглядит...
0
19.06.2011, 09:17
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
19.06.2011, 09:17
Привет! Вот еще темы с ответами:

Функции, Домино, Как!!? - C++
Как написать проект, в котором случайным образом рисуется кость домино, а затем все кости, которые к ней можно присоединить? Как можно...

Реализовать точки на костях домино - C++
Точки на костях Домино (Время: 1 сек. Память: 16 Мб Сложность: 25%) Для того, чтобы заработать огромный капитал, новым русским...

Найти наибольшую сумму костей домино игрока - C++
У игрока есть k костей домино - прямоугольников 2x1. Он кладет их на доску так, чтобы не возникало наложений, и его выигрыш вычисляется как...

Определить, соответствует ли последовательность чисел ряду костей домино - C++
Дана последовательность двадцати чисел из интервала от 0 до 66, представляющая собой условное обозначение костей домино (например, число 42...


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

Или воспользуйтесь поиском по форуму:
14
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.