Mergeți Sortați o listă conectată

De curând, mi-am periat câteva fundamente și mi-am dat seama că îmbinarea unei liste de linkuri este o provocare destul de bună. Dacă aveți o bună implementare, atunci arătați-o aici.

0
fr hi bn
adăugat autor Angus Johnson, sursa

12 răspunsuri

Puteți utiliza acea implementare a sortimentului de îmbinare și puteți scrie propriile funcții pentru a interfața cu lista asociată ca și cum ar fi o matrice.

0
adăugat
public int[] msort(int[] a) {
    if (a.Length > 1) {
        int min = a.Length/2;
        int max = min;

        int[] b = new int[min];
        int[] c = new int[max];//dividing main array into two half arrays
        for (int i = 0; i < min; i++) {
            b[i] = a[i];
        }

        for (int i = min; i < min + max; i++) {
            c[i - min] = a[i];
        }

        b = msort(b);
        c = msort(c);

        int x = 0;
        int y = 0;
        int z = 0;

        while (b.Length != y && c.Length != z) {
            if (b[y] < c[z]) {
                a[x] = b[y];
                //r--
                x++;
                y++;
            } else {
                a[x] = c[z];
                x++;
                z++;
            }
        }

        while (b.Length != y) {
            a[x] = b[y];
            x++;
            y++;
        }

        while (c.Length != z) {
            a[x] = c[z];
            x++;
            z++;
        }
    }

    return a;
}
0
adăugat
Cred că acest 1 este perfect !!!!!!!!!!
adăugat autor Pramod, sursa
Mai întâi de toate, răspunsul dvs. nu se potrivește nicăieri cu întrebarea OP. În al doilea rând, nu sunteți sigur, care sunt comentariile dvs.?
adăugat autor Ravi, sursa

Am fost obsedat de optimizarea dezordinirii pentru acest algoritm și de mai jos este ceea ce am ajuns în sfârșit la. O mulțime de alte coduri pe Internet și StackOverflow este rău rău. Există oameni care încearcă să obțină punctul central al listei, fac recursivitate, au mai multe bucle pentru stânga peste noduri, menținând numărul de tonuri de lucruri - TOATE care nu sunt necesare. MergeSort se potrivește în mod natural cu lista de legături, iar algoritmul poate fi frumos și compact, dar nu este banal să ajungeți la acea stare.

Codul de mai jos menține numărul minim de variabile și are un număr minim de pași logici necesari algoritmului (adică fără a face codul imposibil de citit/citit) din câte știu. Cu toate acestea nu am încercat să minimizez LOC și să păstrez cât mai mult spațiu alb necesar pentru a păstra lucrurile ușor de citit. Am testat acest cod prin teste unitare destul de riguroase.

Rețineți că acest răspuns combină câteva tehnici de la un alt răspuns https://stackoverflow.com/a/3032462/207661 . În timp ce codul este în C#, ar trebui să fie trivial pentru a converti în C, Java, etc.

SingleListNode SortLinkedList(SingleListNode head) where T : IComparable
{
    int blockSize = 1, blockCount;
    do
    {
        //Maintain two lists pointing to two blocks, left and right
        SingleListNode left = head, right = head, tail = null;
        head = null; //Start a new list
        blockCount = 0;

        //Walk through entire list in blocks of size blockCount
        while (left != null)
        {
            blockCount++;

            //Advance right to start of next block, measure size of left list while doing so
            int leftSize = 0, rightSize = blockSize;
            for (;leftSize < blockSize && right != null; ++leftSize)
                right = right.Next;

            //Merge two list until their individual ends
            bool leftEmpty = leftSize == 0, rightEmpty = rightSize == 0 || right == null;
            while (!leftEmpty || !rightEmpty)
            {
                SingleListNode smaller;
                //Using <= instead of < gives us sort stability
                if (rightEmpty || (!leftEmpty && left.Value.CompareTo(right.Value) <= 0))
                {
                    smaller = left; left = left.Next; --leftSize;
                    leftEmpty = leftSize == 0;
                }
                else
                {
                    smaller = right; right = right.Next; --rightSize;
                    rightEmpty = rightSize == 0 || right == null;
                }

                //Update new list
                if (tail != null)
                    tail.Next = smaller;
                else
                    head = smaller;
                tail = smaller;
            }

            //right now points to next block for left
            left = right;
        }

        //terminate new list, take care of case when input list is null
        if (tail != null)
            tail.Next = null;

        //Lg n iterations
        blockSize <<= 1;

    } while (blockCount > 1);

    return head;
}

