ኮምፒዩተር ሳይንስ

From Wikipedia
Jump to: navigation, ድሉይ

ሓምለ ፳፻፱

ክዊክሶርት / Quicksort

ኣብ ስነ-ኮምፒተር እቲ ክዊክሶርት ኣገባብ ሓደ ካብቶም ዝቀልጠፉ ኣገባባት እዩ ሓደ ዓውዲ (Array) ንምስራዕ። እቲ ዓውዲ ዘይስሩዕ ቁጽሪታት ወይ ከኣ ካልእ ትሕዝቶ ክህልዎ ይኽእል።


መፍትሒ ናይ ክዊክሶርት እቲ ክልሰ-ሓሳብ „መቀለ ድሓር ሰፈነ“ (= divide and conquer) እዩ። ቅድም ነቲ ዓቢ ሽግር ኣብ ንኣሽቱ ሽግራት ትመቅሎ፣ ድሓር ነቶም ንኣሽቱ ሽግራት ንምፍታሕ ይቀልል እዩ። ሽዑ ስጉም ብስጉም ነቲ ዓቢ ሽግር ትፈትሖ ማለት እዩ። ስለዚ ከኣ እዚ ኣገባብ „መቀለ ድሓር ሰፈነ“ ይበሃል፥

ሓደ ባእታ ካብቲ ዓውዲ ትወስድ (ኣየናይ ባእታ ከምትወስድ ኣገዳሲ ኣይኮነን) ነቲ ዓውዲ ምእንቲ ኣብ መኣከሉ ክትመቅሎ። ድሓር ነቶም ካልኦት ካብቲ ቀንዲ ባእታ ዝንእሱ ባእታታት ኣብ ጸጋም ትገብሮም፣ ነቶም ካልኦት ካብቲ ቀንዲ ባእታ ዝዓበዩ ባእታታት ኣብ የማን ትገብሮም። ድሓር ልክዕ ነዚ ዕማም ትደግሞ፣ ነቲ ሓድሽ ዝወጸ ክፋል ናይቲ ዓውዲ ትመቅሎ፣ ሽዑ ነቲ ሓድሽ ክፋል ትሰርዖ። ድሓር ሙሉእ ዓውዲ ምስ ሰርዓኻ፡ እቶም ባእታታት ኣብቲ ዓውዲ (ትሕዝቶ ዓውዲ) ኩሎም ተሰሪዖም ኣለው።


እዚ’ቲ ቀንዲ ሽጣራ ናይቲ ክዊክሶርት ኣገባብ እዩ። ነቲ ክልሰ-ሓሳብ „መቀለ ድሓር ሰፈነ“ ኣብ ብዙሕ ዝተፋላለዩ ነገራት ኣብ ውሽጢ ሶፍትዌር ወይ ስነ-ኮምፒተር ይጥቀምሉ እዩ።

ኣብ ውሽጢ’ቲ ፕሮግራም ወይ ኮውድ ሕሳባዊ ፍልጠት ከኣ ክህልወካ ኣለዎ። ስነ-ሎምፒተር ብዘይ ሕሳብ ሙት እዩ።


መብርሂ ናይ ክwክሶርት፥


Quicksort.jpg


እቲ ዝስዕብ ኣገባብ (= function) ነቲ ቀንዲ ባእታ ይደሊ፣ ነቲ ዓውዲ (files[ ]) ከኣ ይመቅሎ፥


ቀንዲ ባእታ = Pivot

Quicksort2.jpg


Quicksort3.jpg