Сортировка односвязных списков

← →
Галинка © (2007-09-13 11:56) [0]

Возможно ли такое в принципе? Есть ли алгоритмы, типа пузырька?

← →
Игорь Шевченко © (2007-09-13 12:00) [1]

Возможно. Алгоритмы ищутся в Яндексе и в Гугле, по выбору

← →
Сергей М. © (2007-09-13 12:01) [2]

> типа пузырька

Пузырек-то как раз не подходит для этого.

Лучшим выбором при прочих равных условиях будет, пожалуй, сортировка слиянием:
http://algolist.ncstu.ru/sort/merge_sort.php

← →
clickmaker © (2007-09-13 12:02) [3]

http://algolist.manual.ru/ds/basic/simple_list.php

← →
Eraser © (2007-09-13 12:02) [4]

> Галинка © (13.09.07 11:56)

Алгоритмов сортировки довольно много, им, по-сути, всё равно с каким списком работать, может вообще с массивом, реализация перестановки значений дело разработчика.

← →
Сергей М. © (2007-09-13 12:10) [5]

> Галинка © (13.09.07 11:56)

Собссно Eraser © верно заметил - выбор алгоритма должен осуществляться, в первую очередь, исходя из содержимого списка, а не из метода доступа к его элементам.

Для адаптации любого алгоритма к условиям связности списка в общем случае достаточно проиндексировать этот список - результирующий связный список индексов будет выступать посредником между алгоритмом сортировки и оригинальным списком.

← →
iam (2007-09-13 12:11) [6]

ты смотри, может в твоё конкретном случае можно вообще на основе списка создать одномерный массив, его отсортировать quick sort и потом на основе массива подправить у узлов списка их данные

← →
Галинка © (2007-09-13 12:32) [7]

У меня нет конкретного случая. Я просто изучаю новый язык. И его методы и алгоритмы. С массивами более менее понятно, а вот со списками придеться разбираться.

← →
Сергей М. © (2007-09-13 12:40) [8]

> изучаю новый язык. И его .. алгоритмы

Что это за язык ? И как алгоритмы работы языковых конструкций этого языка (1) связаны с интересующими тебя алгоритмами (2) ?

← →
Anatoly Podgoretsky © (2007-09-13 12:41) [9]

> Галинка (13.09.2007 12:32:07) [7]

Алгоритмы сортировки не зависят от языка и они основаны на настолько тривиальных методах, что могут быть легко реализованы на любом языке.

← →
Algol (2007-09-13 12:54) [10]

> Пузырек-то как раз не подходит для этого.

По-моему как раз наоборот... Пузырек легко реализуется на списке.

типа такого

bool found;
do
{
found = false;
Item item = list.first;
while(item!=null && item.next!=null)
{
if(item.value>item.next.value)
{
object temp = item.value;
item.value = item.next.value;
item.next.value = temp;
found = true;
}
item = item.next;
}
}while(found);

← →
iam (2007-09-13 13:01) [11]

Algol (13.09.07 12:54) [10]
зачем уж код сразу писать)
достаточно было сказат ьчто пузырёк удобен потому что переставляет соседние элементы и достаточно проходить список держа указатель на предыдущий и последующий узлы)

← →
tesseract © (2007-09-13 13:10) [12]

Я за слияние, ну или qsort :-)

← →
Anatoly Podgoretsky © (2007-09-13 13:19) [13]

> Algol (13.09.2007 12:54:10) [10]

Структура данных слабо влияет на алгоритм, достаточно абстрагироваться.

← →
Галинка © (2007-09-13 14:19) [14]

Надо учиться абстрагироваться. )) Я думала, что можно только с адресами играть. Т.е. можно узбежать Item temp. Но вероятно нельзя.

← →
Сергей М. © (2007-09-13 14:22) [15]

> Галинка © (13.09.07 14:19) [14]

А чем тебя индексация не устраивает ?

← →
iam (2007-09-13 14:22) [16]

Удалено модератором

← →
iam (2007-09-13 14:31) [17]

Галинка © (13.09.07 14:19) [14]
ну вот смотри
возьмём платформу .NET на которой ты писала до некоторого времени
каждый узел пусть представлен классом в котором есть свойство Next типа этого же класса которое указывает на следующий узел
ты можешь просто пробежать по этому связному списку и закинуть каждый узел в тот же ArrayList, потом написать метод сравнения узлов для метода ArrayList.Sort, выполнить сортировку и затем пробегаясь по ArrayList от начала до конца просто делать типа arrList[i].Next = arrList[i+1]
от тебя не требуется знать тут никаких алгоритмов сортировки

← →
Галинка © (2007-09-13 14:32) [18]

Сергей М. © (13.09.07 14:22) [15]

почему не устраивает? Просто я учу сейчас списки. И все что с ними можно делать. Массивы будут потом.

← →
Сергей М. © (2007-09-13 14:36) [19]

> Галинка © (13.09.07 14:32) [18]

> я учу сейчас списки

Ну и учи себе на здоровье, кто ж мешает ?)

Индексация тому только подспорье, уж никак не помеха ..

← →
iam (2007-09-13 14:37) [20]

Галинка © (13.09.07 14:32) [18]
могу подсказать книгу на инглише по алгоритмам на C#

← →
Галинка © (2007-09-13 14:37) [21]

iam (13.09.07 14:31) [17]

я не против. Но сейчас мне надо без всяких платформ. Просто чистый Си. Как когда-то паскаль. Только в паскале я со списками разбираться не стала, потому как их не использовала. А теперь вот решила, что надо бы разобраться.

И вот еще вопрос. На посоветованной странице приведен пример кода конечно на паскале. Но смущает то, что в книгах, оторые у меня, если используются указатели, то всегда есть явная инициализация с выделением памяти. А в примерах просто дерларация и сразу использование. Это зависит от компилятора или все же лучше всегда использовать явное выделение памяти под указатель на структуру?

← →
iam (2007-09-13 14:46) [22]

Галинка © (13.09.07 14:37) [21]
зачем тебе думать об указателяъ если ты пишешь на C#
есть ссылочные переменные есть переменные-значения
забудь об указателях, это прошлый век)

← →
clickmaker © (2007-09-13 14:49) [23]

> А в примерах просто дерларация и сразу использование

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

← →
Галинка © (2007-09-13 14:49) [24]

iam (13.09.07 14:46) [22]

Третий раз в этом топике говорю, я пишу сейчас на чистом СИ. Даже без ++. )) Еще есть вопросы? Но за помощь все равно спасибо.

← →
iam (2007-09-13 14:53) [25]

Галинка © (13.09.07 14:49) [24]
без C++? отсюда вытекает что в читаем тобой книгах и речи не может идти об классе бинарного дерева, классе связного списка...потому что только C++ объектно-ориентированный
странно это)можно конечно и в процедурном стиле всё это делать, но так уже никто не делает...

← →
Галинка © (2007-09-13 14:55) [26]

Сергей М. © (13.09.07 14:36) [19]

можно подробнее про индексацию списков?

← →
Сергей М. © (2007-09-13 14:57) [27]

> пишу сейчас на чистом СИ

В Сишной-спецификации, равно как и в спецификации любого другого языка, думаю, обязательно фигурирует комментарии по поводу инициализации тех или иных данных, предусмотренных спецификацией. Любой компилятор обязан соблюдать требования спецификации, иначе он нафих никому не нужен будет.

От этого и отталкивайся.

← →
Галинка © (2007-09-13 14:58) [28]

iam (13.09.07 14:53) [25]

в книге есть бинарные деревья. А классов вот нет. Но есть структуры.

← →
TUser © (2007-09-13 15:01) [29]

Цифровая сортировка намного быстрее пузырька и хорошо годится для списков.

← →
Сергей М. © (2007-09-13 15:01) [30]

> Галинка © (13.09.07 14:55) [26]

Все просто - за один проход по исходному списку формируешь массив (или связный список) указателей на элементы исходного списка. Алгоритм сортировки при этом оперирует не исходным списком, а списком-индексом, получая возможность быстрого произвольного доступа к элементам исх.списка по их индексам в индексном списке.

← →
tesseract © (2007-09-13 15:03) [31]

> Цифровая сортировка намного быстрее пузырька и хорошо годится
> для списков.

Любая сортировка на массиве > 100 быстрее пузырька.

← →
Anatoly Podgoretsky © (2007-09-13 15:06) [32]

> tesseract (13.09.2007 15:03:31) [31]

И на связаном списке?

← →
iam (2007-09-13 15:08) [33]

не обижайте пузырька
пузырь самый быстрый алгоритм сортировки на полностью упорядоченных массивах)))

← →
tesseract © (2007-09-13 15:10) [34]

> И на связаном списке?

Так qsort за много меншье проходов сделает. Связный список лучше сильно не елозить - тормозит.

← →
iZEN © (2007-09-13 15:11) [35]

Время блокировки операции перестановки у "пузырька" меньше (хотя сумарное больше). Сортируемый им массив всегда частично упорядочен, что выгодно отличает его от других методов в многопоточной среде.

← →
tesseract © (2007-09-13 15:17) [36]

> Сортируемый им массив всегда частично упорядочен,

Ну двоичные деревья вообще всегда упорядочены.

> Время блокировки операции перестановки у "пузырька" меньше
> (хотя сумарное больше).

Переставка вроде суммарно эффективнее пузырька. Я имею в виду затраты на n-ое количество проходов по списку - а оно в разы больше проходов по массиву.

← →
Галинка © (2007-09-13 15:42) [37]

а что лучше, завести несколько переменных (как в сортировке выборкой или вставками) но вроде короче цикл; или обходиться двумя переменными, но долго перебирать?

← →
Anatoly Podgoretsky © (2007-09-13 15:44) [38]

> tesseract © (13.09.07 15:10) [34]

Это точно, только заколебается извлекать нужный элемент из списка для сравнения и перестановки.

← →
Сергей М. © (2007-09-13 15:45) [39]

> Галинка © (13.09.07 15:42) [37]

> а что лучше

Что значит "лучше" ?

> завести несколько переменных

Заводят вообще-то хомячков, бобиков-мурок, слонов-крокодилов, тараканов в конце-концов)

А переменные декларируют (объявляют, если так понятней по рабоче-крестьянски)

← →
tesseract © (2007-09-13 15:48) [40]

> а что лучше, завести несколько переменных (как в сортировке
> выборкой или вставками) но вроде короче цикл; или обходиться
> двумя переменными, но долго перебирать?

Кнут вроде рекомендует заводить вспомогательный массив как раз для ускорения доступа к элементам массива.

← →
Галинка © (2007-09-13 15:51) [41]

Я имею в виду, что экономнее/быстрее/удобнее использовать несколько переменных и мало проходов цикла, или одну переменную и много проходов цикла?

← →
Галинка © (2007-09-13 15:53) [42]

tesseract © (13.09.07 15:48) [40]

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

← →
clickmaker © (2007-09-13 15:56) [43]

> экономнее/быстрее/удобнее

эти три понятия мало сочетаются друг с другом
везде разумный компромисс нужен

← →
Галинка © (2007-09-13 16:07) [44]

Хэширование это из этой же оперы?

← →
clickmaker © (2007-09-13 16:10) [45]

> [44] Галинка © (13.09.07 16:07)

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

← →
Галинка © (2007-09-13 16:13) [46]

Если кто-то может показать пример с использование массива ссылок на элементы массива буду очень благодарна.

← →
iam (2007-09-13 16:17) [47]

Галинка © (13.09.07 16:13) [46]
объясни подробней what you want)

← →
Sandman31 (2007-09-13 16:21) [48]

clickmaker © (13.09.07 15:56) [43]

"Быстро, дешево, хорошо - выберите любые два" :)

← →
Eraser © (2007-09-13 16:37) [49]

> Галинка © (13.09.07 16:13) [46]

http://www.natahaus.ru/2005/11/08/fundamentalnye_algoritmy_i_struktury_dannyh_v_delphi.html

← →
Сергей М. © (2007-09-13 16:38) [50]

> Галинка © (13.09.07 16:13) [46]

А что непонятно ?

> массива ссылок на элементы массива

Массива ссылок на элементы списка !

ты же о списке ведешь речь)

Сергей М. © (13.09.07 16:39) [51]

Объяснить подробней можно? Или статью какую почитать, где человеческим языком с примером (для домохозяек) написано?

Хочешь освоить список?
http://www.delphimaster.ru/articles/dsort/index.html
:-P

> Галинка © (13.09.07 16:47) [52]

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

Zeqfreed © (13.09.07 16:55) [54]

Пасиб. А как организуется массив ссылок на элементы массива? И как быть, если список часто меняется? Все время актуализировать массив? И сколько под него выделять памяти? Или всегда с запасом, а использовать только столько, сколько надо?

> Объяснить подробней можно?

Объяснить что ?

Давай уже подробно, в порядке следования "непониманий", от простого к сложному ..

> Галинка © (13.09.07 17:01) [55]

Массив строится тогда, когда он нужен. Разумеется, он должен отражать актуальное состояние списка для корректных результатов. Все зависит от задачи. Если доступ по индексу нужен все время, то удобней, видимо, будет обновлять массив при каждой модификации списка. А если только для сортировки, то хватит и временного массива.

Есть список из структур struct node{int val; struct node *next} (в соответствие со связанным хранением). Значения полей val структур в списке, например {5, 7, 4, 6, 3, 9, 8, 2, 1}. Как создать ("ключевой") массив? И как ждементы массива будут собственно связаны с узлами списка?

> Как создать ("ключевой") массив? И как ждементы массива
> будут собственно связаны с узлами списка?

Ссылки на узлы списка в массиве будут. Это же базовая алгоритмика первого курса!!!!!

Дешево/Хорошо/Быстро

Выберите любые два

> Галинка © (13.09.07 17:10) [59]

Ну, вероятно, выделить память под него. И пройдя в цикле по списку заполнить массив.

> Как создать ("ключевой") массив? И как ждементы массива
> будут собственно связаны с узлами списка?

Каждый элемент массива должен содержать указатель на соотв.структуру node, т.е. элементы массива должны иметь указательный тип.

Для получения доступа к соотв. элементу ориг.списка из процедуры сортировки нужно просто разыменовать соотв. ему указатель из этого массива.

т.е. получится что-то типа struct node *keys[100], и соответственно:
struct node *start; //ссылка на начало списка struct node *keys[100]; //массив ссылок на элементы списка struct node *list = start; int j, i = 0; while (list != NULL){ keys[i] = list; list = list->next; i++; } // заполнение массива ссылок
а как теперь с сортировкой?

#include <stdio.h> #include <stdlib.h> #define RANDOM_RANGE(a, b) 1 + (int) (b * (rand() / (RAND_MAX + a))) struct Node { int value; struct Node *next; }; static struct Node head = {0, 0}; static int len = 0; static void append(int value) { int i = len; struct Node *node = &head; struct Node *new = (struct Node *) malloc(sizeof(struct Node)); while (i--) node = node->next; new->value = value; new->next = 0; node->next = new; len++; } static void sort() { struct Node **els = malloc(sizeof(struct Node) * len); struct Node *node = &head; int i = 0; while (node = node->next) els[i++] = node; int swapped = 1; struct Node *tmp; while (swapped) { swapped = 0; for (i = 1; i < len; i++) { if (els[i - 1]->value > els[i]->value) { tmp = els[i]; els[i] = els[i - 1]; els[i - 1] = tmp; swapped = 1; } } } printf("sorted: "); for (i = 0; i < len; i++) printf("%d ", els[i]->value); printf("\n"); } int main(int argc, char **argv) { srand(time(0)); int i = 10; while (i--) append(RANDOM_RANGE(0.0, 100.0)); sort(); struct Node *node = &head; printf("original: "); while (node = node->next) printf("%d ", node->value); printf("\n"); return 0; }

Спасибо. Попробую. Почитаю.

← →
iam (2007-09-14 10:10) [67]

using System; using System.Collections.Generic; using System.Text; namespace ConsoleApplication1 { class Program { static void Main(string[] args) { //формирование связного списка LinkedList<Person> linkedList = new LinkedList<Person>(); linkedList.AddLast(new Person(3, "Петя", "Петечкин")); linkedList.AddLast(new Person(2, "Вася", "Васечкин")); linkedList.AddLast(new Person(1, "Гоша", "Гошечкин")); //отображение содержимого связного списка LinkedListNode<Person> node = linkedList.First; while (node != null) { Console.WriteLine(node.Value.ToString()); node = node.Next; } Console.WriteLine(); //формирование обычного списка на основе связного и его сортировка на основе //функции сравнения представляемой классом PersonComparer List<Person> list = new List<Person>(); foreach (Person p in linkedList) list.Add(p); list.Sort(new PersonComparer()); //очистка и затем заполнение связного списка из отсортированного обычного списка linkedList.Clear(); foreach (Person p in list) linkedList.AddLast(p); //отображение содержимого связного списка foreach (Person p in linkedList) { Console.WriteLine(p.ToString()); } Console.ReadLine(); } } public class Person { public Person(int id, string firstName, string lastName) { this.id = id; this.firstName = firstName; this.lastName = lastName; } public int id; public string firstName; public string lastName; public override string ToString() { return id.ToString() + " " + firstName + " " + lastName; } } public class PersonComparer : IComparer<Person> { public int Compare(Person person1, Person person2) { if (person1.id < person2.id) return -1; if (person1.id > person2.id) return 1; return 0; } } }
вот тебе ещё пример;)

> [67] iam (14.09.07 10:10)

щас будет
"Четвертый раз в этом топике говорю, я пишу сейчас на чистом СИ!!! Даже без ++."
:)

← →
iam (2007-09-14 10:25) [69]

clickmaker © (14.09.07 10:17) [68]
и она походу этим гордится)))
я ей тем более предложил книгу по алгоритмам и структурам данных на C#
отказалась почему-то) ну хочет возиться с C пусть возится)
"чистый Си" звучит прямо с какой-то гордостью у неё;)

> "чистый Си" звучит прямо с какой-то гордостью у неё;)

Лаба такая.

> tesseract (14.09.2007 12:53:10) [70]

Карма

Шеф сказал, что на простом Си. Без объектов. Тем более что проект ведется с 2001 года. Работает туева хуча людей. И что им теперь всем на шарп переходить? Да еще и винду в кассы засовывать?

iam, в шарпе я пользовала ArrayList. Это и список и массив одновременно. Т.е. обладает свойствами и того и другого. Там вообще было все просто, там был Sort. И я его успешно применяла. Но теперь нет ни шарпа, ни даже ООП.

Спасибо Zeqfreed © (13.09.07 17:46) [65]. Разобралась вроде.

Сортировка односвязных списков Найти похожие ветки