Puncte de interes

  • Nu există nici o manevrare specială pentru cazuri cum ar fi lista null a listei de 1 etc necesare. Aceste cazuri "funcționează".
  • Numeroase texte de algoritmi "standard" au două bucle pentru a trece peste elementele rămase pentru a se ocupa de cazul în care o listă este mai scurtă decât altele. Codul de mai sus elimină necesitatea.
  • Asigurați-vă că sortarea este stabilă
  • Bucla interioară, care este un punct fierbinte, evaluează în medie 3 expresii pe iterație, ceea ce cred că este minimă.

Actualizați: @ ideasman42 a tradus de mai sus în codul C/C ++ , împreună cu sugestiile pentru fixarea comentariilor și bit mai multă ameliorare. Codul de mai sus este actualizat cu acestea.

0
adăugat
În timp ce acest lucru este destul de bun, versiunea de la eglib-ul lui Mono se realizează ușor mai rapid în testele mele (optimizat C) ~ 10-20%, vezi: stackoverflow .com/a/18246901/432509
adăugat autor ideasman42, sursa
A creat o versiune îmbunătățită a acestui răspuns: gist.github.com/ideasman42/5921b0edfc6aa41a9ce0 1) Utilizați un indicator la coadă (eliminați 2x verificări condiționale, reduce dimensiunea codului). 2) Evitați re-alocarea valorilor goale, dimensiunea nu se modifică. 3) Comentariile corectate.
adăugat autor ideasman42, sursa
Comentariile arată că nu sunt actualizate pentru a corespunde codului. Acestea se referă la variabile care nu există în codul p q & k , care (cred că) ar trebui să fie left right & block_size respectiv.
adăugat autor ideasman42, sursa
Acest lucru este absolut genial! Am transformat-o în Delphi și funcționează foarte bine. Multumesc domnule !
adăugat autor Marus Nebunu, sursa
Multumesc @ ideaman42. Am adăugat o îmbunătățire a codului de mai sus. Pentru tail_p, nu există echivalent C# direct, astfel încât să rămână același :(.
adăugat autor ShitalShah, sursa

Un mod interesant este de a menține un teanc și de a îmbina numai dacă lista de pe stiva are același număr de elemente și, altfel, împingeți lista, până când rămâneți în afara elementelor din lista de intrare și apoi fuzionați stivă.

0
adăugat

Cel mai simplu este de la Gonnet + Baeza Yates Manual de algoritmi . Apelați-l cu numărul de elemente sortate pe care le doriți, care se recuperează în mod repetat până când ajunge la o cerere pentru o listă de dimensiuni unu pe care tocmai o detașați din fața listei originale. Toate acestea se îmbină într-o listă de dimensiuni complete sortate.

(Rețineți că starea se răcească pe baza unui prim post este numită Online Mergesort și devine cea mai mică mențiune într-un exercițiu în Knuth Vol 3]

0
adăugat

Heavily based on the EXCELLENT code from: http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html

S-au tăiat ușor și s-au șters:


typedef struct _aList {
    struct _aList* next;
    struct _aList* prev;//Optional.
      //some data
} aList;

