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

דער ערשטער איז סעלעקציע סאָרט. די גרונט געדאַנק הינטער סעלעקציע סאָרט איז געפינען די קלענסטער ונסאָרטעד עלעמענט אין אַ מענגע און ויסבייַטן עס מיט דער ערשטער ונסאָרטעד עלעמענט פון אַז מענגע. מיר געזאגט אַז די ערגסטע-פאַל לויפן צייַט פון וואָס איז N סקווערד. און אויב איר ווילן צו צוריקרופן וואָס, נעמען אַ קוק אין די סעלעקציע סאָרט ווידעא. דער בעסטער-פאַל לויפן צייַט איז אויך N סקווערד. 

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

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

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

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

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

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

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

איך בין דאַג לויד, דאָס איז קס50.