Является ли сортировка связанного списка с использованием Quicksort по-настоящему медленнее, чем Mergesort из-за отсутствия произвольного доступа в Linked List?

Question

От http://www.geeksforgeeks.org/merge-sort-for-linked-list/

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

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

В быстрой сортировке:

Выбор шарнира требует произвольного доступа, и должен перебирать связанный список (O (N) на рекурсию).

Разметка может быть сделано с помощью левой направо способ развертки (который не требует произвольного доступа):

В Merge Sort:

Split в середине требует произвольного доступа и потребности для итерации по связанному списку (с использованием механизма быстрого замедления) (O (n) для каждой рекурсии).

Слияние может осуществляться с помощью поворота влево-вправо (что не требует произвольного доступа).

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

Я что-то упустил?

РЕДАКТИРОВАТЬ: Я смотрю на функцию перегородки, где pivot является последним элементом, и мы последовательно переходим от lwft. Если раздел работает по-разному (т. Е. Ось находится в середине и вы поддерживаете два указателя на каждом конце), он все равно будет работать нормально, если связанный список дважды связан ...

Answer 1

Вы можете разбить список на элемент поворота в линейном время, использующее постоянную дополнительную память (даже если это довольно сложно реализовать для односвязного списка), поэтому она будет иметь такую ​​же сложность по времени, как и сортировка слияния в среднем (хорошее мнение о сортировке слияния состоит в том, что в худшем случае это O(N log N)). Таким образом, они могут быть одинаковыми с точки зрения асимптотического поведения.

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

Однако раздел, который использует случайный стержень, довольно беспорядок для односвязного списка (возможно, но метод, который я могу думать, имеет большую константу, чем просто получение двух половин для сортировки слияния). Использование первого или последний элемент, как стержень имеет очевидный вопрос: он работает в O(N^2) для отсортированных (или почти отсортированных) списков. Принимая это во внимание, я бы сказал, что сортировка слияния будет более разумным выбором в большинстве случаев.

Answer 2

Как уже указывалось, если используются одиночные связанные списки, сортировка слияния и быстрая сортировка имеют одинаковое среднее время работы: O(n logn).

Я не уверен на 100%, какой алгоритм разбивки вы имеете в виду, но один алгоритм, который я могу подобрать, удалит текущий элемент из списка, если он больше, чем элемент поворота, и вставьте его в конец списка. Для внесения этого изменения необходимы, по крайней мере 3 операции:

1. ссылка родительского элемента должна быть изменена
2. связи последнего элемента должен быть изменен
3. он должен быть обновлен, который является последним элемент

Однако это должно быть сделано только в 50% случаев, поэтому в среднем 1,5 изменения на элемент во время функции перегородки.

С другой стороны, во время функции слияния. Прибл. 50% случаев, два последовательных элемента в связанном списке из одного и того же исходного связанного списка -> нечего делать, потому что эти элементы уже связаны. В другом случае нам нужно изменить ссылку - на другую часть списка. В среднем, 0,5 изменения на элемент для функции слияния.

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

Answer 3

Для связанных списков существует итеративная нижняя версия слияния, которая не сканирует списки для их разделения, что позволяет избежать проблемы медленного произвольного доступа. Сортировка слияния снизу вверх для связанного списка использует небольшой (от 25 до 32) массив указателей на узлы. Сложность времени - O (n log (n)), а сложность пространства - O (1) (массив от 25 до 32 указателей на узлы).

На этой веб-странице

http://www.geeksforgeeks.org/merge-sort-for-linked-list

Я отправил несколько комментариев, в том числе ссылки на рабочий пример снизу вверх сортировки слиянием для связанного списка, но не получил ответа от этой группы. Ссылка на рабочий пример, используемый для этого веб-сайта:

http://code.geeksforgeeks.org/Mcr1Bf

Как для быстрой сортировки без случайного доступа, первый узел может быть использован в качестве опоры. Три списка будут созданы, один список для узлов < pivot, один список для узлов == pivot, один список для узлов> pivot. Рекурсия будет использоваться в двух списках для узлов! = Pivot. Это имеет худшую временную сложность O (n^2) и худшую сложность стекового пространства O (n). Стека сложность может быть уменьшена до O (Log (N)), используя только рекурсии на более короткий список с узлами! = Стержень, а затем цикл обратно, чтобы отсортировать более длинный список, используя первый узел длинного списка в качестве нового поворота , Слежение за последним узлом в списке, например, с использованием указателя хвоста на круговой список, позволит быстро конкатенацию двух других списков. Худшая временная сложность остается на O (n^2).

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

