सिलेक्शन सॉर्ट तकनीक में, सूची को दो भागों में विभाजित किया जाता है। एक भाग में सभी तत्व क्रमबद्ध होते हैं और दूसरे भाग में आइटम असॉर्टेड होते हैं। पहले हम सरणी से अधिकतम या न्यूनतम डेटा लेते हैं। डेटा प्राप्त करने के बाद (मान लें न्यूनतम) हम इसे पहले स्थान के डेटा को न्यूनतम डेटा से बदलकर सूची की शुरुआत में रखते हैं। ऑपरेशन करने के बाद सरणी छोटी होती जा रही है। इस प्रकार यह सॉर्टिंग तकनीक पूरी होती है।
सिलेक्शन सॉर्ट तकनीक की जटिलता
समय जटिलता: O(n2)
स्पेस जटिलता: O(1)
इनपुट − असॉर्टेड सूची: 5 9 7 23 78 20 आउटपुट − सॉर्टिंग के बाद सरणी: 5 7 9 20 23 78
एल्गोरिदम
selectionSort(array, size)
इनपुट: डेटा की एक सरणी, और सरणी में कुल संख्या
आउटपुट: क्रमबद्ध सरणी
शुरुआत i := 0 से size-2 तक करें //i स्थान से size तक न्यूनतम ढूंढें iMin := i; j:= i+1 से size – 1 तक करें यदि array[j] < array[iMin] तो iMin := j हो गया array[i] को array[iMin] से स्वैप करें। हो गया अंत
उदाहरण कोड
#include<iostream> using namespace std; void swapping(int &a, int &b) { //a और b की सामग्री स्वैप करें int temp; temp = a; a = b; b = temp; } void display(int *array, int size) { for(int i = 0; i<size; i++) cout << array[i] << " "; cout << endl; } void selectionSort(int *array, int size) { int i, j, imin; for(i = 0; i<size-1; i++) { imin = i; //न्यूनतम डेटा का सूचकांक प्राप्त करें for(j = i+1; j<size; j++) if(array[j] < array[imin]) imin = j; //सही स्थिति में रखें swap(array[i], array[imin]); } } int main() { int n; cout << "तत्वों की संख्या दर्ज करें: "; cin >> n; int arr[n]; //दिए गए तत्वों की संख्या के साथ एक सरणी बनाएं cout << "तत्व दर्ज करें:" << endl; for(int i = 0; i<n; i++) { cin >> arr[i]; } cout << "सॉर्टिंग से पहले सरणी: "; display(arr, n); selectionSort(arr, n); cout << "सॉर्टिंग के बाद सरणी: "; display(arr, n); }
आउटपुट
तत्वों की संख्या दर्ज करें: 6 तत्व दर्ज करें: 5 9 7 23 78 20 सॉर्टिंग से पहले सरणी: 5 9 7 23 78 20 सॉर्टिंग के बाद सरणी: 5 7 9 20 23 78