छँटाई एल्गोरिदम। ग्नोम सॉर्ट इन सी

छँटाई एल्गोरिदम। वे कई नहीं हैं, लेकिन कुछ नहीं हैं। वहाँ अक्सर उपयोग किया जाता है, वहाँ कोई जरूरत नहीं है। मैंने अपनी मेमोरी और उपयोगकर्ता की मेमोरी दोनों को रीफ्रेश करने के लिए इन एल्गोरिदम की समीक्षा करने का निर्णय लिया। और शायद ही कभी ग्नोम सॉर्ट एल्गोरिथ्म (सूक्ति सॉर्टिंग) के साथ शुरू करें।

आधिकारिक लेखक (डिक ग्रुन) के अनुसार, गनोम सॉर्टिंग एल्गोरिथ्म विकसित किया गया था, जो गनोम द्वारा बगीचे के बर्तन को छांटता था। सच है या नहीं, एल्गोरिथ्म बहुत सरल है, खासकर शुरुआती लोगों के लिए। वास्तव में, एल्गोरिथ्म आसन्न बर्तन की तुलना करता है, अगर वे सही क्रम में हैं, तो हम सरणी के अगले तत्व पर जाते हैं, यदि नहीं, तो हम उन्हें पुनर्व्यवस्थित करते हैं और पिछले एक पर जाते हैं। कोई पिछला तत्व नहीं है - हम आगे बढ़ते हैं, कोई अगला नहीं है - फिर हम कर रहे हैं। प्रारंभ में, हम सरणी के दूसरे तत्व पर हैं।

चलो सी में कार्यान्वयन शुरू करते हैं। मुझे लगता है कि किसी को भी एरे के इनपुट और आउटपुट में कोई समस्या नहीं होगी:

#include <stdio.h> #include <stdlib.h> size_t n = 0; //    long *arr = NULL; //   void Read() { size_t i; printf("Array size: "); scanf("%u", &n); arr = (long*)calloc(n, sizeof(long)); printf("Array: "); for (i = 0; i < n; i++) { scanf("%d", &(arr[i])); } } void Do() { //  } void Write() { size_t i; printf("Result: "); for (i = 0; i < n; i++) { printf("%d ", arr[i]); } printf("\n"); } void main() { Read(); Do(); Write(); } 

तो, खुद को सॉर्ट करें। सबसे पहले, टाइप I के काउंटर I को एक में आरंभीकृत करें। हम उस स्थिति के साथ थोड़ी देर का लूप लिखते हैं <n:

 void Do() { //  size_t i = 1; while (i < n) { } } 

अब एक पाश। यदि हम शुरुआत में हैं, तो हम आगे बढ़ते हैं (यदि (i == 0) i = 1;)। यदि हम अंत में हैं, तो कुछ भी न लिखें, क्योंकि पाश हालत काम करेगा। यदि यह तत्व पिछले एक के बराबर या उससे अधिक है, तो आगे बढ़ें। एक अन्य मामले में, हम तत्वों को इंटरचेंज करते हैं और वापस जाते हैं।

छँटाई के लिए कुल तैयार कार्यक्रम:

 #include <stdio.h> #include <stdlib.h> size_t n = 0; long *arr = NULL; void Read() { size_t i; printf("Array size: "); scanf("%u", &n); arr = (long*)calloc(n, sizeof(long)); printf("Array: "); for (i = 0; i < n; i++) { scanf("%d", &(arr[i])); } } void Do() { //  size_t i = 1; //  while (i < n/*    */) { if (i == 0) { i = 1; } if (arr[i-1] <= arr[i]) { ++i; //   } else { //   long tmp = arr[i]; arr[i] = arr[i-1]; arr[i-1] = tmp; //   --i; } } } void Write() { size_t i; printf("Result: "); for (i = 0; i < n; i++) { printf("%d ", arr[i]); } printf("\n"); } void main() { Read(); Do(); Write(); }