aList *merge_sort_list(aList *list,int (*compare)(aList *one,aList *two))
{
    int listSize=1,numMerges,leftSize,rightSize;
    aList *tail,*left,*right,*next;
    if (!list || !list->next) return list; //Trivial case

    do {//For each power of two<=list length
        numMerges=0,left=list;tail=list=0;//Start at the start

        while (left) {//Do this list_len/listSize times:
            numMerges++,right=left,leftSize=0,rightSize=listSize;
           //Cut list into two halves (but don't overrun)
            while (right && leftSizenext;
           //Run through the lists appending onto what we have so far.
            while (leftSize>0 || (rightSize>0 && right)) {
               //Left empty, take right OR Right empty, take left, OR compare.
                if (!leftSize)                  {next=right;right=right->next;rightSize--;}
                else if (!rightSize || !right)  {next=left;left=left->next;leftSize--;}
                else if (compare(left,right)<0) {next=left;left=left->next;leftSize--;}
                else                            {next=right;right=right->next;rightSize--;}
               //Update pointers to keep track of where we are:
                if (tail) tail->next=next;  else list=next;
               //Sort prev pointer
                next->prev=tail;//Optional.
                tail=next;          
            }
           //Right is now AFTER the list we just sorted, so start the next sort there.
            left=right;
        }
       //Terminate the list, double the list-sort size.
        tail->next=0,listSize<<=1;
    } while (numMerges>1);//If we only did one merge, then we just sorted the whole list.
    return list;
}

NB: Aceasta este O (NLog (N)) garantată și folosește resursele O (1) (fără recurs, fără stivă, nimic).

0
adăugat
Am crezut că încerc acest cod pe propria mea listă de legături. Din anumite motive, acesta rulează mai încet decât versiunea recursivă pe o listă int de 10 milioane de articole. A fost nevoie de aproximativ 6-7 secunde pentru versiunea recursivă și în jur de 10 pentru aceasta?
adăugat autor Matt, sursa
Fără surprize. Cel recursiv utilizează spațiu de stocare suplimentar pentru a accelera lucrurile.
adăugat autor Dave Gamble, sursa

O implementare mai simplă/clară ar putea fi implementarea recursivă, din care timpul de execuție NLog (N) este mai clar.

typedef struct _aList {
    struct _aList* next;
    struct _aList* prev;//Optional.
   //some data
} aList;

aList* merge_sort_list_recursive(aList *list,int (*compare)(aList *one,aList *two))
{
   //Trivial case.
    if (!list || !list->next)
        return list;

    aList *right = list,
          *temp  = list,
          *last  = list,
          *result = 0,
          *next   = 0,
          *tail   = 0;

   //Find halfway through the list (by running two pointers, one at twice the speed of the other).
    while (temp && temp->next)
    {
        last = right;
        right = right->next;
        temp = temp->next->next;
    }

   //Break the list in two. (prev pointers are broken here, but we fix later)
    last->next = 0;

   //Recurse on the two smaller lists:
    list = merge_sort_list_recursive(list, compare);
    right = merge_sort_list_recursive(right, compare);

   //Merge:
    while (list || right)
    {
       //Take from empty lists, or compare:
        if (!right) {
            next = list;
            list = list->next;
        } else if (!list) {
            next = right;
            right = right->next;
        } else if (compare(list, right) < 0) {
            next = list;
            list = list->next;
        } else {
            next = right;
            right = right->next;
        }
        if (!result) {
            result=next;
        } else {
            tail->next=next;
        }
        next->prev = tail; //Optional.
        tail = next;
    }
    return result;
}

NB: This has a Log(N) storage requirement for the recursion. Performance should be roughly comparable with the other strategy I posted. There is a potential optimisation here by running the merge loop while (list && right), and simple appending the remaining list (since we don't really care about the end of the lists; knowing that they're merged suffices).

0
adăugat

Se întreabă de ce ar trebui să fie o mare provocare, așa cum se menționează aici, aici este o implementare simplă în Java, cu orice "trucuri inteligente".

//The main function
public Node merge_sort(Node head) {
    if(head == null || head.next == null) { return head; }
    Node middle = getMiddle(head);      //get the middle of the list
    Node sHalf = middle.next; middle.next = null;   //split the list into two halfs

    return merge(merge_sort(head),merge_sort(sHalf));  //recurse on that
}

//Merge subroutine to merge two sorted lists
public Node merge(Node a, Node b) {
    Node dummyHead, curr; dummyHead = new Node(); curr = dummyHead;
    while(a !=null && b!= null) {
        if(a.info <= b.info) { curr.next = a; a = a.next; }
        else { curr.next = b; b = b.next; }
        curr = curr.next;
    }
    curr.next = (a == null) ? b : a;
    return dummyHead.next;
}

//Finding the middle element of the list for splitting
public Node getMiddle(Node head) {
    if(head == null) { return head; }
    Node slow, fast; slow = fast = head;
    while(fast.next != null && fast.next.next != null) {
        slow = slow.next; fast = fast.next.next;
    }
    return slow;
}

Some more explanation here - http://www.dontforgettothink.com/2011/11/23/merge-sort-of-linked-list

0
adăugat
link @ jayadev rupt
adăugat autor Ravi, sursa
Implementare excelentă. Mulțumiri!
adăugat autor Gaston Sanchez, sursa
excelent ușor ...
adăugat autor L.E., sursa
nu încercați trucuri de cleaver la domiciliu
adăugat autor poolie, sursa
Cod foarte lizibil!
adăugat autor Chuntao Lu, sursa
Îmi plac oamenii care oferă exemple simple și clare, în loc de cod optim optimizat, care necesită ore să înțeleagă ce se întâmplă (dacă nu este ceea ce cere PO). Mulțumesc!
adăugat autor Salivan, sursa

Iată implementarea mea a "Sortului de îmbinare a listei" lui Knuth (Algoritmul 5.2.4L din Vol.3 al TAOCP, ediția a 2-a). Voi adăuga câteva comentarii la final, dar iată un rezumat:

La intrarea aleatorie, rulează puțin mai repede decât codul lui Simon Tatham (a se vedea răspunsul non-recursiv al lui Dave Gamble, cu un link), dar puțin mai lent decât codul recursiv al lui Dave Gamble. Este mai greu de înțeles decât oricare dintre ele. Cel puțin în implementarea mea, este necesar ca fiecare element să aibă două indicii pentru elemente. (O alternativă ar fi un indicator și un steag boolean.) Deci, probabil că nu este o abordare utilă. Cu toate acestea, un punct distinctiv este că rulează foarte rapid dacă intrarea are întinderi lungi deja sortate.

element *knuthsort(element *list)
{ /* This is my attempt at implementing Knuth's Algorithm 5.2.4L "List merge sort"
     from Vol.3 of TAOCP, 2nd ed. */
  element *p, *pnext, *q, *qnext, head1, head2, *s, *t;
  if(!list) return NULL;

L1: /* This is the clever L1 from exercise 12, p.167, solution p.647. */
  head1.next=list;
  t=&head2;
  for(p=list, pnext=p->next; pnext; p=pnext, pnext=p->next) {
    if( cmp(p,pnext) > 0 ) { t->next=NULL; t->spare=pnext; t=p; }
  }
  t->next=NULL; t->spare=NULL; p->spare=NULL;
  head2.next=head2.spare;

L2: /* begin a new pass: */
  t=&head2;
  q=t->next;
  if(!q) return head1.next;
  s=&head1;
  p=s->next;

L3: /* compare: */
  if( cmp(p,q) > 0 ) goto L6;
L4: /* add p onto the current end, s: */
  if(s->next) s->next=p; else s->spare=p;
  s=p;
  if(p->next) { p=p->next; goto L3; } 
  else p=p->spare;
L5: /* complete the sublist by adding q and all its successors: */
  s->next=q; s=t;
  for(qnext=q->next; qnext; q=qnext, qnext=q->next);
  t=q; q=q->spare;
  goto L8;
L6: /* add q onto the current end, s: */
  if(s->next) s->next=q; else s->spare=q;
  s=q;
  if(q->next) { q=q->next; goto L3; } 
  else q=q->spare;
L7: /* complete the sublist by adding p and all its successors: */
  s->next=p;
  s=t;
  for(pnext=p->next; pnext; p=pnext, pnext=p->next);
  t=p; p=p->spare;
L8: /* is this end of the pass? */
  if(q) goto L3;
  if(s->next) s->next=p; else s->spare=p;
  t->next=NULL; t->spare=NULL;
  goto L2;
}
0
adăugat
Așa cum am spus la început, nu mă aștept pe nimeni să-mi placă acest lucru ca pe un algoritm (dacă nu sortați adesea o listă aproape perfect sortată). Am adăugat acest lucru (într-un post destul de vechi) pentru a vă salva problemele și dezamăgirea pe care tocmai am trecut-o ;-)
adăugat autor Ed Wynn, sursa
Pasul L1 aranjează lista de intrări în subliste. O versiune "vanilie" începe cu toate sublists de lungime 1. Versiunea "inteligent" aici păstrează secvențe ordonate în lista de intrare. În special, dacă lista este sortată la sosire, sortarea se termină după (n-1) comparații. Prin urmare, versiunea inteligentă oferă o economie masivă pe intrarea sortată și o economie mai mică la intrare, care are unele tendințe spre a fi sortate. La intrarea aleatorie, versiunea inteligentă este, de obicei, foarte puțin mai rapidă (cu câteva procente), deși utilizează mai multe comparații.
adăugat autor Ed Wynn, sursa
O observație semnificativă a acestei implementări este că utilizează un al doilea pointer, e-> spare, cu fiecare element. Înainte de sfârșitul unei sublistări, e-> next dă următorul element. La sfarsit, e-> urmatorul este NULL. Începutul următoarei subliste (dacă există) este dat de e-> spare. La sfârșitul sortimentului, întreaga listă este legată prin -> următorul. Pseudo-codul lui Knuth a folosit indici de matrice în loc de indicatori, iar un indice negativ a anunțat sfârșitul unei sublistări (iar valoarea absolută a dat startul următorului sublist).
adăugat autor Ed Wynn, sursa
Strategia globală este aceea că deținem două lanțuri de subliste, care se extind din cele două elemente manechinelor head1 și head2. O sublistă este cunoscută a fi sortată. Facem mai multe treceri, îmbinând prima sublistă de la cap 1 cu prima din cap 2, apoi cu cea de-a doua cu cea de-a doua și așa mai departe. (Este esențial să existe un număr egal de subliste sau un extra în lanțul capului.) Sublistele nou îmbinate sunt atașate alternativ la primul și al doilea lanț, la locul lor, în mod stabil și fără recurs.
adăugat autor Ed Wynn, sursa

