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

אַזוי לאָזן ס גיין דורך קוויקקסאָרטינג דעם מענגע פון ​​ינטאַדזשערז פון קלענסטער צו גרעסטן. דאָ מיר האָבן די ינטאַדזשערז 6, 5, 1, 3, 8, 4, 7, 9, און 2. ערשטער, מיר קלייַבן די לעצט עלעמענט פון דעם מענגע - אין דעם פאַל, צוויי - און רופן אַז די "דרייפּונקט". ווייַטער, מיר אָנהייבן צו קוקן בייַ צוויי זאכן - איינער, די לאָואַסט אינדעקס, וואָס איך וועט אָפּשיקן צו ווי סטייינג צו די רעכט פון די וואַנט, און צוויי, די לעפטמאָסט עלעמענט, וואָס איך וועט רופן די "קראַנט עלעמענט. "וואָס מיר ניטאָ געגאנגען צו טאָן איז קוקן אַלע די אנדערע עלעמענטן, אנדערע ווי די דרייפּונקט, און שטעלן אַלע די יסודות קלענערער ווי די דרייפּונקט צו די לינקס פון די וואַנט און אַלע די גרעסערע ווי די דרייפּונקט צו די רעכט פון די וואַנט. דעמאָלט, לעסאָף, מיר וועט פאַלן די דרייפּונקט רעכט אויף אַז וואַנט צו לייגן עס צווישן אַלע די נומערן קלענערער ווי עס און אַלע די נומערן גרעסערע. 

אַזוי לאָזן ס טאָן אַז. קלייַבן אַרויף די 2, שטעלן די וואַנט בייַ די אָנהייב, און רופן די 6 די "קראַנט עלעמענט. "אזוי מיר ווילן צו קוקן בייַ אונדזער איצטיקן עלעמענט, די 6. און זינט עס ס גרעסערע ווי די 2, מיר לאָזן עס עס צו די רעכט פון די וואַנט. דעמאָלט, מיר מאַך אויף צו קוקן בייַ די 5 ווי אונדזער קראַנט עלעמענט און זען אַז דעם איז, ווידער, גרעסערע ווי די דרייפּונקט, אַזוי מיר לאָזן עס ווו עס איז אויף די רעכט זייַט פון די וואַנט. מיר מאַך אויף. אונדזער איצטיקן עלעמענט איז איצט 1, און - טאַקע. דעם איז אַנדערש איצט. די קראַנט עלעמענט איז איצט קלענערער ווי די דרייפּונקט, אַזוי מיר ווילן צו לייגן עס צו די לינקס פון די וואַנט. צו טאָן דאָס, לאָזן ס נאָר באַשטימען די קראַנט עלעמענט מיט די לאָואַסט אינדעקס זיצן נאָר צו די רעכט פון די וואַנט. איצט, מיר מאַך די וואַנט זיך איין אינדעקס אַזוי די 1 איז אויף די לינק זייַט פון די וואַנט איצט. 

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

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

מיר דעמאָלט איבערחזרן דעם פּראָצעס פֿאַר די סובאַררייַס לינקס און רעכט פון די דרייפּונקט. זינט די לעצטע סובאַררייַ איז בלויז איין עלעמענט לאַנג, מיר וויסן אַז ס שוין אויסגעשטעלט ווייַל ווי קענען איר זיין אויס פון סדר אויב איר 'רע בלויז איין עלעמענט? פֿאַר די רעכט זייַט פון די סובאַררייַ, מיר זען אַז די דרייפּונקט איז 5, און די וואַנט איז פּונקט לינקס פון די 6. און די קראַנט עלעמענט אויך סטאַרץ אויס ווי די 6. אַזוי 6 איז גרעסער ווי 5. מיר לאָזן עס ווו עס איז אויף די רעכט זייַט פון די וואַנט. איצט, מאָווינג אויף, 3 איז ווייניקער ווי 5. אַזוי מיר באַשטימען עס מיט דער ערשטער עלעמענט פּונקט רעכט פון די וואַנט. איצט, איך אריבערגעפארן די וואַנט זיך איין. איצט, מאָווינג אויף צו די 8. 8 איז גרעסער ווי 5, און אַזוי מיר לאָזן עס. די 4 איז ווייניקער ווי 5, אַזוי מיר באַשטימען עס. און אויף. און אויף. 

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

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

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

מייַן נאָמען איז מארק גראָזען-סמיט, און דעם איז קס50. 

פֿאַר פּאַשטעס, לאָזן ס יבערנעמען אַז די דאס זענען נאָר ינטאַדזשערז, אָבער וויסן אַז קוויקקסערט - קוויקקסערט? נעבעכדיק. 

דאָ מיר האָבן די ינטאַדזשערז 6, 5, 1, 3, 8, 4, 9. 

רעדנער 1: טאַקע? 

רעדנער 2: דו זאלסט נישט האַלטן עס. 

רעדנער 1: טאַקע?