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

сортировка перестановками - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 13, средняя оценка - 4.77
crewww
30 / 1 / 1
Регистрация: 28.10.2010
Сообщений: 102
26.03.2012, 19:18     сортировка перестановками #1
нужно отсортировать линейный список перестановками
я так понимаю это тоже самое что пузырек?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.03.2012, 19:18     сортировка перестановками
Посмотрите здесь:

C/C++ FAQ :: Быстрая сортировка (сортировка Хоара) C++
C++ сортировка линейного списка перестановками
Быстрая сортировка(сортировка Хоара). Отсортировать фрагмент массива C++
Построить последовательность n!, для n=1…7 со всеми возможными перестановками из элементов этой последовательности C++
Быстрая сортировка (сортировка Хоара) для связных списков C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
bunny
7 / 7 / 0
Регистрация: 18.03.2012
Сообщений: 77
26.03.2012, 19:19     сортировка перестановками #2
да это тоже самое
crewww
30 / 1 / 1
Регистрация: 28.10.2010
Сообщений: 102
26.03.2012, 19:58  [ТС]     сортировка перестановками #3
Цитата Сообщение от bunny Посмотреть сообщение
да это тоже самое
хорошо
то есть мне нужно реализовать стандартный код как для массивов?
bunny
7 / 7 / 0
Регистрация: 18.03.2012
Сообщений: 77
26.03.2012, 21:52     сортировка перестановками #4
Цитата Сообщение от crewww Посмотреть сообщение
хорошо
то есть мне нужно реализовать стандартный код как для массивов?
Да но смотря что ты хочешь сортировать? если цифры тогда простые знаки <,> если буквы коды из аски
Kuzia domovenok
 Аватар для Kuzia domovenok
1883 / 1738 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
26.03.2012, 22:15     сортировка перестановками #5
Цитата Сообщение от crewww Посмотреть сообщение
хорошо
то есть мне нужно реализовать стандартный код как для массивов?
создай функцию перестановки двух соседних элементов.
Дальше дело техники.
crewww
30 / 1 / 1
Регистрация: 28.10.2010
Сообщений: 102
26.03.2012, 23:01  [ТС]     сортировка перестановками #6
естественно числа)
попробую написать код
crewww
30 / 1 / 1
Регистрация: 28.10.2010
Сообщений: 102
08.04.2012, 01:42  [ТС]     сортировка перестановками #7
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
#include <iostream>
#include <fstream>
using namespace std;
struct tElem
{
    int value;
    tElem *r;
};
void create(tElem* &list,ifstream &f)
{
    tElem *temp;
    list=new tElem;
    temp=list;
    f>>temp->value;
    while (f.peek()!=EOF)
    {
        temp->r=new tElem;
        temp=temp->r;
        temp->r=NULL;
        f>>temp->value;
    }
}
void change(tElem* &a)
{ifstream f;
create(a,f);
    tElem *temp;
    a=new tElem;
        temp=a;
        a=temp->r;
        temp->r=a;
 
}
 
void bubbleSort (tElem *&list, ifstream &f)
{   create(list);
    while (list)
    {
        if (list->r->value > list->r->r-value)
        change(list);
    }
}
написал код, но он совсем нерабочий компилятор ругается практически на все
подскажите в чем я согрешил
Kuzia domovenok
 Аватар для Kuzia domovenok
1883 / 1738 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
08.04.2012, 11:46     сортировка перестановками #8
наверное там, где не добавил функцию main. (или она в другом файле)?

C++
1
2
3
4
5
6
7
8
9
void change(tElem* &a)
{ifstream f;
create(a,f);
    tElem *temp;
    a=new tElem;
        temp=a;
        a=temp->r;
        temp->r=a;
}
ЛОЛ. То есть ты для перестановки двух элементов
-создаёшь заново список, причём
-создаёшь его из какого-то неинициализированного файлопотока,
-берёшь в качестве аргумента нечто tElem* &a, боюсь предположить, что это, указатель на ссылку?
-затем полностью затираешь свою ссылку "а", теряя всё
-затем в а записываешь неинициализированное поле r из только созданного объекта temp
-И затем снова присваиваешь его a , в точно таком виде, в каком ты его прочитал.

Может тебе рановато списки проходить?