Пример C код:

#include <stdio.h> 
#include <stdlib.h> 

typedef struct NODE_{ 
struct NODE_ * next; 
int data; 
}NODE; 

/* merge two already sorted lists     */ 
/* compare uses pSrc2 < pSrc1 to follow the STL rule */ 
/* of only using < and not <=      */ 
NODE * MergeLists(NODE *pSrc1, NODE *pSrc2) 
{ 
NODE *pDst = NULL;   /* destination head ptr */ 
NODE **ppDst = &pDst;  /* ptr to head or prev->next */ 
    if(pSrc1 == NULL) 
     return pSrc2; 
    if(pSrc2 == NULL) 
     return pSrc1; 
    while(1){ 
     if(pSrc2->data < pSrc1->data){ /* if src2 < src1 */ 
      *ppDst = pSrc2; 
      pSrc2 = *(ppDst = &(pSrc2->next)); 
      if(pSrc2 == NULL){ 
       *ppDst = pSrc1; 
       break; 
      } 
     } else {      /* src1 <= src2 */ 
      *ppDst = pSrc1; 
      pSrc1 = *(ppDst = &(pSrc1->next)); 
      if(pSrc1 == NULL){ 
       *ppDst = pSrc2; 
       break; 
      } 
     } 
    } 
    return pDst; 
} 

/* sort a list using array of pointers to list  */ 
/* aList[i] == NULL or ptr to list with 2^i nodes */ 

#define NUMLISTS 32    /* number of lists */ 
NODE * SortList(NODE *pList) 
{ 
NODE * aList[NUMLISTS];   /* array of lists */ 
NODE * pNode; 
NODE * pNext; 
int i; 
    if(pList == NULL)   /* check for empty list */ 
     return NULL; 
    for(i = 0; i < NUMLISTS; i++) /* init array */ 
     aList[i] = NULL; 
    pNode = pList;    /* merge nodes into array */ 
    while(pNode != NULL){ 
     pNext = pNode->next; 
     pNode->next = NULL; 
     for(i = 0; (i < NUMLISTS) && (aList[i] != NULL); i++){ 
      pNode = MergeLists(aList[i], pNode); 
      aList[i] = NULL; 
     } 
     if(i == NUMLISTS) /* don't go beyond end of array */ 
      i--; 
     aList[i] = pNode; 
     pNode = pNext; 
    } 
    pNode = NULL;   /* merge array into one list */ 
    for(i = 0; i < NUMLISTS; i++) 
     pNode = MergeLists(aList[i], pNode); 
    return pNode; 
} 

/* allocate memory for a list */ 
/* create list of nodes with pseudo-random data */ 
NODE * CreateList(int count) 
{ 
NODE *pList; 
NODE *pNode; 
int i; 
int r; 
    /* allocate nodes */ 
    pList = (NODE *)malloc(count * sizeof(NODE)); 
    if(pList == NULL) 
     return NULL; 
    pNode = pList;     /* init nodes */ 
    for(i = 0; i < count; i++){ 
     r = (((int)((rand()>>4) & 0xff))<< 0); 
     r += (((int)((rand()>>4) & 0xff))<< 8); 
     r += (((int)((rand()>>4) & 0xff))<<16); 
     r += (((int)((rand()>>4) & 0x7f))<<24); 
     pNode->data = r; 
     pNode->next = pNode+1; 
     pNode++; 
    } 
    (--pNode)->next = NULL; 
    return pList; 
} 

#define NUMNODES (1024)   /* number of nodes */ 
int main(void) 
{ 
void *pMem;      /* ptr to allocated memory */ 
NODE *pList;     /* ptr to list */ 
NODE *pNode; 
int data; 

    /* allocate memory and create list */ 
    if(NULL == (pList = CreateList(NUMNODES))) 
     return(0); 
    pMem = pList;    /* save ptr to mem */ 
    pList = SortList(pList); /* sort the list */ 
    data = pList->data;   /* check the sort */ 
    while(pList = pList->next){ 
     if(data > pList->data){ 
      printf("failed\n"); 
      break; 
     } 
    } 
    if(pList == NULL) 
     printf("passed\n"); 
    free(pMem);     /* free memory */ 
    return(0); 
}