Iată o versiune alternativă recursivă. Nu este nevoie să treceți de-a lungul listei pentru ao împărți: furnizăm un pointer unui element de cap (care nu face parte din sortare) și o lungime, iar funcția recursivă returnează un pointer la sfârșitul listei sortate.

element* mergesort(element *head,long lengtho)
{ 
  long count1=(lengtho/2), count2=(lengtho-count1);
  element *next1,*next2,*tail1,*tail2,*tail;
  if (lengtho<=1) return head->next;  /* Trivial case. */

  tail1 = mergesort(head,count1);
  tail2 = mergesort(tail1,count2);
  tail=head;
  next1 = head->next;
  next2 = tail1->next;
  tail1->next = tail2->next; /* in case this ends up as the tail */
  while (1) {
    if(cmp(next1,next2)<=0) {
      tail->next=next1; tail=next1;
      if(--count1==0) { tail->next=next2; return tail2; }
      next1=next1->next;
    } else {
      tail->next=next2; tail=next2;
      if(--count2==0) { tail->next=next1; return tail1; }
      next2=next2->next;
    }
  }
}
0
adăugat
Am venit în esență cu aceeași implementare, cu excepția indicatorilor indicatori în loc de nodurile manechinului , gândindu-mă în mod clar codul inovator trebuie să fie un salt cuantic în domeniul informaticii. Nimic nou sub soare, presupun. Orice sugestii pentru un mod curat de accelerare a cazului majoritar pre-sortat?
adăugat autor doynax, sursa

Există o fuzionare de listă fără legătură recursivă în mono eglib .

Ideea de bază este că buclă de control pentru diversele fuziuni paralel cu creșterile de biți ale unui întreg binar. Există noduri O (n) îmbinate cu "inserați" nodurile n în arborele de îmbinare, iar rangul acelor fuzionări corespunde cifrei binare care devine incrementată. Folosind această analogie, numai nodurile O (log n) ale arborelui de îmbinare trebuie să fie materializate într-o matrice de exploatare temporară.

0
adăugat
Aceasta este cea mai bună implementare pe care am găsit-o până acum, a făcut o implementare portabilă a acesteia (care poate fi inclusă direct, cu adăugarea opțiunii thunk argument ~ ca qsort_r ). Vedeți gist.github.com/ideasman42/…
adăugat autor ideasman42, sursa

Unul dintre dezavantajele sortimentului de îmbinare este că utilizează spațiul O (n) pentru a stoca datele. adică atunci când îmbinați cele două subliste Pentru lista conectată, aceasta poate fi evitată prin modificarea următorului pointer din nodul listă. Ultima implementare pare ciudată, dar nu o ia în considerare.

0
adăugat