Добавлено через 17 минут
и ещё: вот это
C++
1
2
3
4
5
while (list)
    {
        if (list->r->value > list->r->r-value)
        change(list);
    }
-это не сортировка пузырьком, это один проход пузырька, а надо сортировать, пока не отсортируется
Лучше так
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
tElem *list_ptr;
bool run;
while (run){
   run=true;
   list_ptr=start;
   while (list_ptr->r)
    {
        if (list_ptr->value > list_ptr->r-value){
                change(list_ptr);
                run=false;
               }
    }
}
Так что перестань пихать везде create(list)!!!!!
crewww
30 / 1 / 1
Регистрация: 28.10.2010
Сообщений: 102
08.04.2012, 12:36  [ТС]     сортировка перестановками #9
может и рановато
но меня никто не спрашивает рановато ли мне или нет, задают и я разбираюсь
Kuzia domovenok
 Аватар для Kuzia domovenok
1883 / 1738 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
08.04.2012, 12:45     сортировка перестановками #10
Ой только я похоже с run=true напутал
так чуть вернее:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
tElem *list_ptr;
bool run=true;
while (run){
   run=false;
   list_ptr=start;
   while (list_ptr->r)
       {
        if (list_ptr->value > list_ptr->r-value){
                change(list_ptr);
                run=true;
                }
       }
}
crewww
30 / 1 / 1
Регистрация: 28.10.2010
Сообщений: 102
08.04.2012, 19:00  [ТС]     сортировка перестановками #11
как сделать правильно перестановку 2-x элементов?
crewww
30 / 1 / 1
Регистрация: 28.10.2010
Сообщений: 102
09.04.2012, 20:40  [ТС]     сортировка перестановками #12
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 tElem *c;
 tElement *t=c;
 
for (int i=0; i<n; i++)
 { c=t;
 
 while (c->r!=NULL)
 { if (c->value>c->r->value)
 { int temp=c->value;
 c->value=c->r->value;
 c->r->value=temp;
 }
 c=c->r;
 }
 }
а что если вот так реализовать сортировку?
Kuzia domovenok
 Аватар для Kuzia domovenok
1883 / 1738 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
09.04.2012, 20:53     сортировка перестановками #13
твоё право, вполне рабочая вещь, - сработает.

Хотя, конечно, будь я преподавателем, я бы потребовал сделать через "перенаправление указателей".
ну то есть через изменение адресов на которые "следующий" и "предыдущий" указывают,
но это сложнее.
crewww
30 / 1 / 1
Регистрация: 28.10.2010
Сообщений: 102
09.04.2012, 21:19  [ТС]     сортировка перестановками #14
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
твоё право, вполне рабочая вещь, - сработает.

Хотя, конечно, будь я преподавателем, я бы потребовал сделать через "перенаправление указателей".
ну то есть через изменение адресов на которые "следующий" и "предыдущий" указывают,
но это сложнее.
я то вот именно сам и хотел через перенаправление указателей сделать, про способ выше я додумался к своему стыду не сразу а только когда мне подсказали

а как можно сделать перенаправлением указателей? выше вы написали код, но там есть функция change которая у меня бредово описана, вот как ее грамотно описать?
Kuzia domovenok
 Аватар для Kuzia domovenok
1883 / 1738 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
09.04.2012, 21:45     сортировка перестановками #15
Цитата Сообщение от crewww Посмотреть сообщение
я то вот именно сам и хотел через перенаправление указателей сделать, про способ выше я додумался к своему стыду не сразу а только когда мне подсказали

а как можно сделать перенаправлением указателей? выше вы написали код, но там есть функция change которая у меня бредово описана, вот как ее грамотно описать?
Во! Зацени! Хитро а? Запутаться в таком довольно просто.
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
tElem *list_ptr;
tElem *pre_ptr=NULL;
bool run;
while (run){
   run=true;
   list_ptr=start;
   while (list_ptr->r)
    {
        if (list_ptr->value > list_ptr->r-value){
               /* change(list_ptr);*/
                if (list_ptr==start){//случай если меняем первый и второй элемент особый, т.к
                                    //предыдущего элемента нет
                    start=list_ptr->next;
                    list_ptr->next=start->next;
                    start->next=list_ptr;
                }
                else{//все остальные случаи
                 pre_ptr->next=list_ptr->next;
                 list_ptr->next=list_ptr->next->next;
                 pre_ptr->next->next=list_ptr;
                }
                run=false;
               }
        pre_ptr=list_ptr;
        list_ptr=list_ptr->r;
         
    }
}
crewww
30 / 1 / 1
Регистрация: 28.10.2010
Сообщений: 102
09.04.2012, 23:09  [ТС]     сортировка перестановками #16
круто) спасибо
а не могли бы вы что нибудь посоветовать мне что ли по спискам, а то чувствую я тяжко ой как тяжко мне будет на контрольной
Kuzia domovenok
 Аватар для Kuzia domovenok
