हमें विशिष्ट तत्वों की एक असॉर्टेड सरणी दी गई है। लक्ष्य सरणी के क्रमबद्ध होने के बाद क्रॉस लाइन्स ढूंढना है। क्रॉस लाइन्स को नीचे दिखाए अनुसार गिना जाता है -
Arr[]={ 1,2,4,3,5 } यहां 3 क्रॉस लाइन्स हैं जैसा कि नीचे दिखाया गया है
Arr[]= { 1,2,3,4,5 }. कोई क्रॉस लाइन्स नहीं क्योंकि सरणी पहले से क्रमबद्ध है।
हम इंसर्शन सॉर्ट का उपयोग करके क्रॉस लाइन्स गिनेंगे जिसमें दाएं से एक तत्व को उसके बाएं क्रमबद्ध तत्वों में जोड़ा जाता है। हर बार जब तत्व क्रमबद्ध भाग में अपनी सही स्थिति में जुड़ता है, तो काउंट बढ़ाते हैं क्योंकि यह अपनी सही स्थिति में जाने के लिए उन सभी तत्वों को पार करता है जो इससे बड़े हैं।
आइए उदाहरणों से समझते हैं।
इनपुट - arr[]= {4,3,1,2 }
आउटपुट - सरणी में क्रॉस लाइन्स की संख्या: 5
व्याख्या - लाइन 4-4 और 3-3, लाइन्स 1-1 और 2-2 को पार करती हैं। कुल 4 क्रॉस लाइन्स।
4-4 और 3-3 दोनों एक दूसरे को एक बार पार करते हैं। कुल 4+1=5 क्रॉस लाइन्स।
इनपुट - arr[]= { 0,1,5,3 }
आउटपुट - सरणी में क्रॉस लाइन्स की संख्या: 1
व्याख्या - 5-5 और 3-3 दोनों एक दूसरे को एक बार पार करते हैं। कुल 1 क्रॉस लाइन।
नीचे दिए गए प्रोग्राम में उपयोग किया गया दृष्टिकोण
हम विशिष्ट संख्याओं से आरंभ एक पूर्णांक सरणी arr[] लेते हैं।
फंक्शन insertionSort(int arr[], int n) एक सरणी और उसकी लंबाई को इनपुट के रूप में लेता है और क्रमबद्ध करने के बाद क्रॉस लाइन्स की गिनती परिणाम के रूप में लौटाता है।
प्रारंभिक क्रॉस लाइन्स की संख्या को 0 के रूप में लेते हैं। काउंट वेरिएबल का उपयोग किया जाता है।
पहला तत्व पहले से क्रमबद्ध है, इसलिए दूसरे तत्व से अंत तक (i=1 से i
अब उन सभी तत्वों को दाएं शिफ्ट करते हैं जो > item हैं और j>=0। प्रत्येक शिफ्ट के लिए काउंट बढ़ाते हैं क्योंकि ये सभी item द्वारा पार किए जाते हैं।
व्हाइल लूप के अंत में item को उसकी सही स्थिति arr[j+1] पर रखते हैं।
सभी तत्वों के लिए ऐसा करते हैं और उनके द्वारा पार किए गए तत्वों को गिनते हैं।
काउंट के मान को संभावित क्रॉस लाइन्स की संख्या के रूप में बढ़ाते हैं।
उदाहरण
#include <bits/stdc++.h> using namespace std; int insertionSort(int arr[], int n){ int count=0; int item; int j; for (int i = 1; i < n; i++){ item = arr[i]; j = i - 1; //क्रमबद्ध भाग में तत्व को सही स्थिति में डालें, तत्व द्वारा दाएं से सही स्थिति तक पार किए गए तत्वों की संख्या क्रॉस लाइन्स की गिनती है। while (j >= 0 && arr[j] > item){ arr[j + 1] = arr[j]; j = j - 1; count++; } arr[j + 1] = item; } return count; } int main(){ int arr[] = { 4,5,3,1,2}; int n = 5; cout<<"क्रॉस लाइन्स की संख्या: "<<insertionSort(arr, n); return 0; } आउटपुट
यदि हम उपरोक्त कोड चलाते हैं तो यह निम्नलिखित आउटपुट उत्पन्न करेगा -
क्रॉस लाइन्स की संख्या: 8
