Как отсортировать односвязный список си
Pers.narod.ru. Алгоритмы. Cортировка односвязного списка перестановкой указателей
Сортировка односвязного списка — одна из самых типовых «головоломных» задач для начинающих.
В принципе, если список состоит, к примеру, из больших структур, теоретически имеет смысл при сортировке не копировать данные, а менять их местами с помощью имеющихся в структуре указателей на связанные элементы.
Но на практике даже простейшая пузырьковая сортировка заметно усложняется связями указателей. поэтому в инете куча неработающих решений и неверных мнений, не стану приводить ссылки на все.
По-моему, вся беда типовых «студенческих» кодов в том, что авторы пытались применить любимый «пузырёк» к списку по аналогии с массивом, а в списке из-за перестановок указателей начиналась путаница.
Метод вставок рулит, что б там не писали на форумах. Остальные комменты в исходнике:
#include #include #include #include #define MAX 30 typedef struct student < unsigned char f[MAX]; //Фамилия int ekz[4]; //4 оценки student *next; //Указатель на следующего студента >; int show (student *head) < //Показать список, начиная с эл. head и вернуть кол-во записей int count=0; while (1) < printf ("\n%s",head->f); for (int i=0; iekz[i]); count++; if (!head->next) break; head=head->next; > return count; > student *sort (student *ph) < //Сортируем список по алфавиту (фамилии, полю f) и возвращаем //указатель на начало измененного списка student *q,*out=NULL,*p,*pr; //out - выход - сначала пуст while (ph !=NULL) < //пока не конец входного списка q = ph; ph = ph->next; //исключить очередной элемент for (p=out,pr=NULL; p!=NULL && strcmp(q->f,p->f)>0; pr=p,p=p->next); //ищем, куда включить очередной элемент - тут strcmp //задает критерий сравнения элементов, в вашей задаче м.б. другой if (pr==NULL) < q->next=out; out=q; > //включение в начало else < q->next=p; pr->next=q; > //или после предыдущего > return out; > void main () < student group[] = < //В начале фамилии в списке расставлены как в массиве - //предыдущий элемент показывает на следующий ,&group[1]>, ,&group[2]>, ,&group[3]>, ,&group[4]>, ,NULL> >; printf ("\nИсходный список:"); int count=show (&group[0]); printf ("\nВсего записей: %d",count); //Сортируем список структур по алфавиту student *ptr=sort (group); printf ("\nОтсортированный список:"); show (ptr); getchar(); >
Проверил в консольном Borland C++ 3.1, работает, завершается без Null pointer assignment, значит, есть надежда, что нормально. хотя вырожденные случаи не смотрел, а писал в спешке, мож чего и не так, тогда жду поправок.
Как отсортировать односвязный список си
Сортировка односвязного списка
Посмотрите пожалуйста свежим взглядом на функцию sort не могу понять что не правильно она зациклятся(((
#include #include #include #include #include #include struct Node< int d; char *NM; Node *next; >; Node * first(FILE * fp)< int d; fscanf(fp,"%d",&d); char str[50]; fgets(str,50,fp); int strln=strlen(str); Node *pv=new Node; pv->NM=new char [strln+1]; strcpy(pv->NM,str); pv->d=d; pv->next=0; return pv; > void add(Node **pend, FILE * fp)< int d; fscanf(fp,"%d",&d); char str[50]; fgets(str,50,fp); int strln=strlen(str); Node *pv=new Node; pv->NM=new char [strln+1]; strcpy(pv->NM,str); pv->d=d; pv->next=0; (*pend)->next=pv; *pend=pv; > void sort(Node **pbeg,Node **pend) < Node *f=*pbeg; Node *temp=0; Node *tmp=0; Node *pv=f->next; int l=0; int min; while (f->next)< min=f->d; l=0; pv=f->next; while(pv)< if(pv->dd; l++; tmp=pv; > pv=pv->next; > if(l>0) < if(f==*pbeg) temp=f->next; f->next=tmp->next; tmp->next=temp; f=temp; > else next;> > > void print(Node *pv) < while (pv)< printf("%d %s",pv->d,pv->NM); pv=pv->next; > > int main() < clrscr(); FILE * fp; fp=fopen("D:\\WORK\\TC\\7.txt","r+"); if (fp==NULL) < printf("Ochibka otkritia fila 7.txt"); >Node *pbeg=first(fp); Node *pend=pbeg; while(!feof(fp)) < add(&pend,fp); >Node *pv=pbeg; print(pv); printf("\n\n"); sort(&pbeg,&pend); print(pv); fclose(fp); while(pv) < delete[]pv->NM; pv=pv->next; > getch(); return 0; > Форумчанин
Регистрация: 02.10.2009
Сообщений: 104
что то у тебя много кода, попробуй переделать сортировку методом вставок по аналогии:
list *sort(list *ph) // функция возвращает заголовок нового списка < list *q, *out, *p , *pr; out = NULL; // выходной список пуст while (ph !=NULL) // пока не пуст входной список < q = ph; ph = ph->next; // исключить очередной // поиск места включения for ( p=out,pr=NULL; p!=NULL && q->val>p->val; pr=p,p=p->next); if (pr==NULL) // включение перед первым < q->next=out; out=q; > else // иначе после предыдущего < q->next=p; pr->next=q; > > return out; >| blackbanny |
| Посмотреть профиль |
| Найти ещё сообщения от blackbanny |
| Похожие темы | ||||
| Тема | Автор | Раздел | Ответов | Последнее сообщение |
| СИ. Списки. Описание структуры односвязного списка | Jane-sad | Помощь студентам | 9 | 17.05.2010 14:40 |
| Мин. элемент. односвязного списка в СИ | Sultan237 | Общие вопросы C/C++ | 0 | 22.03.2010 23:24 |
| Сортировка односвязного списка | btf | Общие вопросы C/C++ | 0 | 15.02.2010 14:40 |
| Сортировка списка | DOJ | Общие вопросы C/C++ | 3 | 23.08.2009 19:36 |
| Cортировка односвязного списка | alesfoss | Общие вопросы C/C++ | 3 | 30.03.2009 19:46 |
Односвязный список
О дносвязный список – структура данных, в которой каждый элемент (узел) хранит информацию, а также ссылку на следующий элемент. Последний элемент списка ссылается на NULL.
Для нас односвязный список полезен тем, что
- 1) Он очень просто устроен и все алгоритмы интуитивно понятны
- 2) Односвязный список – хорошее упражнение для работы с указателями
- 3) Его очень просто визаулизировать, это позволяет «в картинках» объяснить алгоритм
- 4) Несмотря на свою простоту, односвязные списки часто используются в программировании, так что это не пустое упражнение.
- 5) Эта структуру данных можно определить рекурсивно, и она часто используется в рекурсивных алгоритмах.
Для простоты рассмотрим односвязный список, который хранит целочисленное значение.
Односвязный список
Односвязный список состоит из узлов. Каждый узел содержит значение и указатель на следующий узел, поэтому представим его в качестве структуры
typedef struct Node < int value; struct Node *next; >Node;
Чтобы не писать каждый раз struct мы определили новый тип.
Теперь наша задача написать функцию, которая бы собирала список из значений, которые мы ей передаём. Стандартное имя функции – push, она должна получать в качестве аргумента значение, которое вставит в список. Новое значение будет вставляться в начало списка. Каждый новый элемент списка мы должны создавать на куче. Следовательно, нам будет удобно иметь один указатель на первый элемент списка.
Node *head = NULL;
Вначале списка нет и указатель ссылается на NULL.
Для добавления нового узла необходимо
- 1) Выделить под него память.
- 2) Задать ему значение
- 3) Сделать так, чтобы он ссылался на предыдущий элемент (или на NULL, если его не было)
- 4) Перекинуть указатель head на новый узел.
1) Создаём новый узел
Создали новый узел, на который ссылается локальная переменная tmp
2) Присваиваем ему значение
Присвоили ему значение
3) Присваиваем указателю tmp адрес предыдущего узла
Перекинули указатель tmp на предыдущий узел
4) Присваиваем указателю head адрес нового узла
Перекинули указатель head на вновь созданный узел tmp
5) После выхода из функции переменная tmp будет уничтожена. Получим список, в который будет вставлен новый элемент.
Новый узел добавлен
void push(Node **head, int data) < Node *tmp = (Node*) malloc(sizeof(Node)); tmp->value = data; tmp->next = (*head); (*head) = tmp; >
Так как указатель head изменяется, то необходимо передавать указатель на указатель.
Теперь напишем функцию pop: она удаляет элемент, на который указывает head и возвращает его значение.
Если мы перекинем указатель head на следующий элемент, то мы потеряем адрес первого и не сможем его удалить и тем более вернуть его значения. Для этого необходимо сначала создать локальную переменную, которая будет хранить адрес первого элемента
Локальная переменная хранит адрес первого узла
Уже после этого можно удалить первый элемент и вернуть его значение
Перекинули указатель head на следующий элемент и удалили узел
int pop(Node **head) < Node* prev = NULL; int val; if (head == NULL) < exit(-1); >prev = (*head); val = prev->value; (*head) = (*head)->next; free(prev); return val; >
Не забываем, что необходимо проверить на NULL голову.
Таким образом, мы реализовали две операции push и pop, которые позволяют теперь использовать односвязный список как стек. Теперь добавим ещё две операции — pushBack (её ещё принято называть shift или enqueue), которая добавляет новый элемент в конец списка, и функцию popBack (unshift, или dequeue), которая удаляет последний элемент списка и возвращает его значение.
Для дальнейшего разговора необходимо реализовать функции getLast, которая возвращает указатель на последний элемент списка, и nth, которая возвращает указатель на n-й элемент списка.
Так как мы знаем адрес только первого элемента, то единственным способом добраться до n-го будет последовательный перебор всех элементов списка. Для того, чтобы получить следующий элемент, нужно перейти к нему через указатель next текущего узла
Node* getNth(Node* head, int n) < int counter = 0; while (counter < n && head) < head = head->next; counter++; > return head; >
Переходя на следующий элемент не забываем проверять, существует ли он. Вполне возможно, что был указан номер, который больше размера списка. Функция вернёт в таком случае NULL. Сложность операции O(n), и это одна из проблем односвязного списка.
Для нахождение последнего элемента будем передирать друг за другом элементы до тех пор, пока указатель next одного из элементов не станет равным NULL
Node* getLast(Node *head) < if (head == NULL) < return NULL; >while (head->next) < head = head->next; > return head; >
Теперь добавим ещё две операции — pushBack (её ещё принято называть shift или enqueue), которая добавляет новый элемент в конец списка, и функцию popBack (unshift, или dequeue), которая удаляет последний элемент списка и возвращает его значение.
Для вставки нового элемента в конец сначала получаем указатель на последний элемент, затем создаём новый элемент, присваиваем ему значение и перекидываем указатель next старого элемента на новый
void pushBack(Node *head, int value) < Node *last = getLast(head); Node *tmp = (Node*) malloc(sizeof(Node)); tmp->value = value; tmp->next = NULL; last->next = tmp; >
Односвязный список хранит адрес только следующего элемента. Если мы хотим удалить последний элемент, то необходимо изменить указатель next предпоследнего элемента. Для этого нам понадобится функция getLastButOne, возвращающая указатель на предпоследний элемент.
Node* getLastButOne(Node* head) < if (head == NULL) < exit(-2); >if (head->next == NULL) < return NULL; >while (head->next->next) < head = head->next; > return head; >
Функция должна работать и тогда, когда список состоит всего из одного элемента. Вот теперь есть возможность удалить последний элемент.
void popBack(Node **head) < Node *lastbn = NULL; //Получили NULL if (!head) < exit(-1); >//Список пуст if (!(*head)) < exit(-1); >lastbn = getLastButOne(*head); //Если в списке один элемент if (lastbn == NULL) < free(*head); *head = NULL; >else < free(lastbn->next); lastbn->next = NULL; > >
Удаление последнего элемента и вставка в конец имеют сложность O(n).
Можно написать алгоритм проще. Будем использовать два указателя. Один – текущий узел, второй – предыдущий. Тогда можно обойтись без вызова функции getLastButOne:
int popBack(Node **head) < Node *pFwd = NULL; //текущий узел Node *pBwd = NULL; //предыдущий узел //Получили NULL if (!head) < exit(-1); >//Список пуст if (!(*head)) < exit(-1); >pFwd = *head; while (pFwd->next) < pBwd = pFwd; pFwd = pFwd->next; > if (pBwd == NULL) < free(*head); *head = NULL; >else < free(pFwd->next); pBwd->next = NULL; > >
Теперь напишем функцию insert, которая вставляет на n-е место новое значение. Для вставки, сначала нужно будет пройти до нужного узла, потом создать новый элемент и поменять указатели. Если мы вставляем в конец, то указатель next нового узла будет указывать на NULL, иначе на следующий элемент
void insert(Node *head, unsigned n, int val) < unsigned i = 0; Node *tmp = NULL; //Находим нужный элемент. Если вышли за пределы списка, то выходим из цикла, //ошибка выбрасываться не будет, произойдёт вставка в конец while (i < n && head->next) < head = head->next; i++; > tmp = (Node*) malloc(sizeof(Node)); tmp->value = val; //Если это не последний элемент, то next перекидываем на следующий узел if (head->next) < tmp->next = head->next; //иначе на NULL > else < tmp->next = NULL; > head->next = tmp; >
Покажем на рисунке последовательность действий
Создали новый узел и присвоили ему значение
После этого делаем так, чтобы новый элемент ссылался на следующий после n-го
Теперь значение next нового узла хранит адрес того же узла, что и элемент, на который ссылается head
Перекидываем указатель next n-го элемента на вновь созданный узел
Теперь узел, адрес которого хранит head, указывает на новый узел tmp
Функция удаления элемента списка похожа на вставку. Сначала получаем указатель на элемент, стоящий до удаляемого, потом перекидываем ссылку на следующий элемент за удаляемым, потом удаляем элемент.
int deleteNth(Node **head, int n) < if (n == 0) < return pop(head); >else < Node *prev = getNth(*head, n-1); Node *elm = prev->next; int val = elm->value; prev->next = elm->next; free(elm); return val; > >
Рассмотрим то же самое в картинках. Сначала находим адреса удаляемого элемента и того, который стоит перед ним
Для удаления узла, на который ссылается elm необходим предыдущий узел, адрес которого хранит prev
После чего прокидываем указатель next дальше, а сам элемент удаляем.
Прекидываем указатель на следующий за удалённым узел и освобождаем память
Кроме создания списка необходимо его удаление. Так как самая быстрая функция у нас этот pop, то для удаления будем последовательно выталкивать элементы из списка.
void deleteList(Node **head) < while ((*head)->next) < pop(head); *head = (*head)->next; > free(*head); >
Вызов pop можно заменить на тело функции и убрать ненужные проверки и возврат значения
void deleteList(Node **head) < Node* prev = NULL; while ((*head)->next) < prev = (*head); (*head) = (*head)->next; free(prev); > free(*head); >
Осталось написать несколько вспомогательных функций, которые упростят и ускорят работу. Первая — создать список из массива. Так как операция push имеет минимальную сложность, то вставлять будем именно с её помощью. Так как вставка произойдёт задом наперёд, то массив будем обходить с конца к началу:
void fromArray(Node **head, int *arr, size_t size) < size_t i = size - 1; if (arr == NULL || size == 0) < return; >do < push(head, arr[i]); >while(i--!=0); >
И обратная функция, которая возвратит массив элементов, хранящихся в списке. Так как мы будем создавать массив динамически, то сначала определим его размер, а только потом запихнём туда значения.
int* toArray(const Node *head) < int leng = length(head); int *values = (int*) malloc(leng*sizeof(int)); while (head) < values[--leng] = head->value; head = head->next; > return values; >
И ещё одна функция, которая будет печатать содержимое списка
void printLinkedList(const Node *head) < while (head) < printf("%d ", head->value); head = head->next; > printf("\n"); >
Теперь можно провести проверку и посмотреть, как работает односвязный список
void main() < Node* head = NULL; int arr[] = ; //Создаём список из массива fromArray(&head, arr, 10); printLinkedList(head); //Вставляем узел со значением 333 после 4-го элемента (станет пятым) insert(head, 4, 333); printLinkedList(head); pushBack(head, 11); pushBack(head, 12); pushBack(head, 13); pushBack(head, 14); printLinkedList(head); printf("%d\n", pop(&head)); printf("%d\n", popBack(&head)); printLinkedList(head); //Удаляем пятый элемент (индексация с нуля) deleteNth(&head, 4); printLinkedList(head); deleteList(&head); getch(); >
Сортировка односвязного списка
Сортировать список будем слиянием. Этот метод очень похож на сортировку слиянием для массива. Для его реализации нам понадобятся две функции: одна буде делить список пополам, а другая будет объединять два упорядоченных односвязных списка, не создавая при этом новых узлов. Наша реализация не будет оптимальной, однако, некоторые решения, которые мы применим, могут быть использованы и в других алгоритмах.
Вспомогательная функция – слияние двух отсортированных списков. Функция не должна создавать новых узлов, так что будем использовать только имеющиеся. Для начала проверим, если хоть один из списков пуст, то вернём другой.
Node tmp; *c = NULL; if (a == NULL) < *c = b; return; >if (b == NULL)
После этого нужно, чтобы наша локальная переменная стала хранить адрес большего из узлов двух списков, от него и будем танцевать дальше
if (a->value < b->value) < *c = a; a = a->next; > else < *c = b; b = b->next; >
Теперь сохраним указатель c, так как в дальнейшем он будет использоваться для прохода по списку
tmp.next = *c;
После этого проходим по спискам, сравниваем значения и перекидываем их
while (a && b) < if (a->value < b->value) < (*c)->next = a; a = a->next; > else < (*c)->next = b; b = b->next; > (*c) = (*c)->next; >
В конце, может остаться один список, который пройден не до конца. Добавим его узлы
if (a) < while (a) < (*c)->next = a; (*c) = (*c)->next; a = a->next; > > if (b) < while (b) < (*c)->next = b; (*c) = (*c)->next; b = b->next; > >
Теперь указатель c хранит адрес последнего узла, а нам нужна ссылка на голову. Она как раз хранится во второй переменной tmp
*c = tmp.next;
void merge(Node *a, Node *b, Node **c) < Node tmp; *c = NULL; if (a == NULL) < *c = b; return; >if (b == NULL) < *c = a; return; >if (a->value < b->value) < *c = a; a = a->next; > else < *c = b; b = b->next; > tmp.next = *c; while (a && b) < if (a->value < b->value) < (*c)->next = a; a = a->next; > else < (*c)->next = b; b = b->next; > (*c) = (*c)->next; > if (a) < while (a) < (*c)->next = a; (*c) = (*c)->next; a = a->next; > > if (b) < while (b) < (*c)->next = b; (*c) = (*c)->next; b = b->next; > > *c = tmp.next; >
Ещё одна важная функция – нахождение середины списка. Для этих целей будем использовать два указателя. Один из них — fast – за одну итерацию будет два раза изменять значение и продвигаться по списку вперёд. Второй – slow, всего один раз. Таким образом, если список чётный, то slow окажется ровно посредине списка, а если список нечётный, то второй подсписок будет на один элемент длиннее.
void split(Node *src, Node **low, Node **high) < Node *fast = NULL; Node *slow = NULL; if (src == NULL || src->next == NULL) < (*low) = src; (*high) = NULL; return; >slow = src; fast = src->next; while (fast != NULL) < fast = fast->next; if (fast != NULL) < fast = fast->next; slow = slow->next; > > (*low) = src; (*high) = slow->next; slow->next = NULL; >
Очевидно, что можно было один раз узнать длину списка, а потом передавать размер в каждую функцию. Это было бы проще и быстрее. Но мы не ищем лёгких путей)))
Теперь у нас есть функция, которая позволяет разделить список на две части и функция слияния отсортированных списков. С их помощью реализуем функцию сортировки слиянием.
Сортировка слиянием для односвязного списка
Функция рекурсивно вызывает сама себя, передавая части списка. Если в функцию пришёл список длинной менее двух элементов, то рекурсия прекращается. Идёт обратная сборка списка. Сначала из двух списков, каждый из которых хранит один элемент, создаётся отсортированный список, далее из таких списков собирается новый отсортированный список, пока все элементы не будут включены.
void mergeSort(Node **head) < Node *low = NULL; Node *high = NULL; if ((*head == NULL) || ((*head)->next == NULL)) < return; >split(*head, &low, &high); mergeSort(&low); mergeSort(&high); merge(low, high, head); >
Если Вы желаете изучать этот материал с преподавателем, советую обратиться к репетитору по информатике
ru-Cyrl 18- tutorial Sypachev S.S. 1989-04-14 sypachev_s_s@mail.ru Stepan Sypachev students
Всё ещё не понятно? – пиши вопросы на ящик
Как отсортировать односвязный список си
Доброго времени суток!
Подскажите, пожалуйста, хороший алгоритм сортировки односвязного списка такого типа.
typedef struct _MY_LIST< struct _MY_LIST *Next; TCHAR *Data; >MY_LIST, *PMY_LIST;Желательно, с примерами на C.
Re: Сортировка односвязного списка.
| От: | CreatorCray |
| Дата: | 05.01.11 08:48 |
| Оценка: |
Здравствуйте, <Аноним>, Вы писали:
А>Подскажите, пожалуйста, хороший алгоритм сортировки односвязного списка такого типа.
У меня была специфическая задача, односвязный список указателей и надо было отсортировать его по значению указателя.
Идеально подошёл radix sort
Не уверен что подойдёт в твоем случае, т.к. без понятия как ты сравниваешь Data.
Re: Сортировка односвязного списка.
| От: | alpha21264 | |
| Дата: | 05.01.11 10:53 | |
| Оценка: | +2 | |
Здравствуйте, Аноним, Вы писали:
А>Доброго времени суток!
А>Подскажите, пожалуйста, хороший алгоритм сортировки односвязного списка такого типа.
1) Кладешь его в массив (адреса).
2) quicksort
3) Кладешь обратно в список (ссылки next)
Простите за пошлость.
Течёт вода Кубань-реки куда велят большевики.
Re: Сортировка односвязного списка.
| От: | WolfHound |
| Дата: | 05.01.11 22:01 |
| Оценка: |
Здравствуйте, <Аноним>, Вы писали:
А>Подскажите, пожалуйста, хороший алгоритм сортировки односвязного списка такого типа.
http://www.rsdn.ru/forum/cpp/926532.flat.aspx
Автор: boxter
Дата: 01.12.04
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re: Сортировка односвязного списка.
| От: | D14 | |
| Дата: | 06.01.11 16:00 | |
| Оценка: | -1 | |
Здравствуйте, Аноним, Вы писали:
А>Подскажите, пожалуйста, хороший алгоритм сортировки односвязного списка такого типа.
Да все тот же quicksort. По определению рекурсивнго quicksort’a
сортированный список суть =
сортированный список элементов только меньших медианы
конкатенация со списком, состоящим только из медианы
сортированный список элементов только больших медианы
А>Желательно, с примерами на C.
Готового нет, а расписывать лениво. Если особо не заморачиваться с median of free и.т.п., а взять медианой первый элемент, расколбасить список на два — больше и меньше медианы понятно как. Конкатенацию тоже можно проптимизировать, если прихранить указатель на хвост первого списка.
Re[2]: Сортировка односвязного списка.
| От: | Аноним |
| Дата: | 07.01.11 22:47 |
| Оценка: |
Здравствуйте, WolfHound, Вы писали:
WH>http://www.rsdn.ru/forum/cpp/926532.flat.aspx
Автор: boxter
Дата: 01.12.04
Понял. Всем большое спасибо.
Re[2]: Сортировка односвязного списка.
| От: | Pzz | https://github.com/alexpevzner |
| Дата: | 08.01.11 00:43 | |
| Оценка: |
Здравствуйте, D14, Вы писали:
D14>Да все тот же quicksort. По определению рекурсивнго quicksort’a
D14>сортированный список суть =
D14> сортированный список элементов только меньших медианы
D14> конкатенация со списком, состоящим только из медианы
D14> сортированный список элементов только больших медианы
Этот алкогоритм работает просто ужасно, если его просят отсортировать уже отсортированный список.
Re[3]: Сортировка односвязного списка.
| От: | Muxa |
| Дата: | 08.01.11 01:02 |
| Оценка: |
Pzz>Этот алкогоритм работает просто ужасно, если его просят отсортировать уже отсортированный список.
а вот нефиг сортировать такое!
Re[4]: Сортировка односвязного списка.
| От: | Pzz | https://github.com/alexpevzner |
| Дата: | 08.01.11 03:15 | |
| Оценка: |
Здравствуйте, Muxa, Вы писали:
Pzz>>Этот алкогоритм работает просто ужасно, если его просят отсортировать уже отсортированный список.
M>а вот нефиг сортировать такое!
Ну уж какое приходит, то и приходится сортировать. Предлагаешь сначала перемешать?
Re[3]: Сортировка односвязного списка.
| От: | McSeem2 | http://www.antigrain.com |
| Дата: | 08.01.11 04:19 | |
| Оценка: |
Здравствуйте, Pzz, Вы писали:
Pzz>Этот алкогоритм работает просто ужасно, если его просят отсортировать уже отсортированный список.
Так работает реализация из Кнута. Нормальная классическая имплементация K&R сортирует отсортированный список за O(N log N). Конечно же, можно подстроить ситуацию, когда будет N^2, но на реальных задачах вероятность этого не поддается измерению, даже на 1000 элементов. В общем, надо пережить много миллиардов Вселенных, чтобы такое хоть раз случилось, при условии, что каждый житель Земли каждую микросекунду запускает qsort на 1000 элементов.
У меня был прикол на предыдущей работе в J&J — там сделали именно Кнутовскую имплементацию, которая надолго зависала на отсортированных массивах и вызывала переполнение стэка. А такие иногда случались, ну или почти отсортированные. Так они тупо делали shuffle, на всякий случай, а потом сортировали ихним кривым квик сортом. LOL! При том, что классическая нерекурсивная имплементация K&R справляется с задачей на счет раз.
McSeem
Я жертва цепи несчастных случайностей. Как и все мы.
Re[2]: Сортировка односвязного списка.
| От: | McSeem2 | http://www.antigrain.com |
| Дата: | 08.01.11 04:25 | |
| Оценка: |
Здравствуйте, WolfHound, Вы писали:
А>>Подскажите, пожалуйста, хороший алгоритм сортировки односвязного списка такого типа.
WH>http://www.rsdn.ru/forum/cpp/926532.flat.aspx
Автор: boxter
Дата: 01.12.04
Ну, в качестве упражнения это безусловно прикольно. Но на практике гораздо эффективнее собрать массив указателей, дарбулызнуть по нему квик-сортом, после чего вытянуть обратно в список. Память — те же O(N), что и при Merge Sort. Но на практике может быть на порядок эффективнее.
McSeem
Я жертва цепи несчастных случайностей. Как и все мы.
Re[3]: Сортировка односвязного списка.
| От: | WolfHound |
| Дата: | 08.01.11 15:58 |
| Оценка: |
Здравствуйте, McSeem2, Вы писали:
MS>Ну, в качестве упражнения это безусловно прикольно. Но на практике гораздо эффективнее собрать массив указателей, дарбулызнуть по нему квик-сортом, после чего вытянуть обратно в список. Память — те же O(N), что и при Merge Sort. Но на практике может быть на порядок эффективнее.
Вобщето потребление памяти O(Log(N))
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[3]: Сортировка односвязного списка.
| От: | D14 |
| Дата: | 09.01.11 21:43 |
| Оценка: |
Здравствуйте, Pzz, Вы писали:
Pzz>Этот алкогоритм работает просто ужасно, если его просят отсортировать уже отсортированный список.
Есть подозрение, что сабжавая задачка имеет учебное приложение, потому и совет несколько академичен.
Для того, чтобы вел себя не так ужасно, можно пользоваться медианами из трех, из девяти и.т.д. Но надо иметь в виду, что проход по списку не самая дешовая операция. Ну, и коль уж зашла речь о почти отсортированном списке, мержд-сорт тут тоже не самый лучший вариант. Ну, и в общем случае наивная реализация мерджсорта мегарекурсивная не думаю, что сильно хороша. Мердж сорт стреляет на случаях, когда данные идут непрерывно друг за другом, а в данном случае можно обломаться, если сравнения дороги.
Re[4]: Сортировка односвязного списка.
| От: | LaptevVV |
| Дата: | 09.01.11 22:20 |
| Оценка: |
Здравствуйте, McSeem2, Вы писали:
MS>У меня был прикол на предыдущей работе в J&J — там сделали именно Кнутовскую имплементацию, которая надолго зависала на отсортированных массивах и вызывала переполнение стэка. А такие иногда случались, ну или почти отсортированные. Так они тупо делали shuffle, на всякий случай, а потом сортировали ихним кривым квик сортом. LOL! При том, что классическая нерекурсивная имплементация K&R справляется с задачей на счет раз.
И эти люди — считаются программистами! Блин, ну сколько же неучей в нашей сфере!