የገባ አይነት፡ አልጎሪዝም እንዴት እንደሚሰራ ምሳሌዎች

2024 ደራሲ ደራሲ: Angel Austin | [email protected]. ለመጨረሻ ጊዜ የተሻሻለው: 2024-02-02 14:08

አደራደር የመደርደር ችግርን ለመፍታት በርካታ መሰረታዊ ስልተ ቀመሮች አሉ። ከነሱ መካከል በጣም ዝነኛ ከሆኑት አንዱ የማስገቢያ ዓይነት ነው። ግልጽነት እና ቀላልነት, ግን ዝቅተኛ ቅልጥፍና, ይህ ዘዴ በዋናነት ፕሮግራሚንግ በማስተማር ላይ ጥቅም ላይ ይውላል. መሰረታዊ የመደርደር ዘዴዎችን እንዲረዱ ያስችልዎታል።

የአልጎሪዝም መግለጫ

የማስገቢያ ደርድር አልጎሪዝም ፍሬ ነገር በትክክል የታዘዘ ክፍል በመጀመሪያው ድርድር ውስጥ መፈጠሩ ነው። እያንዳንዱ ንጥረ ነገር አንድ በአንድ ከተፈተሸው ክፍል ጋር በማነፃፀር ወደ ትክክለኛው ቦታ ያስገባል. ስለዚህ፣ ሁሉንም ንጥረ ነገሮች ከደጋገሙ በኋላ፣ በትክክለኛው ቅደም ተከተል ይሰለፋሉ።

ኤለመንቶችን የመምረጥ ቅደም ተከተል ማንኛውም ሊሆን ይችላል፣ በዘፈቀደ ወይም በአንዳንድ ስልተ ቀመር ሊመረጡ ይችላሉ። ብዙ ጊዜ፣ ተከታታይ ቆጠራ ከድርድሩ መጀመሪያ ጀምሮ ጥቅም ላይ ይውላል፣ የታዘዘ ክፍል ከተመሠረተ።

የመደርደር መጀመሪያ ይህን ሊመስል ይችላል፡

1. የድርድሩን የመጀመሪያ አካል ይውሰዱ።
2. ከሱ ጋር የሚነጻጸር ምንም ነገር ስለሌለ ኤለመንቱን እራሱ እንደታዘዘው ይውሰዱት።ቅደም ተከተል።
3. ወደ ሁለተኛው ንጥል ይሂዱ።
4. በመደርደር ደንቡ ላይ በመመስረት ከመጀመሪያው ጋር ያወዳድሩት።
5. አስፈላጊ ከሆነ ኤለመንቶችን በቦታ ይቀያይሩ።
6. የመጀመሪያዎቹን ሁለት አካላት እንደታዘዘ ቅደም ተከተል ይውሰዱ።
7. ወደ ሦስተኛው ንጥል ይሂዱ።
8. ከሁለተኛው ጋር ያወዳድሩት፣ ካስፈለገም ይቀይሩት።
9. ተተኪው ከተሰራ ከመጀመሪያው ጋር ያወዳድሩ።
10. ሦስት አካላትን እንደታዘዘው ቅደም ተከተል ውሰድ።

እናም እንዲሁ እስከ ዋናው ድርድር መጨረሻ ድረስ።

የእውነተኛ ህይወት ማስገቢያ አይነት

ግልጽ ለማድረግ ይህ የመለየት ዘዴ በዕለት ተዕለት ሕይወት ውስጥ እንዴት ጥቅም ላይ እንደሚውል ምሳሌ መስጠት ተገቢ ነው።

ለምሳሌ የኪስ ቦርሳ ይውሰዱ። መቶ፣ አምስት መቶ እና ሺህ ዶላር ሂሳቦች በባንክ ኖት ክፍል ውስጥ መታወክ አለባቸው። ይህ የተዝረከረከ ነው, በእንደዚህ አይነት የሆድፖጅ ውስጥ ትክክለኛውን ወረቀት ወዲያውኑ ማግኘት አስቸጋሪ ነው. የባንክ ኖቶች ድርድር መደርደር አለበት።

የመጀመሪያው የ 1000 ሬብሎች የባንክ ኖት ነው, እና ወዲያውኑ - 100. መቶ ወስደን ፊት ለፊት እናስቀምጠዋለን. በተከታታይ ሶስተኛው 500 ሬብሎች ነው, ትክክለኛው ቦታ ከመቶ እስከ አንድ ሺህ መካከል ነው.

በተመሳሳይ መንገድ የተቀበሉትን ካርዶች "ፉል" ስንጫወት በቀላሉ ለማሰስ እንለያያለን።

ኦፕሬተሮች እና አጋዥ ተግባራት

የማስገቢያ መደርደር ዘዴው ለመደርደር የመጀመሪያ ድርድር፣የማነጻጸሪያ ተግባር እና አስፈላጊ ከሆነ ኤለመንቶችን ለመቁጠር ደንቡን የሚወስን ተግባርን እንደ ግብአት ይወስዳል። በምትኩ በብዛት ጥቅም ላይ ይውላልመደበኛ ምልልስ መግለጫ።

የመጀመሪያው አካል እራሱ የታዘዘ ስብስብ ነው፣ስለዚህ ንፅፅሩ የሚጀምረው ከሁለተኛው ነው።

