Which of the following sorting algorithms can be used to sort a random linked…
2024
Which of the following sorting algorithms can be used to sort a random linked list with minimum time complexity?
- A.
Insertion Sort
- B.
Quick Sort
- C.
Merge Sort
- D.
More than one of the above
- E.
None of the above
Attempted by 388 students.
Show answer & explanation
Correct answer: C
Correct Answer: Merge Sort
To sort a random linked list with minimum time complexity, we must consider the data structure's limitations. Unlike arrays, linked lists do not support random access (O(1) access to any element). This constraint eliminates algorithms that rely heavily on indexing.
Analysis of Options
Insertion Sort: While it can be implemented on linked lists, it has a time complexity of O(n^2). This is inefficient for large random lists.
Quick Sort: Standard Quick Sort requires random access to pick pivots and partition elements efficiently. Implementing it on a linked list is complex and often results in O(n^2) worst-case or high overhead.
Merge Sort: This is the ideal choice. It can be implemented to work in O(n log n) time without random access. It only requires sequential traversal and pointer manipulation to merge sub-lists.
Therefore, Merge Sort provides the minimum time complexity of O(n log n) for sorting a linked list.
सही उत्तर: मर्ज सॉर्ट
एक यादृच्छिक लिंक्ड लिस्ट को न्यूनतम समय जटिलता में सॉर्ट करने के लिए, हमें डेटा संरचना की सीमाओं पर विचार करना होगा। एरे की तरह, लिंक्ड लिस्ट में रैंडम एक्सेस (किसी भी तत्व तक O(1) एक्सेस) का समर्थन नहीं करता है। यह प्रतिबंध उन एल्गोरिदम को हटा देता है जो इंडेक्सिंग पर बहुत निर्भर करते हैं।
विकल्पों का विश्लेषण
इन्सर्शन सॉर्ट: हालांकि इसे लिंक्ड लिस्ट पर लागू किया जा सकता है, इसकी समय जटिलता O(n^2) होती है। यह बड़ी यादृच्छिक लिस्ट के लिए दक्ष नहीं है।
क्विक सॉर्ट: मानक क्विक सॉर्ट को पिवोट चुनने और तत्वों को विभाजित करने के लिए रैंडम एक्सेस की आवश्यकता होती है। लिंक्ड लिस्ट पर इसे लागू करना जटिल है और अक्सर O(n^2) खराब मामला या उच्च ओवरहेड का परिणाम देता है।
मर्ज सॉर्ट: यह आदर्श विकल्प है। इसे बिना रैंडम एक्सेस के O(n log n) समय में काम करने के लिए लागू किया जा सकता है। इसमें उप-लिस्ट को मर्ज करने के लिए केवल अनुक्रमिक ट्रावर्सल और पॉइंटर मैन्युपुलेशन की आवश्यकता होती है।
अतः, मर्ज सॉर्ट लिंक्ड लिस्ट को सॉर्ट करने के लिए O(n log n) की न्यूनतम समय जटिलता प्रदान करता है।