फिशर-येट्स शफल एल्गोरिदम
यह एल्गोरिदम सरणी में तत्वों को शफल करने के लिए है। सरणी में तत्वों को शफल करने के लिए हम अपना लॉजिक लिख सकते हैं, लेकिन कई डेवलपर्स मानते हैं कि फिशर-येट्स आधुनिक शफल एल्गोरिदम सरणी में तत्वों को शफल करने का सबसे अच्छा तरीका है। इस एल्गोरिदम के निम्न चरण हैं।
पालन करने योग्य चरण
- इस एल्गोरिदम के अनुसार हमें सरणी को पीछे से आगे की ओर लूप करना चाहिए। उदाहरण के लिए, निम्न उदाहरण में, हमारे पास 8 तत्वों (A,B,C,D,E,F,G,H) वाली एक सरणी है जो इंडेक्स 0 से इंडेक्स 7 तक है। तो पहला लूप पास इंडेक्स 7 पर मौजूद तत्व H को प्रभावित करेगा।
- अगला चरण चयनित इंडेक्स 7 और इंडेक्स 0 के बीच एक रैंडम नंबर (रैंडम इंडेक्स) उत्पन्न करना है। मान लीजिए रैंडम इंडेक्स 3 है।
- रैंडम इंडेक्स प्राप्त करने के बाद चयनित इंडेक्स और रैंडम इंडेक्स पर मौजूद तत्वों को स्वैप करें। प्रदान की गई सरणी में रैंडम इंडेक्स पर मौजूद तत्व D है। स्वैप करने के बाद सरणी A,B,C,H,E,G,F,D में बदल जाएगी।
- दूसरे लूप पास में केवल अंतिम इंडेक्स को अनदेखा करें (क्योंकि यह पहले ही लूप हो चुका है) और इंडेक्स 0 और इंडेक्स 6 के बीच रैंडम इंडेक्स खोजने का प्रयास करें, यानी तत्वों A और F के बीच। मान लीजिए उत्पन्न रैंडम इंडेक्स 2 है।
- रैंडम इंडेक्स प्राप्त करने के बाद इंडेक्स 6 और 2 पर मौजूद तत्वों को स्वैप करें। अब सरणी A,B,F,H,E,G,C,D जैसी दिखेगी।
- यह एल्गोरिदम उसी पैटर्न का पालन करता है: यह इंडेक्स 6 को अनदेखा करता है और इंडेक्स 5 और इंडेक्स 0 के बीच रैंडम इंडेक्स खोजना शुरू करता है और इसी तरह तब तक जब तक यह इंडेक्स 1 तक नहीं पहुंच जाता। यह इंडेक्स 0 को लूप नहीं कर सकता क्योंकि स्वैपिंग के लिए 0 से कम कोई इंडेक्स नहीं है।
- ध्यान दें कि उत्पन्न रैंडम इंडेक्स चयनित लूप इंडेक्स के बराबर हो सकता है। उदाहरण के लिए, मान लीजिए लूप चयनित इंडेक्स 4 और इंडेक्स 0 के बीच चल रहा है। मान लीजिए उत्पन्न रैंडम इंडेक्स 4 है। तब इंडेक्स 4 पर मौजूद मान उसी स्थिति में रहेगा।
निम्न उदाहरण फिशर-येट्स आधुनिक शफल एल्गोरिदम को दर्शाता है
उदाहरण
<html> <body> <script> var arr = ['A','B','C','D','E','F','G','H'] var i = arr.length, k , temp; // k is to generate random index and temp is to swap the values while(--i > 0){ k = Math.floor(Math.random() * (i+1)); temp = arr[k]; arr[k] = arr[i]; arr[i] = temp; } document.write(arr); </script> </body> </html>आउटपुट
C,F,H,D,A,G,E,B // ध्यान दें कि आउटपुट हर पुनरावृत्ति के लिए बदल जाएगा।