አልጎሪዝም ብዙውን ጊዜ ሁለት እሴቶችን ለመለዋወጥ የረዳት ተግባር ይጠቀማል። ተጨማሪ ጊዜያዊ ተለዋዋጭ ይጠቀማል፣ ማህደረ ትውስታን የሚወስድ እና ኮዱን ትንሽ ይቀንሳል።

አማራጭ የኤለመንቶችን ቡድን በጅምላ መቀየር እና በመቀጠል የአሁኑን ወደ ነጻ ቦታ ማስገባት ነው። በዚህ አጋጣሚ ወደ ቀጣዩ ኤለመንት የሚደረገው ሽግግር የሚከሰተው ንፅፅሩ አወንታዊ ውጤት ሲሰጥ ነው ይህም ትክክለኛውን ቅደም ተከተል ያሳያል።

የአተገባበር ምሳሌዎች

የተለየ አተገባበር በአብዛኛው የተመካው በተጠቀሰው የፕሮግራም አወጣጥ ቋንቋ፣ አገባብ እና አወቃቀሮቹ ላይ ነው።

እሴቶችን ለመለዋወጥ ጊዜያዊ ተለዋዋጭ በመጠቀም የታወቀ C ትግበራ፡

int i, j, temp; ለ (i=1; i =0; j--) { (array[j] < temp) ቢሰበር; አደራደር[j + 1]=ድርድር[j]; ድርድር [j]=ሙቀት; } }

PHP ትግበራ፡


የተግባር ማስገቢያ_ዓይነት(&$a) { ለ ($i=1; $i=0 &&$a[$j] > $x; $j--) {$a[$ j + 1]=$a[$j]; } $a[$j + 1]=$x; } }

እዚህ፣ በመጀመሪያ፣ ሁሉም ከድርድሩ ሁኔታ ጋር የማይዛመዱ ንጥረ ነገሮች ወደ ቀኝ ይቀየራሉ፣ እና አሁን ያለው ኤለመንቱ ወደ ነፃው ቦታ እንዲገባ ይደረጋል።
የጃቫ ኮድ ሲጠቀም፡


የሕዝብ የማይንቀሳቀስ ባዶ ማስገቢያSort(int arr) {ለ(int i=1; i =0 &&arr[prevKey] > currElem){ arr[prevKey+1]=አርር[prevKey]; arr[prevKey]=currElem; prevKey --; } }

የኮዱ አጠቃላይ ትርጉም ሳይለወጥ ይቆያል፡ እያንዳንዱ የድርድር አካል በቅደም ተከተል ከቀዳሚዎቹ ጋር ይነጻጸራል እና ካስፈለገም ይለዋወጣል።

የተገመተው የሩጫ ጊዜ
በግልጽ፣ በጥሩ ሁኔታ፣ የአልጎሪዝም ግብአት አስቀድሞ በትክክለኛው መንገድ የታዘዘ ድርድር ይሆናል። በዚህ ሁኔታ ስልተ ቀመር በቀላሉ መለዋወጥ ሳያስፈልግ በትክክለኛው ቦታ ላይ መሆኑን ለማረጋገጥ እያንዳንዱን ንጥረ ነገር መፈተሽ አለበት። ስለዚህ የሩጫ ሰዓቱ በቀጥታ በዋናው ኦ(n) ድርድር ርዝመት ይወሰናል።
በጣም የከፋው ግቤት በተቃራኒው ቅደም ተከተል የተደረደረ ድርድር ነው። ይህ ብዙ ቁጥር ያላቸው ማስተላለፎችን ይፈልጋል፣ የአሂድ ጊዜ ተግባሩ በካሬው አባሎች ብዛት ይወሰናል።
ሙሉ በሙሉ ላልታዘዘ ድርድር ትክክለኛው የዝውውሮች ብዛት በቀመርው ሊሰላ ይችላል፡


n(n-1)/2

፣ n የዋናው ድርድር ርዝመት ነው። ስለዚህ፣ 100 ኤለመንቶችን በትክክለኛው ቅደም ተከተል ለማዘጋጀት 4950 ፔርሙቴሽን ያስፈልጋል።
የማስገቢያ ዘዴው ትናንሽ ወይም በከፊል የተደረደሩ ድርድሮችን ለመለየት በጣም ቀልጣፋ ነው። ነገር ግን በከፍተኛ የስሌቶች ውስብስብነት ምክንያት በየቦታው እንዲተገበር አይመከርም።
አልጎሪዝም በብዙ ሌሎች ውስብስብ የመደርደር ዘዴዎች እንደ ረዳት ሆኖ ያገለግላል።






እኩል እሴቶችን ደርድር
የማስገቢያ ስልተ ቀመር የተረጋጋ ዓይነት የሚባሉት ነው። ይህ ማለት,ተመሳሳይ ንጥረ ነገሮችን እንደማይለዋወጥ ነገር ግን የመጀመሪያውን ቅደም ተከተል እንደሚጠብቅ. የመረጋጋት መረጃ ጠቋሚው በብዙ ሁኔታዎች ለትክክለኛ ቅደም ተከተል አስፈላጊ ነው።





ከላይ ያለው በዳንስ ውስጥ የማስገባት ታላቅ ምስላዊ ምሳሌ ነው።