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