एक लिंक्ड सूची को सॉर्ट करें

आप मर्ज सॉर्ट के उस कार्यान्वयन का उपयोग कर सकते हैं और लिंक किए गए सूची के साथ इंटरफ़ेस में अपने स्वयं के फ़ंक्शंस लिख सकते हैं जैसे कि यह एक सरणी थी।

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

मैं इस एल्गोरिदम के लिए अनुकूलन को अनुकूलित करने पर जुनून लगा रहा था और नीचे वह आखिरकार आया है। इंटरनेट और स्टैक ओवरफ्लो पर बहुत सारे कोड बहुत खराब हैं। लोग सूची के मध्य बिंदु को पाने की कोशिश कर रहे हैं, रिकर्सन कर रहे हैं, नोड्स पर बाएं के लिए कई लूप रखते हैं, चीजों की संख्या को बनाए रखते हैं - जिनमें से सभी अनावश्यक हैं। MergeSort स्वाभाविक रूप से जुड़ी हुई सूची में फिट बैठता है और एल्गोरिदम सुंदर और कॉम्पैक्ट हो सकता है लेकिन उस स्थिति में जाने के लिए यह छोटा नहीं है।

नीचे कोड चर की संख्या को बनाए रखता है और जहां तक ​​मुझे पता है, एल्गोरिदम (यानी कोड को अनजान/अपठनीय बनाने के बिना) के लिए आवश्यक तार्किक चरणों की न्यूनतम संख्या है। हालांकि मैंने एलओसी को कम करने की कोशिश नहीं की है और चीजों को पठनीय रखने के लिए जितना आवश्यक हो उतना सफेद स्थान रखा है। मैंने काफी कठोर यूनिट परीक्षणों के माध्यम से इस कोड का परीक्षण किया है।

ध्यान दें कि यह उत्तर अन्य उत्तरों https://stackoverflow.com/a/3032462/207661 से कुछ तकनीकों को जोड़ता है। जबकि कोड सी # में है, सी ++, जावा इत्यादि में कनवर्ट करने के लिए यह छोटा होना चाहिए।

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

ब्याज के अंक

• 1 आदि की सूची की शून्य सूची जैसे मामलों के लिए कोई विशेष हैंडलिंग नहीं है। ये मामले "बस काम करता है"।
• बहुत से "मानक" एल्गोरिदम ग्रंथों में दो लूप होते हैं जो बचे हुए तत्वों पर जाने के लिए होते हैं जब एक सूची दूसरे की तुलना में कम होती है। उपरोक्त कोड इसके लिए आवश्यकता को समाप्त करता है।
• हम सुनिश्चित करते हैं कि सॉर्ट स्थिर है
• आंतरिक लूप जो हॉट स्पॉट है, औसत पर प्रति अभिव्यक्ति के 3 अभिव्यक्तियों का मूल्यांकन करता है जो मुझे लगता है कि न्यूनतम कोई भी कर सकता है।

अपडेट करें: @ ideasman42 में कोड से ऊपर अनुवादित सी/सी ++ टिप्पणियों और बिट को ठीक करने के सुझावों के साथ है अधिक सुधार उपरोक्त कोड अब इनके साथ अद्यतित है।

एक दिलचस्प तरीका एक ढेर को बनाए रखना है, और केवल विलय करें यदि स्टैक की सूची में तत्वों की संख्या समान है, और अन्यथा सूची को दबाएं, जब तक कि आप आने वाली सूची में तत्वों से बाहर नहीं हो जाते, और फिर स्टैक को मर्ज करें।

सबसे सरल है गोननेट + बेज़ा येट्स हैंडबुक एल्गोरिदम । आप इसे इच्छित सॉर्ट किए गए तत्वों की संख्या के साथ बुलाते हैं, जो तब तक विभाजित हो जाते हैं जब तक यह एक आकार की सूची के अनुरोध तक पहुंच न जाए, जिसे आप मूल सूची के सामने छीलते हैं। ये सभी एक पूर्ण आकार की क्रमबद्ध सूची में विलय हो जाते हैं।

[ध्यान दें कि पहली पोस्ट में ठंडा ढेर-आधारित एक को ऑनलाइन विलयोर्ट कहा जाता है और इसे Knuth Vol 3 में एक अभ्यास में सबसे छोटा उल्लेख मिलता है]

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

थोड़ा छंटनी, और tidied:

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

एनबी: यह ओ (एनएलओजी (एन)) गारंटी है, और ओ (1) संसाधनों का उपयोग करता है (कोई रिकर्सन नहीं, कोई ढेर नहीं, कुछ भी नहीं)।

एक सरल/स्पष्ट कार्यान्वयन पुनरावर्ती कार्यान्वयन हो सकता है, जिससे एनएलओजी (एन) निष्पादन समय अधिक स्पष्ट होता है।

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

आश्चर्य है कि इसे यहां बड़ी चुनौती क्यों दी जानी चाहिए, जैसा कि यहां बताया गया है, यहां जावा में किसी भी "चालाक चाल" के साथ एक सीधा कार्यान्वयन है।

//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

यहां Knuth की "लिस्ट मर्ज सॉर्ट" (TAOCP के वॉल्यूम 3 से एल्गोरिदम 5.2.4L, दूसरा संस्करण) का कार्यान्वयन है। मैं अंत में कुछ टिप्पणियां जोड़ूंगा, लेकिन यहां सारांश है:

यादृच्छिक इनपुट पर, यह साइमन तथम के कोड से थोड़ा तेज़ चलता है (डेव गैंबल के गैर-रिकर्सिव उत्तर को एक लिंक के साथ देखें) लेकिन डेव गैंबल के रिकर्सिव कोड से थोड़ी धीमी है। या तो समझना मुश्किल है। कम से कम मेरे कार्यान्वयन में, प्रत्येक तत्व को तत्वों के लिए TWO पॉइंटर्स की आवश्यकता होती है। (एक विकल्प एक सूचक और एक बुलियन ध्वज होगा।) तो, यह शायद एक उपयोगी दृष्टिकोण नहीं है। हालांकि, एक विशिष्ट बिंदु यह है कि यदि इनपुट में लंबे समय तक फैला हुआ है जो पहले से क्रमबद्ध है तो यह बहुत तेज़ चलता है।

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

यहां एक वैकल्पिक रिकर्सिव संस्करण है। इसे विभाजित करने के लिए सूची के साथ कदम उठाने की आवश्यकता नहीं है: हम एक प्रमुख तत्व (जो कि प्रकार का हिस्सा नहीं है) और एक लम्बाई के लिए एक सूचक प्रदान करते हैं, और पुनरावर्ती फ़ंक्शन क्रमबद्ध सूची के अंत में एक सूचक देता है।

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

mono eglib <में एक गैर-पुनरावर्ती लिंक-लिस्ट विलय है।/a>।

मर्ज सॉर्ट की कमी में से एक यह है कि यह डेटा स्टोर करने के लिए ओ (एन) स्पेस का उपयोग करता है। यानी जब आप दो उपन्यासों को विलय करते हैं तो लिंक्ड सूची के लिए, सूची सूचक नोड में अगला पॉइंटर बदलकर इसे टाला जा सकता है। अंतिम कार्यान्वयन साफ ​​दिखता है लेकिन इसे मानने में विफल रहता है।