የአረፋ ደርድር ከምርጫ ድርድር
የአረፋ መደርደር በአጎራባች ያሉ ጥንዶችን በማነፃፀር በተደጋጋሚ ለመደርደር ዝርዝሩን በማለፍ የሚሰራ የመደርደር ስልተ ቀመር ነው። ጥንድ ንጥረ ነገሮች በተሳሳተ ቅደም ተከተል ውስጥ ከሆኑ በትክክለኛው ቅደም ተከተል ለማስቀመጥ ይለዋወጣሉ። ምንም ተጨማሪ መለዋወጥ እስካልፈለገ ድረስ ይህ መሻገር ይደገማል። የምርጫ መደርደር እንዲሁ የመደርደር ስልተ ቀመር ነው፣ እሱም የሚጀምረው በዝርዝሩ ውስጥ ያለውን አነስተኛውን አካል በማግኘት እና ከመጀመሪያው አካል ጋር በመለዋወጥ ነው። ይህ ሂደት የተለዋወጡ ክፍሎችን በቅደም ተከተል በማስቀመጥ ለቀሪው ዝርዝር ይደገማል።
የአረፋ መደርደር ምንድነው?
የአረፋ መደርደር በአጎራባች ያሉ ጥንዶችን በማነፃፀር በተደጋጋሚ ለመደርደር ዝርዝሩን በማለፍ የሚሰራ የመደርደር ስልተ ቀመር ነው። ጥንድ ንጥረ ነገሮች በተሳሳተ ቅደም ተከተል ውስጥ ከሆኑ በትክክለኛው ቅደም ተከተል ለማስቀመጥ ይለዋወጣሉ። ምንም ተጨማሪ መለዋወጥ እስካልፈለገ ድረስ ይህ መሻገር ይደገማል (ይህ ማለት ዝርዝሩ ተደርድሯል ማለት ነው)። በዝርዝሩ ውስጥ ያሉት ትናንሽ አካላት አረፋ ወደ ላይ ሲመጣ ወደ ላይ ስለሚመጡ የአረፋ ዓይነት የሚል ስያሜ ተሰጥቶታል። የአረፋ መደርደር በጣም ቀላል የመደርደር ስልተ-ቀመር ነው ነገር ግን ዝርዝርን ከ n ኤለመንቶች ጋር ሲደረደር አማካይ የ O(n2) ውስብስብነት አለው። በዚህ ምክንያት, የአረፋ ዓይነት ብዙ ቁጥር ያላቸውን ዝርዝሮች ለመደርደር ተስማሚ አይደለም. ነገር ግን በቀላልነቱ ምክንያት የአረፋ ዓይነት ወደ ስልተ ቀመሮች መግቢያ ወቅት ይማራል።
ምርጫ መደርደር ምንድነው?
የምርጫ ዓይነት እንዲሁ በዝርዝሩ ውስጥ ያለውን አነስተኛውን አካል በማግኘት እና ከመጀመሪያው አካል ጋር በመለዋወጥ የሚጀምር ሌላ የመደርደር ስልተ-ቀመር ነው።ከዚያም ዝቅተኛው ንጥረ ነገር ከዝርዝሩ ውስጥ ይገኛል (ከሁለተኛው ኤለመንቱ እስከ መጨረሻው አካል ድረስ) እና ከሁለተኛው አካል ጋር ይለዋወጣል. ይህ ሂደት የተለዋወጡትን ንጥረ ነገሮች በቅደም ተከተል በማስቀመጥ ለቀሪው ዝርዝር ይደገማል። ስለዚህ በምርጫ ዓይነት፣ በማንኛውም የስልተ ቀመር ደረጃ፣ ዝርዝሩ በሁለት ክፍሎች የተከፈለ ሲሆን አንደኛው ክፍል የተደረደሩ ንጥረ ነገሮችን የያዘ ሲሆን ሌላኛው ክፍል ደግሞ ያልተደረደሩ ክፍሎችን ይይዛል። አልጎሪዝም በሚቀጥልበት ጊዜ, የተደረደሩት ዝርዝር ከግራ ወደ ቀኝ ያድጋል. የምርጫ ዓይነት እንዲሁ የO(n2) አማካኝ የጉዳይ ጊዜ ውስብስብነት አለው። ስለዚህ ትልልቅ ዝርዝሮችን ለመደርደርም ተስማሚ አይደለም።
በአረፋ ደርድር እና በምርጫ ደርድር መካከል ያለው ልዩነት ምንድን ነው?
ምንም እንኳን ሁለቱም የአረፋ ድርድር እና የመምረጫ ስልተ ቀመሮች አማካኝ የጉዳይ ጊዜ ውስብስብነት ኦ(n2) ቢኖራቸውም የአረፋ መደርደር ሁሉም ጊዜ ማለት ይቻላል በምርጫ አይነት ይበልጣል። ይህ በሁለቱ ስልተ ቀመሮች በሚያስፈልጉት የመለዋወጫ ብዛት ምክንያት ነው (የአረፋ ዓይነቶች ተጨማሪ መለዋወጥ ያስፈልጋቸዋል)።ነገር ግን በአረፋ ዓይነት ቀላልነት ምክንያት የኮድ መጠኑ በጣም ትንሽ ነው። በእነዚህ ሁለት ስልተ ቀመሮች ውስጥ መረጋጋት ሌላ ልዩነት ነው. የተረጋጋ የመደርደር ስልተ-ቀመር፣ ዝርዝሩ እኩል ዋጋ ያላቸውን ንጥረ ነገሮች ከያዘ የመዝገቦችን ቅደም ተከተል የሚይዝ የመደርደር ስልተ-ቀመር ነው። ከዚህ አንፃር፣ የመምረጫ አይነት የተረጋጋ ስልተ-ቀመር አይደለም፣ነገር ግን የአረፋ መደርደር የተረጋጋ ስልተ-ቀመር ነው።
