አንድ ፕሮግራም ስልት እንደ Quicksort

በ 1960 ውስጥ, ኬ ኤ Hoar, መረጃ ፈጣን ድርደራ አንድ ዘዴ በጣም ታዋቂ ሆኗል. አወንታዊ ንብረቶች ብዙ ያለው ሆኖ ዛሬ በሰፊው, ፕሮግራም ውስጥ ጥቅም ላይ ነው: ይህም አጠቃላይ ጉዳዮች ጥቅም ላይ ሊውል ይችላል, ይህም ዝርዝሮች የተለያዩ ዓይነቶች ጋር ተኳሃኝ እና ለመተግበር ቀላል ተጨማሪ ትውስታ ውስጥ አንድ አነስተኛ ጭማሪ, ይጠይቃል. በመጠቀም ሥራ ስህተቶች ብዙ ፈቀደ; ይህም በተወሰነ ያልተረጋጋ ነው: ነገር ግን Quicksort ያለው, እንቅፋቶች አሉ.

ይሁን እንጂ በጣም ጥናት ስሪት ነው. የመጀመሪያው ክፍያ Hoare በኋላ, ብዙ በውስጡ ጥቅጥቅ ጥናት ማድረግ. ትልቅ መሰረት የተጠና ማስረጃ በሚያስተዋውቁና ነው ይህም ሥራ ላይ የሚያሳልፈውን ጊዜ የማግኘት በንድፈ ጥያቄዎች ላይ ተቋቋመ. መሠረታዊ ስልተ እና ጨምሯል ፍጥነት ለማሻሻል እውነተኛ መጫረቻ ነበሩ.

Quicksort በየስፍራው ሁሉ ሊገኙ ይችላሉ, በጣም የተለመደ ነው. በውስጡ መሠረት ላይ ያለውን ዘዴ ዴልፊ, ይህም ++ ሲ ውስጥ, qsort ለማጠናቀቅ ወሰደ ጊዜ ቤተ መጻሕፍት ተግባር (1 በስተቀር) ሁሉም ስሪቶች ውስጥ በአሁኑ TList.Sort, አልተተገበረም ነው.

የክወና መሠረታዊ መርህ አንድ "መከፋፈል እና ከአሸናፊዎች እንበልጣለን" እንደ በመንደፍ ይቻላል. ሁለት ቡድኖች ወደ ዝርዝር ሰበር የሚሳካ በራሱ እያንዳንዱ ክፍል የተደረደሩ ናቸው. አንድ መሰረታዊ አባል የሚወሰነው ሲሆን በአንጻራዊ ሁኔታ መላ ዝርዝር ለውጠዋል አድርጓል: ይበልጥ ትኩረት የሚከተለውን ተጠቅሶ ወቅት ተለያይተው ሂደት, ወደ መከፈል እንዳለበት ይከተላል. እጩዎች ቡድን በስተግራ የተሰራ, ዋጋ ያለውን ሁሉ ወደ ሌሎች ማስተላለፍ ደንቦች ያነሰ ነው. ይህ የተደረደሩ ዝርዝር ውስጥ ዋና አባል በትክክለኛ ቦታ ላይ ነው ይንጸባረቅበታል. ቀጣዩ ደረጃ - ግርጌ ወደ አንጻራዊ ንጥረ ነገሮች በሁለቱም ወገኖች ፈታኝ recursive ድርደራ ተግባራት. በዚያ የሚደረደረው ነው, ሂደት ዝርዝር ብቻ አንድ አባል ይዟል ከሆነ ብቻ ነው የሚሰራው ያበቃል. በመሆኑም ፈጣን ዓይነት እንደ አንድ ፕሮግራም ተግባር ማከናወን እስኪችል ሲሉ, ይህም ዝቅተኛ-ደረጃ ስልተ ሥራ ማወቅ አስፈላጊ ነው: ሀ) መሠረት አባል ምርጫ; ለ) በጣም ውጤታማ ስልፈት ዝርዝር አነስ እና ተለቅ እሴቶች ጋር ሁለት ስብስቦችን ለማምረት.

የመጀመሪያዎቹ መርሆዎች ጋር ይወቁ. የ ቤዝ አባል በምትመርጥበት ጊዜ, በሐሳብ ደረጃ አማካይ ዝርዝር መመረጥ ያለበት. ከዚያም እረፍት ላይ ሁለት እኩል ግማሾችን የተከፋፈለ ነው. በቀላሉ ለማስላት አማካይ ዋጋ በዝርዝሩ ውስጥ በጣም አስቸጋሪ ነው, ስለዚህ እንኳ ፈጣን ድርደራ ይህን ካልኩለስ ጎን የጨጓራ. ነገር ግን ከፍተኛ ወይም ዝቅተኛ ዋጋ ጋር መሠረታዊ ንጥረ ያለውን ምርጫ - ደግሞ እንጂ የተሻለ አማራጭ. ሁኔታ ውስጥ አንዱ እንዲህ ያለ ውሳኔ ባዶ ዝርዝሮች የተረጋገጠ ሲሆን ሁለተኛው ሙሉ ይሆናል ይፈጥራል. በመሆኑም በ ቤዝ አባል ሆኖ አማካይ ይበልጥ የሆነ አንድ የተመረጠ, ነገር ግን ከፍተኛ እና ዝቅተኛ ላይ መሆን አለበት የሚል መደምደሚያ ላይ.

ምርጫ የሚወሰነው አንዴ ውህድ ስልተ መቀጠል ይችላሉ. ይህን ፈጣን ዓይነት ውስጣዊ ቀለበቶች ስለዚህ-ይባላል. ሁሉም ሁለት ፈጣን መዳረሻ ኢንዴክሶች ላይ የተሰራ ነው: መጀመሪያ ወደ ግራ ወደ ቀኝ ጀምሮ, በተቃራኒ ላይ: በቀኝ: ሁለተኛውን ከግራ ወደ ንጥረ ነገሮች ላይ ይሂዱ. ክወና አፈጻጸም መብት ይጀምራል: የኢንዴክሱን በዝርዝሩ ላይ ነው እና ዋናው ሁሉንም ዋጋዎች ማወዳደር. ወደ አባል ወደ ከመነሻው ወደ ያነሰ ወይም እኩል በሚሆንበት ጊዜ ዑደት ተጠናቋል. ይህ የለም አንድ ንጽጽር ነው የኢንዴክሱን ዋጋ ይቀንሳል ነው. በግራ በኩል ሥራ የበለጠ ወይም እኩል እሴት ሲጠናቀቅ. እዚህ ያለውን ንጽጽር ዋጋ ይጨምራል.

quicksort ያካተተ ይህም በመከፋፈል ስልተ በዚህ ደረጃ ላይ, ሁለት ሁኔታዎች ሊፈጠሩ ይችላሉ. የመጀመሪያው በግራ በኩል ያለውን ማውጫ ትክክል ያነሰ መሆኑን ነው. ይሄ ስህተት ያመለክታል, ከዛ ዝርዝር ውስጥ እንደተገለጸው ነበር የሆነውን ላይ ክፍሎችን የተሳሳተ ቅደም ናቸው አሉ. የውጤት - ያላቸውን ቦታዎች መለወጥ. አምድ ሁለቱም እኩል ወይም በመሻገር ጊዜ ሁለተኛው ሁኔታ ነው. ይህ አትበል; ይህ ሥራ በአሁኑ ጊዜ ሙሉ ነው, በዝርዝሩ ውስጥ ስኬታማ መለያየት ያመለክታል.