इस ट्यूटोरियल में, आप सीखेंगे कि चयन प्रकार कैसे काम करता है। साथ ही, आपको C, C ++, Java और पायथन में चयन प्रकार के काम के उदाहरण मिलेंगे।
चयन सॉर्ट एक एल्गोरिथ्म है जो प्रत्येक पुनरावृत्ति में एक अनसोल्ड सूची से सबसे छोटे तत्व का चयन करता है और उस तत्व को अनसोल्ड सूची की शुरुआत में रखता है।
चयन कैसे कार्य करता है?
- पहले तत्व को इस प्रकार सेट करें
minimum।
न्यूनतम के रूप में पहले तत्व का चयन करें minimumदूसरे तत्व के साथ तुलना करें । यदि दूसरा तत्व इससे छोटा हैminimum, तो दूसरा तत्व असाइन करेंminimum। तीसरे तत्व के साथ
तुलना करेंminimum। दोबारा, यदि तीसरा तत्व छोटा है, तोminimumतीसरे तत्व को असाइन करें अन्यथा कुछ भी न करें। प्रक्रिया अंतिम तत्व तक चलती है।
शेष तत्वों के साथ न्यूनतम तुलना करें- प्रत्येक पुनरावृत्ति के बाद,
minimumअनसोल्ड सूची के सामने रखा जाता है।
न्यूनतम के साथ पहले स्वैप करें - प्रत्येक पुनरावृत्ति के लिए, अनुक्रमण पहले अनसोल्ड तत्व से शुरू होता है। चरण 1 से 3 को दोहराया जाता है जब तक कि सभी तत्व अपने सही स्थान पर नहीं रखे जाते।
पहला पुनरावृति 
दूसरा पुनरावृति 
तीसरा पुनरावृत्ति 
चौथा पुनरावृत्ति
चयन सॉर्ट एल्गोरिथम
सिलेक्शन सोर (एरे, साइज) रिपीट (साइज - 1) बार पहले अनसर्टेड एलिमेंट को हर एक अनसर्टेड एलिमेंट के लिए न्यूनतम सेट करें अगर एलिमेंट <currentininimum सेट एलिमेंट नए मिनिमम स्वैप के साथ मिनिमम अनसोल्ड पोजिशन एंड सिलेक्शन हो।
पायथन, जावा और सी / सी ++ उदाहरण
पायथन जावा सी सी ++ # Selection sort in Python def selectionSort(array, size): for step in range(size): min_idx = step for i in range(step + 1, size): # to sort in descending order, change> to < in this line # select the minimum element in each loop if array(i) < array(min_idx): min_idx = i # put min at the correct position (array(step), array(min_idx)) = (array(min_idx), array(step)) data = (-2, 45, 0, 11, -9) size = len(data) selectionSort(data, size) print('Sorted Array in Ascending Order:') print(data)
// Selection sort in Java import java.util.Arrays; class SelectionSort ( void selectionSort(int array()) ( int size = array.length; for (int step = 0; step < size - 1; step++) ( int min_idx = step; for (int i = step + 1; i to < in this line. // Select the minimum element in each loop. if (array(i) < array(min_idx)) ( min_idx = i; ) ) // put min at the correct position int temp = array(step); array(step) = array(min_idx); array(min_idx) = temp; ) ) // driver code public static void main(String args()) ( int() data = ( 20, 12, 10, 15, 2 ); SelectionSort ss = new SelectionSort(); ss.selectionSort(data); System.out.println("Sorted Array in Ascending Order: "); System.out.println(Arrays.toString(data)); ) )
// Selection sort in C #include // function to swap the the position of two elements void swap(int *a, int *b) ( int temp = *a; *a = *b; *b = temp; ) void selectionSort(int array(), int size) ( for (int step = 0; step < size - 1; step++) ( int min_idx = step; for (int i = step + 1; i to < in this line. // Select the minimum element in each loop. if (array(i) < array(min_idx)) min_idx = i; ) // put min at the correct position swap(&array(min_idx), &array(step)); ) ) // function to print an array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( printf("%d ", array(i)); ) printf(""); ) // driver code int main() ( int data() = (20, 12, 10, 15, 2); int size = sizeof(data) / sizeof(data(0)); selectionSort(data, size); printf("Sorted array in Acsending Order:"); printArray(data, size); )
// Selection sort in C++ #include using namespace std; // function to swap the the position of two elements void swap(int *a, int *b) ( int temp = *a; *a = *b; *b = temp; ) // function to print an array void printArray(int array(), int size) ( for (int i = 0; i < size; i++) ( cout << array(i) << " "; ) cout << endl; ) void selectionSort(int array(), int size) ( for (int step = 0; step < size - 1; step++) ( int min_idx = step; for (int i = step + 1; i to < in this line. // Select the minimum element in each loop. if (array(i) < array(min_idx)) min_idx = i; ) // put min at the correct position swap(&array(min_idx), &array(step)); ) ) // driver code int main() ( int data() = (20, 12, 10, 15, 2); int size = sizeof(data) / sizeof(data(0)); selectionSort(data, size); cout << "Sorted array in Acsending Order:"; printArray(data, size); )
जटिलता
| चक्र | तुलना की संख्या |
|---|---|
| पहली बार | (एन -1) |
| 2 रा | (एन -2) |
| ३ | (एन -3) |
| … | … |
| अंतिम | 1 है |
तुलनाओं की संख्या: (n - 1) + (n - 2) + (n - 3) +… + 1 = n(n - 1) / 2लगभग बराबर है ।n2
जटिलता =O(n2)
इसके अलावा, हम केवल छोरों की संख्या को देखकर जटिलता का विश्लेषण कर सकते हैं। 2 लूप हैं इसलिए जटिलता है ।n*n = n2
समय जटिलताएं:
- सबसे खराब स्थिति जटिलता: यदि हम बढ़ते क्रम में क्रमबद्ध करना चाहते हैं और सरणी अवरोही क्रम में है, तो सबसे खराब स्थिति होती है।
O(n2) - बेस्ट केस कॉम्प्लेक्सिटी: यह तब होता है जब एरे पहले से ही सॉर्ट हो जाता है
O(n2) - औसत केस जटिलता: यह तब होता है जब सरणी के तत्व जंबल्ड ऑर्डर में होते हैं (न तो आरोही और न ही अवरोही)।
O(n2)
सभी मामलों में चयन प्रकार की समय जटिलता समान है। हर कदम पर, आपको न्यूनतम तत्व ढूंढना होगा और इसे सही जगह पर रखना होगा। सरणी के अंत तक नहीं पहुंचने तक न्यूनतम तत्व ज्ञात नहीं है।
अंतरिक्ष जटिलता:
अंतरिक्ष जटिलता O(1)इसलिए है क्योंकि एक अतिरिक्त चर tempका उपयोग किया जाता है।
चयन सॉर्ट एप्लिकेशन
चयन प्रकार का उपयोग तब किया जाता है जब:
- एक छोटी सूची को क्रमबद्ध करना है
- स्वैपिंग की लागत कोई मायने नहीं रखती
- सभी तत्वों की जाँच अनिवार्य है
- मेमोरी मेमोरी में लिखने की लागत फ्लैश मेमोरी की तरह होती है ( बबल सॉर्ट की
O(n)तुलना में राइट्स / स्वैप की संख्या )O(n2)
