void QuickSort( Node **pbeg, Node **pend )
{
//голова и хвост списка соотвественно
if( (*pbeg) == (*pend) )
return;
//дно рекурсии
Node *sup = (*pbeg); //Опорный элемент
Node *current = (*pbeg)->next;
//текущий элемент
Node *help = current;
//Вспомогательный
while( current != (*pend) )
{
//пока не достигнут конец списка
help = current;
current = current->next;
if( maximum( sup, help ) == sup )
//Функция maximum( sup, help ) возвращает больший из переданных элементов, т.е. если help меньше опорного
transfer_elem( sup, help, pbeg, pend );
//...вставляем help перед опорным
}
QuickSort( pbeg, &sup );
//вызываем тоже самое для левой части
QuickSort( &sup, pend );
//Для правой части
Алгоритм быстрой сортировки на связном списке
Здравствуйте уважаемые форумчане.
Задача: отсортировать связный список именно быстрой сортировкой, причем функция должна быть именно рекурсивной.
Мои наброски вот:
Что не так? - через N(причем N никак не зависит от длинны списка) шагов функция выдает ошибку ошибку сегментации.
Подскажите пожалуйста как необходимо исправить функцию, чтобы она корректно сортировала весь список.
Задача: отсортировать связный список именно быстрой сортировкой, причем функция должна быть именно рекурсивной.
Мои наброски вот:
Код:
Что не так? - через N(причем N никак не зависит от длинны списка) шагов функция выдает ошибку ошибку сегментации.
Подскажите пожалуйста как необходимо исправить функцию, чтобы она корректно сортировала весь список.
ide не показывает стэк вызова функций или строчку,в которой была ошибка сегментации?
Ругается при присвоении опорного элемента в этой строке
Цитата:
Node *sup = (*pbeg);
что за ошибка?что при этом лежит в pbeg?какая структура у Node?можно вообще весь код программы увидеть?
Alm3n, я ж писал в стартовом посте что ошибка сегментации(Segmentation faul). Что в pbeg при этом отследить не могу, т.к. рекурсия вызывается большее количество раз чем расчетное(на бумаге), на много больше, причем дно вообще достигается.
Исходник прикрепляю к посту.
Исходник прикрепляю к посту.
опорный элемент не нужно передавать снова в функцию
Цитата: Alm3n
опорный элемент не нужно передавать снова в функцию
Почему? Как тогда рекурсивно упорядочивать элементы, лежащие слева и справа от него?
Не очень понял, как приведенный код должен работать.
На мой взгляд нужно примерно так:
P.S Тестировать это мне лениво, так что могут быть мелкие ошибки.
На мой взгляд нужно примерно так:
Код:
void QuickSort( Node*& pbeg, Node*& pend )
{
if ( pbeg == pend )
return;
Node *sup = pbeg;
Node *left = pbeg;
Node *right = pend;
while( left != right )
{
while (left != sup && maximum(left, sup)==sup ) left = left->next;
while (right != sup && maximum(right, sup)==right ) right = right->prev;
if (left == right) break;
Node* o = left->next;
transfer_elem(right, left, pbeg, pend);
transfer_elem(leftNext, right, pbeg, pend);
o = left;
left = right;
right = o;
if (left != sup) left = left->next;
if (right != sup) right = right->prev;
}
if (pbeg!=sup) QuickSort( pbeg, sup->prev );
if (pend!=sup) QuickSort( sup->next, pend );
}
{
if ( pbeg == pend )
return;
Node *sup = pbeg;
Node *left = pbeg;
Node *right = pend;
while( left != right )
{
while (left != sup && maximum(left, sup)==sup ) left = left->next;
while (right != sup && maximum(right, sup)==right ) right = right->prev;
if (left == right) break;
Node* o = left->next;
transfer_elem(right, left, pbeg, pend);
transfer_elem(leftNext, right, pbeg, pend);
o = left;
left = right;
right = o;
if (left != sup) left = left->next;
if (right != sup) right = right->prev;
}
if (pbeg!=sup) QuickSort( pbeg, sup->prev );
if (pend!=sup) QuickSort( sup->next, pend );
}
P.S Тестировать это мне лениво, так что могут быть мелкие ошибки.
Цитата: Apach47
Почему? Как тогда рекурсивно упорядочивать элементы, лежащие слева и справа от него?
а в чем проблема?рекурсивно передавай в функции постоянно новые границы подмассивов,которые будут уменьшаться в размере на еденицу.вероятно, неправильно написана функция transfer_elem,я ее не особо смотрел.но,после того,как ты выбрал опорный элемент,подмассивы должны обрастать с двух его сторон.
Alm3n, transfer_elem() нормально работает. Я ее тестировал при сортировки вставками. Тут, в моей модификации алгоритма, принцип такой же.
Alm3n,P*t*, спасибо. Сейчас сам еще подумаю)) Если что-то получиться - выложу свой код в топике.
Alm3n,P*t*, спасибо. Сейчас сам еще подумаю)) Если что-то получиться - выложу свой код в топике.
я не имел в виду,что она работает с ошибками,она работает неправильно.при передаче подмассива во вторую функцию почему-то передается и опорный элемент,чего быть не должно.
Посмотрел еще раз твой код.
1) почему в цикле while не обрабатывается последний элемент pend?
2) Alm3n правильно говорит - надо заменить
на
Допустим у тебя остался список из двух элементов (Е1 и Е2).
Тогда исходный вызов - (Е1, Е2), а рекурсивные вызовы - (E1, E1) и (E1, E2). Видно что второй из них зацикливается.
1) почему в цикле while не обрабатывается последний элемент pend?
2) Alm3n правильно говорит - надо заменить
Код:
QuickSort( pbeg, &sup );
QuickSort( &sup, pend );
QuickSort( &sup, pend );
на
Код:
if ((*pbeg)!=sup) QuickSort( pbeg, &sup->prev );
if ((*pend)!=sup) QuickSort( &sup->next, pend );
if ((*pend)!=sup) QuickSort( &sup->next, pend );
Допустим у тебя остался список из двух элементов (Е1 и Е2).
Тогда исходный вызов - (Е1, Е2), а рекурсивные вызовы - (E1, E1) и (E1, E2). Видно что второй из них зацикливается.
P*t*, большое спасибо, разобрался.
Как и обещал выкладываю рабочую функцию для быстрой сортировки связного списка
Буду раз если он кому-то пригодится :)
Как и обещал выкладываю рабочую функцию для быстрой сортировки связного списка
Код:
void QuickSort( Node **pbeg, Node **pend )
{
if( (*pbeg) == (*pend) )
return;
Node *sup = (*pbeg);
//Опорный элемент
Node *current = (*pbeg)->next;
//Первый за опорным
Node *help = current;
//Вспомогательный элемент
while( current != (*pend)->next )
{
//Пока текущий не вышел за границы массива
help = current;
current = current->next;
//Очень наглядно эти две иструкции выглядят на схеме(нарисаовать самостоятельно)
if( maximum( sup, help ) == sup )
//Если текущий меньше опорного
transfer_elem( sup, help, pbeg, pend );
//Вставить его перед опорным
}
if( (*pbeg) != sup )
//Если в левой части списка осталось больше одного элемента
QuickSort( pbeg, &(sup->prev) );
if( (*pend) != sup )
//Если в правой части списка осталось больше одного элемента
QuickSort( &(sup->next), pend );
}
{
if( (*pbeg) == (*pend) )
return;
Node *sup = (*pbeg);
//Опорный элемент
Node *current = (*pbeg)->next;
//Первый за опорным
Node *help = current;
//Вспомогательный элемент
while( current != (*pend)->next )
{
//Пока текущий не вышел за границы массива
help = current;
current = current->next;
//Очень наглядно эти две иструкции выглядят на схеме(нарисаовать самостоятельно)
if( maximum( sup, help ) == sup )
//Если текущий меньше опорного
transfer_elem( sup, help, pbeg, pend );
//Вставить его перед опорным
}
if( (*pbeg) != sup )
//Если в левой части списка осталось больше одного элемента
QuickSort( pbeg, &(sup->prev) );
if( (*pend) != sup )
//Если в правой части списка осталось больше одного элемента
QuickSort( &(sup->next), pend );
}
Буду раз если он кому-то пригодится :)