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

← →
Галинка © (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]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

> а что лучше

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

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

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

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

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

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

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