सॉर्टेड ऐरे
ऐरे जिसमें तत्व क्रमबद्ध क्रम में हों (संख्यात्मक, वर्णानुक्रमिक, आदि)। कई सॉर्टिंग एल्गोरिदम: बबल सॉर्ट, इन्सर्शन सॉर्ट, सिलेक्शन सॉर्ट, मर्ज सॉर्ट, क्विक सॉर्ट, हीप सॉर्ट।
सिलेक्शन सॉर्ट
अनसॉर्टेड भाग में सबसे छोटा तत्व ढूंढकर उसे शुरुआत से स्वैप करता है। O(n²) समय जटिलता।
C++ प्रोग्राम उदाहरण
#include <iostream>
using namespace std;
void selectionSort(int a[], int n) {
int i, j, min, temp;
for (i = 0; i < n - 1; i++) {
min = i;
for (j = i + 1; j < n; j++)
if (a[j] < a[min])
min = j;
temp = a[i];
a[i] = a[min];
a[min] = temp;
}
}
int main() {
int a[] = { 22, 91, 35, 78, 10, 8, 75, 99, 1, 67 };
int n = sizeof(a) / sizeof(a[0]);
int i;
cout << "Given array is:" << endl;
for (i = 0; i < n; i++)
cout << a[i] << " ";
cout << endl;
selectionSort(a, n);
cout << "Sorted array is:" << endl;
for (i = 0; i < n; i++)
cout << a[i] << " ";
return 0;
}
आउटपुट
Given array is: 22 91 35 78 10 8 75 99 1 67 Sorted array is: 1 8 10 22 35 67 75 78 91 99
कोड व्याख्या
selectionSort() फ़ंक्शन
दो नेस्टेड लूप: बाहरी लूप प्रत्येक स्थिति i के लिए, आंतरिक लूप i+1 से n-1 तक न्यूनतम ढूंढता है, फिर स्वैप करता है।
मुख्य फ़ंक्शन
ऐरे परिभाषित करता है, आकार की गणना करता है, मूल ऐरे प्रिंट करता है, सॉर्ट कॉल करता है, फिर सॉर्टेड ऐरे प्रिंट करता है।
सिलेक्शन सॉर्ट विशेषताएं
- समय जटिलता: O(n²) - सभी मामलों में
- स्थान जटिलता: O(1) - इन-प्लेस सॉर्टिंग
- स्वैप की संख्या: न्यूनतम (अधिकतम n-1)
- स्थिर नहीं (unstable)