Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 5.00/9: Рейтинг темы: голосов - 9, средняя оценка - 5.00
24 / 24 / 3
Регистрация: 17.05.2011
Сообщений: 141

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

18.06.2011, 21:03. Показов 2126. Ответов 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
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
18.06.2011, 21:03
Ответы с готовыми решениями:

Крах апгрейда Домино 7 сервера на Домино 8
Доброго времени суток. У меня возникла проблема, суть: 1. На Шведской оське стоит английский Домино 7 + шведский ленвич пак. Там же...

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

Задача "Домино": сгенерировать рандомно 28 костяшек домино
Надо написать код, который задавал бы рандомно 28 пар неповторяющихся элементов от 0 до 6. то есть 28 доминошек. type ...

13
Модератор
Эксперт по электронике
8981 / 6748 / 921
Регистрация: 14.02.2011
Сообщений: 23,871
18.06.2011, 22:53
Цитата Сообщение от Глупец Посмотреть сообщение
соответственно runtime улетает в поднебесье...
скорее всего что то с выделением памяти
потом обращение к невыделенной и досвидания
пройди под отладчиком
а лучше используй исключения

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

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

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

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

Добавлено через 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
24 / 24 / 3
Регистрация: 17.05.2011
Сообщений: 141
19.06.2011, 08:13  [ТС]
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
1313 / 1228 / 72
Регистрация: 22.03.2011
Сообщений: 3,744
19.06.2011, 08:13
Цитата Сообщение от Глупец Посмотреть сообщение
Делается это потому что системный вылетает при большом количестве элементов.
Как ты умудрился использовать системный стек без рекурсии?
0
24 / 24 / 3
Регистрация: 17.05.2011
Сообщений: 141
19.06.2011, 08:19  [ТС]
да где ты увидел рекурсию в первом сообщении темы, и использование системного стека?!O_O

Цитата Сообщение от Глупец Посмотреть сообщение
В общем идея проста: сделать псевдо рекурсивную сортировку разделением, т.е. она будет работать на собственноручно созданом стеке.
Делается это потому что системный вылетает при большом количестве элементов.
Я сразу и предоставил вариант на своем стеке.
И собственно спрашиваю где косяк?
0
Делаю внезапно и красиво
Эксперт С++
 Аватар для Deviaphan
1313 / 1228 / 72
Регистрация: 22.03.2011
Сообщений: 3,744
19.06.2011, 08:41
Цитата Сообщение от Deviaphan Посмотреть сообщение
Цитата Сообщение от Глупец Посмотреть сообщение
Делается это потому что системный вылетает при большом количестве элементов.
Как ты умудрился использовать системный стек без рекурсии?
0
24 / 24 / 3
Регистрация: 17.05.2011
Сообщений: 141
19.06.2011, 09:07  [ТС]
Всем кто принимал участие спасибо-заработала.
0
Модератор
Эксперт по электронике
8981 / 6748 / 921
Регистрация: 14.02.2011
Сообщений: 23,871
19.06.2011, 09:11
Цитата Сообщение от Глупец Посмотреть сообщение
это за тем, чтоб при удалении не было рекурсии...здесь все норм, т.е. мы занулили указатель на следующий, а потом удалили то, что сняли со стека...
не занулил ты его
ты занулил указатель последнего элемента,который так указывает в ноль
а занулить тебе надо указатель на тот элемент который ты будешь удалять
пройди в отладчике и посмотри какой указатель на что у тебя указывает
0
24 / 24 / 3
Регистрация: 17.05.2011
Сообщений: 141
19.06.2011, 09:17  [ТС]
Цитата Сообщение от ValeryS Посмотреть сообщение
а занулить тебе надо указатель на тот элемент который ты будешь удалять
как бэ он верхний, на него ни чего не указывает...
head->next->next->next->next->next->NULL
Вот так стек мой и выглядит...
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
19.06.2011, 09:17
Помогаю со студенческими работами здесь

Свой компонент от ListBox. Не могу задать свой тип для Items
День добрый господа. Нуждаюсь в вашей помощи. Суть такова, что я желаю создать свой компонент на базе ListBox. На данный момент меня...

Как установить свой текст подсказки при наведении на свой контрол?
Как установить свой текст подсказки при наведении на свой контрол?

Как посадить свой домен на свой сайт, который на домашнем компе?
У меня статический ip. на картинке видно что сейчас в настройках, в качестве записи A указал свой статический ip, больше в 1-ой...

В свой div свой текст, класс один и тот же
div class=&quot;head&quot;&gt;ОДИН&lt;/div&gt; &lt;div class=&quot;body&quot;&gt;&lt;div class=&quot;cl&quot;&gt;&lt;/div&gt; &lt;script&gt; $(document).ready(function() { //Если клик...

Домино
Народ помогите у меня такая проблема игра запускает а нечего не работает ходить нажимаю тоже нечего .Помогите пожалуйста я уже не знаю что...


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

Или воспользуйтесь поиском по форуму:
14
Ответ Создать тему
Новые блоги и статьи
SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий
8Observer8 02.03.2026
Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11680&amp;d=1772460536 Одним из. . .
Реалии
Hrethgir 01.03.2026
Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .
Ритм жизни
kumehtar 27.02.2026
Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .
SDL3 для Web (WebAssembly): Сборка библиотек: SDL3, Box2D, FreeType, SDL3_ttf, SDL3_mixer и SDL3_image из исходников с помощью CMake и Emscripten
8Observer8 27.02.2026
Недавно вышла версия 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual Studio. . . .
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами
8Observer8 20.02.2026
Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .
Конвертировать закладки radiotray-ng в m3u-плейлист
damix 19.02.2026
Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .
Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI
Eddy_Em 18.02.2026
Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .
Камера Toupcam IUA500KMA
Eddy_Em 12.02.2026
Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru