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

मैं हाल ही में कुछ मौलिक सिद्धांतों पर ब्रश कर रहा था और एक जुड़ी सूची को एक बहुत अच्छी चुनौती के रूप में छेड़छाड़ करने में विलय पाया। यदि आपके पास अच्छा कार्यान्वयन है तो इसे यहां दिखाएं।

0
ro fr bn
जोड़ा लेखक Angus Johnson, स्रोत

12 उत्तर

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

0
जोड़ा
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
जोड़ा
मुझे लगता है कि यह 1 सही है !!!!!!!!!!
जोड़ा लेखक Pramod, स्रोत
सबसे पहले, आपका उत्तर ओपी प्रश्न के साथ कहीं भी मेल नहीं खाता है। दूसरा, यकीन नहीं, आपकी टिप्पणी क्या हैं?
जोड़ा लेखक Ravi, स्रोत

मैं इस एल्गोरिदम के लिए अनुकूलन को अनुकूलित करने पर जुनून लगा रहा था और नीचे वह आखिरकार आया है। इंटरनेट और स्टैक ओवरफ्लो पर बहुत सारे कोड बहुत खराब हैं। लोग सूची के मध्य बिंदु को पाने की कोशिश कर रहे हैं, रिकर्सन कर रहे हैं, नोड्स पर बाएं के लिए कई लूप रखते हैं, चीजों की संख्या को बनाए रखते हैं - जिनमें से सभी अनावश्यक हैं। 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 में कोड से ऊपर अनुवादित सी/सी ++ टिप्पणियों और बिट को ठीक करने के सुझावों के साथ है अधिक सुधार उपरोक्त कोड अब इनके साथ अद्यतित है।

0
जोड़ा
हालांकि यह काफी अच्छा है, मोनो के एग्लिब का संस्करण मेरे परीक्षणों (अनुकूलित सी) ~ 10-20% में थोड़ा तेज़ प्रदर्शन करता है, देखें: स्टैक ओवरफ्लो .com/एक/18246901/432509
जोड़ा लेखक ideasman42, स्रोत
इस उत्तर का एक बेहतर संस्करण बनाया गया: gist.github.com/ideasman42/5921b0edfc6aa41a9ce0 1) उपयोग करें पूंछ के लिए एक सूचक (2x सशर्त चेक हटा दें, कोड आकार को कम करता है)। 2) खाली मूल्यों को फिर से असाइन करने से बचें आकार बदल नहीं है। 3) सही टिप्पणियां।
जोड़ा लेखक ideasman42, स्रोत
टिप्पणियां दिखती हैं कि कोड से मेल खाने के लिए उन्हें अपडेट नहीं किया गया है। वे उन चरों को संदर्भित करते हैं जो कोड p q & k में मौजूद नहीं हैं जो (मुझे लगता है) क्रमशः बाएं दाएं और block_size होना चाहिए।
जोड़ा लेखक ideasman42, स्रोत
यह बिल्कुल शानदार है! मैंने इसे डेल्फी में बदल दिया और यह बहुत अच्छा काम करता है। धन्यवाद महोदय !
जोड़ा लेखक Marus Nebunu, स्रोत
धन्यवाद @ ideaman42। मैंने उपरोक्त कोड में एक सुधार जोड़ा है। Tail_p के लिए, कोई प्रत्यक्ष सी # समतुल्य नहीं है, इसलिए यह वही रहता है :(।
जोड़ा लेखक ShitalShah, स्रोत

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

0
जोड़ा

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) संसाधनों का उपयोग करता है (कोई रिकर्सन नहीं, कोई ढेर नहीं, कुछ भी नहीं)।

0
जोड़ा
मैंने सोचा कि मैं अपनी कोड लिंक्ड सूची पर इस कोड को आजमाउंगा। किसी कारण से यह 10 मिलियन वस्तुओं की एक int सूची पर रिकर्सिव संस्करण से धीमी गति से चलता है। रिकर्सिव संस्करण के लिए लगभग 6-7 सेकंड और इस के लिए लगभग 10 ले गए?
जोड़ा लेखक Matt, स्रोत
कोई आश्चर्य नहीं। रिकर्सिव एक चीजों को गति देने के लिए अतिरिक्त संग्रहण का उपयोग करता है।
जोड़ा लेखक Dave Gamble, स्रोत

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

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
जोड़ा

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

//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
जोड़ा
@ जयादेव टूटी हुई लिंक
जोड़ा लेखक Ravi, स्रोत
महान कार्यान्वयन। धन्यवाद!
जोड़ा लेखक Gaston Sanchez, स्रोत
उत्कृष्टता से आसान ...
जोड़ा लेखक L.E., स्रोत
घर पर क्लीवर चाल की कोशिश मत करो
जोड़ा लेखक poolie, स्रोत
बहुत पठनीय कोड!
जोड़ा लेखक Chuntao Lu, स्रोत
मुझे ऐसे लोगों को पसंद है जो भारी अनुकूलित कोड के बजाय सरल और स्पष्ट उदाहरण प्रदान करते हैं जिसके लिए क्या हो रहा है यह समझने के लिए घंटों की आवश्यकता होती है (जब तक कि ओपी यही मांग नहीं कर रहा हो)। धन्यवाद!
जोड़ा लेखक Salivan, स्रोत

यहां 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;
}
0
जोड़ा
जैसा कि मैंने शुरुआत में कहा था, मैं किसी को यह एल्गोरिदम के रूप में पसंद करने की उम्मीद नहीं कर रहा हूं (जब तक आप अक्सर लगभग पूरी तरह से क्रमबद्ध सूची को सॉर्ट नहीं करते)। मैंने आपको यह परेशानी और निराशा बचाने के लिए (काफी पुरानी पोस्ट में) जोड़ा है ;-)
जोड़ा लेखक Ed Wynn, स्रोत
चरण एल 1 सूक्ष्मवादियों में इनपुट सूची की व्यवस्था करता है। एक "वेनिला" संस्करण लंबाई 1 के सभी उपन्यासियों के साथ शुरू होता है। यहां "चालाक" संस्करण इनपुट सूची में किसी भी क्रमबद्ध अनुक्रम रखता है। विशेष रूप से, यदि सूची आगमन पर क्रमबद्ध की जाती है, तो क्रम (एन -1) तुलना के बाद समाप्त होता है। चतुर संस्करण इसलिए सॉर्ट किए गए इनपुट पर भारी बचत देता है, और इनपुट पर कम बचत करता है जिसमें सॉर्ट किए जाने की दिशा में कुछ पूर्वाग्रह होते हैं। यादृच्छिक इनपुट पर, चालाक संस्करण आमतौर पर बहुत तेज़ (कुछ प्रतिशत तक) होता है हालांकि यह अधिक तुलना का उपयोग करता है।
जोड़ा लेखक Ed Wynn, स्रोत
इस कार्यान्वयन का एक महत्वपूर्ण प्रश्न यह है कि यह प्रत्येक तत्व के साथ एक दूसरा सूचक, ई-> अतिरिक्त का उपयोग करता है। एक उपन्यास के अंत से पहले, ई-> अगला अगला तत्व देता है। अंत में, ई-> अगला पूर्ण है। अगले उपन्यास (अगर कोई है) की शुरुआत ई-> अतिरिक्त द्वारा दी गई है। इस तरह के अंत में, पूरी सूची -> अगले के माध्यम से जुड़ा हुआ है। न्यूथ के छद्म कोड ने पॉइंटर्स के बजाय सरणी सूचकांक का उपयोग किया, और एक नकारात्मक सूचकांक ने एक उपन्यास के अंत की घोषणा की (और पूर्ण मूल्य ने अगले उपन्यास की शुरुआत दी)।
जोड़ा लेखक Ed Wynn, स्रोत
समग्र रणनीति यह है कि हम दो डमी तत्वों हेड 1 और हेड 2 से विस्तारित, उपन्यासियों की दो श्रृंखलाएं रखते हैं। एक उपन्यास को हल करने के लिए जाना जाता है। हम कई गुजरते हैं, हेड 1 से पहले सब्लिस्ट को हेड 2 से पहले विलय करते हैं, फिर दूसरे के साथ दूसरा, और इसी तरह। (यह आवश्यक है कि उपन्यासों की समान संख्याएं हों, या हेड 1 की श्रृंखला में एक अतिरिक्त हो।) नए मर्ज किए गए उपन्यास पहले और दूसरी श्रृंखला के लिए वैकल्पिक रूप से संलग्न होते हैं, स्थान पर, स्थिर रूप से, और बिना किसी पुनरावर्तन के।
जोड़ा लेखक Ed Wynn, स्रोत

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

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
जोड़ा
मैं अनिवार्य रूप से एक ही कार्यान्वयन के साथ आया, डमी नोड्स के बजाय पॉइंटर्स-टू-पॉइंटर्स को छोड़कर , स्पष्ट रूप से मेरी सोच अभिनव कोड कंप्यूटर विज्ञान में क्वांटम छलांग होना चाहिए। मुझे लगता है कि सूरज के नीचे कुछ नया नहीं है। ज्यादातर पूर्व-क्रमबद्ध मामले को तेज करने के एक साफ तरीके के लिए कोई सुझाव?
जोड़ा लेखक doynax, स्रोत
0
जोड़ा
यह अब तक का सबसे अच्छा कार्यान्वयन है, मैंने इसका एक पोर्टेबल कार्यान्वयन किया है (जिसे विकल्प <�कोड> थंक arg ~ जैसे qsort_r ) के अतिरिक्त सीधे शामिल किया जा सकता है। gist.github.com/ideasman42/… देखें
जोड़ा लेखक ideasman42, स्रोत

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

0
जोड़ा