קוויקקסאָרט ווי אַ פּראָגראַממינג אופֿן

אין 1960, קיי יי האָאַר דעוועלאָפּעד אַ אופֿן פֿאַר דער גיך סאָרטינג פון אינפֿאָרמאַציע, איז געווארן די מערסט באַרימט. הייַנט עס איז וויידלי געניצט אין פּראָגראַממינג, ווי עס האט אַ פּלאַץ פון positive פּראָפּערטיעס: עס קענען זיין געניצט פֿאַר גענעראַל קאַסעס, עס ריקווייערז אַ קליין פאַרגרעסערן אין די נאָך זכּרון, קאַמפּאַטאַבאַל מיט פאַרשידענע טייפּס פון רשימות און גרינג צו ינסטרומענט. אבער עס זענען דראָבאַקס, וואָס האט קוויקקסאָרט: ניצן אַרבעט ערלויבט אַ פּלאַץ פון מיסטייקס, און עס איז עפּעס אַנסטייבאַל.

אָבער, עס איז די מערסט געלערנט ווערסיע. נאָך דער ערשטער צאָלונג האָאַרע, פילע טאָן זייַן טעמפּ לערנען. גרויס באַזע איז געגרינדעט אויף טעאָרעטיש שאלות פון דערגייונג די צייַט אויסגעגעבן אויף די אַרבעט, וואָס איז ונדערפּיננעד דורך עמפּיריקאַל זאָגן. עס זענען געווען פאַקטיש פּראַפּאָוזאַלז צו פֿאַרבעסערן די גרונט אַלגערידאַם און געוואקסן גיכקייַט.

קוויקקסאָרט איז זייער פּראָסט, עס קענען זיין געפֿונען אומעטום. אויף זייַן יקער דעם אופֿן איז ימפּלאַמענטאַד טליסט.סאָרט, פאָרשטעלן אין אַלע ווערסיעס (חוץ 1) Delphi, די ביבליאָטעק פֿונקציע פון צייַט עס גענומען צו פאַרענדיקן, קסאָרט אין C ++.

די גרונט פּרינציפּ פון אָפּעראַציע קענען זיין פאָרמולאַטעד ווי אַ "טיילן און קאַנגקער". עס אַקערז ברייקינג די רשימה אין צוויי גרופּעס און זענען אויסגעשטעלט פֿאַר יעדער טייל דורך זיך. עס גייט אַז מער אכטונג זאָל ווערן באַצאָלט צו די צעשיידונג פּראָצעס, בעשאַס וואָס די ווייַטערדיק אַקערז: איז באשלאסן דורך אַ באַזע עלעמענט און האט לעפיערעך ריעריינדזשד זייַן גאנצע רשימה. געבויט צו די לינקס פון אַ גרופּע פון קאַנדאַדייץ, די ווערט פון וואָס איז ווייניקער ווי אַלע די אנדערע אַריבערפירן כּללים. עס טורנס אויס אַז די הויפּט עלעמענט אין דער אויסגעשטעלט רשימה איז אין זייַן ריגהטפול אָרט. די ווייַטער בינע - אַ אַרויסרופן רעקורסיווע סאָרטינג פֿעיִקייטן פֿאַר ביידע זייטן פון די יסודות קאָרעוו צו די באַזע. עס ענדס די פּראָצעס אַרבעט נאָר אויב דער רשימה כּולל בלויז איין עלעמענט, אַז איז צו זיין אויסגעשטעלט. אזוי, אין סדר צו בעל אַ פּראָגראַממינג פונקציאָנירן ווי אַ שנעל סאָרט, עס איז נייטיק צו וויסן די אַרבעט פון נידעריקער-מדרגה אַלגערידאַמז: אַ) די ברירה פון די באַזע מיטגליד; ב) אַ רשימה פון די מערסט עפעקטיוו פּערמיוטיישאַן צו פּראָדוצירן צוויי שטעלט מיט קלענערער און גרעסערע וואַלועס.

באקענען מיט ערשטער פּרינציפּן. ווען טשוזינג די באַזע מיטגליד, זאָל יידילי ווערן אויסגעקליבן פון דער רשימה פון דורכשניטלעך. דעמאָלט אויף די ברעכן איז צעטיילט אין צוויי גלייַך כאַווז. נאָר רעכענען די דורכשניטלעך ווערט אין דער רשימה איז זייער שווער, אַזוי אַפֿילו די fastest סאָרטינג בייפּאַסיז דעם קאַלקולוס זייַט. אבער די ברירה פון די גרונט עלעמענט מיט די מאַקסימום אָדער מינימום ווערט - אויך ניט דער בעסטער אָפּציע. אין פאַל אַזאַ פעסטקייַט פון איינער קריייץ ליידיק רשימות וועט זיין געראַנטיד, און די רגע פול. בכן די מסקנא אַז ווי די באַזע מיטגליד זאָל זיין אויסדערוויילט איינער וואָס איז נעענטער צו די דורכשניטלעך, אָבער אויף די מאַקסימום און מינימום.

אַמאָל אַ ברירה איז באשלאסן, איר קענען גיינ ווייַטער צו די דיקאַמפּאָוזישאַן אַלגערידאַם. דעם אַזוי-גערופֿן ינער לופּס שנעל סאָרט. אַלץ איז געבויט אויף צוויי גיך אַקסעס ינדעקסיז: ערשטער גיין איבער די יסודות פון לינקס צו רעכט, די רגע, אויף די פאַרקערט, פון רעכט צו לינקס. הייבט אָפּעראַציע דורכפירונג רעכט: די אינדעקס איז אויף דער רשימה און פאַרגלייַכן אַלע די וואַלועס צו די הויפּט. די ציקל איז גאַנץ ווען די עלעמענט איז ווייניקער ווי אָדער גלייַך צו די באַסעלינע. אַז איז, עס איז אַ פאַרגלייַך און דיקריסיז די ווערט פון די אינדעקס. אויף די לינקס האַנט ווען די אַרבעט איז פאַרטיק גרעסער ווי אָדער גלייַך ווערט. דאָ, די פאַרגלייַך ווערט ינקריסאַז.

אין דעם בינע פון פּאַרטישאַנינג אַלגערידאַם וואָס קאַמפּרייזיז קוויקקסאָרט, צוויי סיטואַטיאָנס קען שטיי אויף. דער ערשטער איז אַז דער אינדעקס אויף די לינקס איז ווייניקער ווי רעכט. דאס ינדיקייץ אַ טעות, דעמאָלט דאָרט זענען עלעמענטן אויף וואָס עס איז געווען סטייטיד אין דער רשימה זענען אין די אומרעכט סדר. רעזולטאַט - טוישן זייער ערטער. די רגע סיטואַציע איז ווען ביידע פון די זייַל איז גלייַך צו אָדער קראָסט. דאס ינדיקייץ אַ מצליח צעשיידונג פון דער רשימה, וואָס איז, די אַרבעט איז איצט גאַנץ.