1883 / 1738 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
10.04.2012, 19:24     сортировка перестановками #17
Цитата Сообщение от crewww Посмотреть сообщение
круто) спасибо
а не могли бы вы что нибудь посоветовать мне что ли по спискам, а то чувствую я тяжко ой как тяжко мне будет на контрольной
Я не уверен, что считается хорошей книгой. Я в своё время начинал с "Крупник. Изучаем Си". В инете есть. Маленькая такая книга, я считаю, что мне помогла, списки там разбирались нормально.
Но опять-таки, я не знаю, возможно есть какая-то более "классическая" литература.
(в книге описывается работа со средой borland C++ for DOS) но на консольные приложения в Visual Studio эти примеры полностью подходят.

Добавлено через 20 часов 9 минут
Сильно извиняюсь, похоже я в предыдущем посте запутался с условием выхода из цикла
Думаю так верно:
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
tElem *list_ptr;
tElem *pre_ptr=NULL;
bool run=true;
while (run){
   run=false;
   list_ptr=start;
   while (list_ptr->r)
    {
        if (list_ptr->value > list_ptr->r-value){
               /* change(list_ptr);*/
                if (list_ptr==start){//случай если меняем первый и второй элемент особый, т.к
                                    //предыдущего элемента нет
                    start=list_ptr->next;
                    list_ptr->next=start->next;
                    start->next=list_ptr;
                }
                else{//все остальные случаи
                 pre_ptr->next=list_ptr->next;
                 list_ptr->next=list_ptr->next->next;
                 pre_ptr->next->next=list_ptr;
                }
                run=true;
               }
        pre_ptr=list_ptr;
        list_ptr=list_ptr->r;
         
    }
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
17.04.2012, 03:05     сортировка перестановками
Еще ссылки по теме:

C++ Сортировка слиянием. В каком куске кода происходит сортировка и каким именно образом?
C++ Перестановками заполнить главную диагональ двумерного массива наибольшими элементами
C++ Сортировка Шелла. Написал программу, не могу понять, почему сортировка не выполняется

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

Или воспользуйтесь поиском по форуму:
crewww
30 / 1 / 1
Регистрация: 28.10.2010
Сообщений: 102
17.04.2012, 03:05  [ТС]     сортировка перестановками #18
все таки я пока решил попробовать показать вариант без перенаправления указателей, но он наотрез отказывается работать. Можете указать на ошибку?
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
#include <iostream>
#include <fstream>
using namespace std;
 
 
struct tElem
{
 int value;
 tElem *next;
 
};
 
void create_list(tElem* &h1,ifstream &f)
{
tElem* temp;
 
h1=new tElem;
 
temp=h1;
 
f>>temp->value;
 
while(f.peek()!=EOF)
    {
        temp->next=new tElem;
        
        temp=temp->next;
        
        temp->next=NULL;
        
        f>>temp->value;
    }
 
}
 
int main()
{
 tElem *c;
 
 ifstream file("bubble.txt");
 
 create_list(c,file);
 tElem *t=c;
 
while (file.peek()!=EOF)
{
     c=t;
 
    while (c->next!=NULL)
    {
     if (c->value>c->next->value)
        {
            int temp=c->value;
 
            c->value=c->next->value;
 
            c->next->value=temp;
        }
    c=c->next;
    }
 }
t=c;
while (t)
{
    cout<<t->value<<" ";
    t=t->next;
}
file.close();
 
 return 0;
}
Yandex
Объявления
17.04.2012, 03:05     сортировка перестановками
Ответ Создать тему
Опции темы

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