Mergeți Sortați o listă conectată

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.

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;
}

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.

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ă.

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]

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).

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).

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

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;
}

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;
    }
  }
}

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ă.

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.