सम्मिलन क्रमबद्ध एल्गोरिथम

इस ट्यूटोरियल में, आप सीखेंगे कि प्रविष्टि सॉर्ट कैसे काम करता है। साथ ही, आपको C, C ++, Java और पायथन में सम्मिलन प्रकार के काम के उदाहरण मिलेंगे।

सम्मिलन सॉर्ट उसी तरह काम करता है जैसे हम कार्ड गेम में अपने हाथ में कार्ड छांटते हैं।

हम मानते हैं कि पहले कार्ड को पहले से ही सॉर्ट किया गया है, फिर हम एक अनसोल्ड कार्ड का चयन करते हैं। यदि हाथ में अनसोल्ड कार्ड कार्ड से अधिक है, तो इसे दाईं ओर रखा गया है, अन्यथा बाईं ओर। उसी तरह, अन्य अनसोल्ड कार्ड्स को उनके सही स्थान पर ले जाया जाता है।

एक समान दृष्टिकोण प्रविष्टि सॉर्ट द्वारा उपयोग किया जाता है।

सम्मिलन सॉर्ट एक छँटाई एल्गोरिथ्म है जो प्रत्येक पुनरावृत्ति में अपने उपयुक्त स्थान पर एक अनसुलझा तत्व रखता है।

प्रविष्टि कैसे काम करती है?

मान लें कि हमें निम्नलिखित सरणी को क्रमबद्ध करने की आवश्यकता है।

प्रारंभिक सरणी

1. सरणी में पहला तत्व क्रमबद्ध माना जाता है। दूसरा तत्व लें और इसे अलग से स्टोर करें key। पहले तत्व के साथ
   तुलना करें key। यदि पहले तत्व से अधिक है key, तो पहले तत्व के सामने कुंजी रखी गई है। यदि पहला तत्व कुंजी से अधिक है, तो कुंजी को पहले तत्व के सामने रखा गया है।
2. अब, पहले दो तत्वों को क्रमबद्ध किया गया है।
   तीसरा तत्व लें और उसकी बाईं ओर के तत्वों के साथ तुलना करें। इसे उससे छोटे तत्व के ठीक पीछे रखा। यदि इससे छोटा कोई तत्व नहीं है, तो इसे सरणी की शुरुआत में रखें। शुरुआत में 1 रखें
3. इसी तरह, हर अनसुलझे तत्व को उसके सही स्थान पर रखें। 4 को 1 के पीछे रखें, 1 के पीछे 3 को जगह दें और सरणी को क्रमबद्ध करें

सम्मिलन क्रमबद्ध एल्गोरिथम

 निवेशनसॉर्ट (सरणी) प्रत्येक असंगत तत्व के लिए छांटे गए तत्व के रूप में पहले तत्व को चिह्नित करता है। एक्स एक्स निकालने के लिए तत्व एक्स, जे एक्स मूव के लिए तत्व को 1 ब्रेक लूप द्वारा दाईं ओर ले जाता है और एक्स को यहां सम्मिलित करता है

पायथन, जावा और सी / सी ++ उदाहरण

पायथन जावा सी सी ++

 # Insertion sort in Python def insertionSort(array): for step in range(1, len(array)): key = array(step) j = step - 1 # Compare key with each element on the left of it until an element smaller than it is found # For descending order, change keyarray(j). while j>= 0 and key < array(j): array(j + 1) = array(j) j = j - 1 # Place key at after the element just smaller than it. array(j + 1) = key data = (9, 5, 1, 4, 3) insertionSort(data) print('Sorted Array in Ascending Order:') print(data)

  // Insertion sort in Java import java.util.Arrays; class InsertionSort ( void insertionSort(int array()) ( int size = array.length; for (int step = 1; step < size; step++) ( int key = array(step); int j = step - 1; // Compare key with each element on the left of it until an element smaller than // it is found. // For descending order, change keyarray(j). while (j>= 0 && key < array(j)) ( array(j + 1) = array(j); --j; ) // Place key at after the element just smaller than it. array(j + 1) = key; ) ) // Driver code public static void main(String args()) ( int() data = ( 9, 5, 1, 4, 3 ); InsertionSort is = new InsertionSort(); is.insertionSort(data); System.out.println("Sorted Array in Ascending Order: "); System.out.println(Arrays.toString(data)); ) )

 // Insertion sort in C #include // Function to print an array void printArray(int array(), int size) ( for (int i = 0; i < size; i++) ( printf("%d ", array(i)); ) printf(""); ) void insertionSort(int array(), int size) ( for (int step = 1; step < size; step++) ( int key = array(step); int j = step - 1; // Compare key with each element on the left of it until an element smaller than // it is found. // For descending order, change keyarray(j). while (key = 0) ( array(j + 1) = array(j); --j; ) array(j + 1) = key; ) ) // Driver code int main() ( int data() = (9, 5, 1, 4, 3); int size = sizeof(data) / sizeof(data(0)); insertionSort(data, size); printf("Sorted array in ascending order:"); printArray(data, size); )

 // Insertion sort in C++ #include using namespace std; // Function to print an array void printArray(int array(), int size) ( for (int i = 0; i < size; i++) ( cout << array(i) << " "; ) cout << endl; ) void insertionSort(int array(), int size) ( for (int step = 1; step < size; step++) ( int key = array(step); int j = step - 1; // Compare key with each element on the left of it until an element smaller than // it is found. // For descending order, change keyarray(j). while (key = 0) ( array(j + 1) = array(j); --j; ) array(j + 1) = key; ) ) // Driver code int main() ( int data() = (9, 5, 1, 4, 3); int size = sizeof(data) / sizeof(data(0)); insertionSort(data, size); cout << "Sorted array in ascending order:"; printArray(data, size); )

जटिलता

समय की जटिलताएँ

• सबसे खराब मामला जटिलता: मान लीजिए, एक सरणी आरोही क्रम में है, और आप इसे अवरोही क्रम में क्रमबद्ध करना चाहते हैं। इस मामले में, सबसे खराब स्थिति जटिलता होती है। प्रत्येक तत्व की तुलना प्रत्येक अन्य तत्वों के साथ की जाती है इसलिए, प्रत्येक nth तत्व के लिए, तुलना की संख्या बनाई जाती है। इस प्रकार, तुलनाओं की कुल संख्या =O(n2)

(n-1)
n*(n-1) ~ n2
• सर्वश्रेष्ठ मामले की जटिलता: O(n)
  जब सरणी पहले से ही हल हो जाती है, तो बाहरी लूप nकई बार चलता है जबकि आंतरिक लूप बिल्कुल नहीं चलता है। तो, nतुलना की संख्या केवल हैं । इस प्रकार, जटिलता रैखिक है।
• औसत केस जटिलता: यह तब होता है जब किसी सरणी के तत्व जंबल्ड ऑर्डर में होते हैं (न तो आरोही और न ही अवरोही)।O(n2)

अंतरिक्ष की जटिलता

अंतरिक्ष जटिलता O(1)इसलिए है क्योंकि एक अतिरिक्त चर keyका उपयोग किया जाता है।

प्रविष्टि सॉर्ट अनुप्रयोग

प्रविष्टि प्रकार का उपयोग तब किया जाता है जब:

• सरणी में तत्वों की एक छोटी संख्या होती है
• छांटने के लिए कुछ ही तत्व बचे हैं