[Powered by Google Translate] טאַמי: זאל ס נעמען אַ קוק בייַ סעלעקציע סאָרט, אַ אַלגערידאַם
פֿאַר גענומען אַ רשימה פון נומערן און סאָרטינג זיי.
אַ אַלגערידאַם, געדענקען, איז פשוט אַ שריט-דורך-שריט
פּראָצעדור פֿאַר אַקאַמפּלישינג אַ אַרבעט.
די גרונט געדאַנק הינטער סעלעקציע סאָרט איז צו טיילן
אונדזער רשימה אין צוויי פּאָרשאַנז -
אַ אויסגעשטעלט חלק און אַ ונסאָרטעד חלק.
אין יעדער שריט פון די אַלגערידאַם, אַ נומער איז אריבערגעפארן פון דער
ונסאָרטעד חלק צו די אויסגעשטעלט חלק ביז יווענטשאַוואַלי די
גאנצע רשימה איז אויסגעשטעלט.
אַזוי דאָ ס אַ רשימה פון זעקס נומערן -
23, 42, 4, 16, 8, און 15.
רעכט איצט די גאנצע רשימה איז געהאלטן ונסאָרטעד.
אפילו כאָטש אַ נומער ווי מאי 16 שוין זייַן אין זייַן ריכטיק
אָרט, אונדזער אַלגערידאַם האט קיין וועג פון געוואוסט אַז ביז די
גאנצע רשימה איז אויסגעשטעלט.
אַזוי מיר וועט באַטראַכטן יעדער נומער צו זייַן ונסאָרטעד ביז מיר סאָרט
עס זיך.
מיר וויסן אַז מיר ווילן די רשימה צו זייַן אין אַסענדינג סדר.
אַזוי מיר וועט ווילן צו בויען אַרויף די אויסגעשטעלט חלק פון אונדזער רשימה
פון לינקס צו רעכט, קלענסטער צו גרעסטן.
צו טאָן וואָס, מיר וועט דאַרפֿן צו געפֿינען די מינימום ונסאָרטעד עלעמענט
און שטעלן אים אין די סוף פון די אויסגעשטעלט חלק.
זינט דעם רשימה איז ניט אויסגעשטעלט, די בלויז וועג צו טאָן וואָס איז צו
קוק אין יעדער עלעמענט אין דער ונסאָרטעד חלק, רימעמבערינג
וואָס עלעמענט איז די לאָואַסט און קאַמפּערינג
יעדער עלעמענט צו וואָס.
אַזוי מיר וועט ערשטער קוקן בייַ די 23.
דאס איז דער ערשטער עלעמענט מיר ווע געזען, אַזוי מיר וועט געדענקען
עס ווי די מינימום.
ווייַטער מיר וועט קוקן אין 42.
42 איז גרעסערע ווי 23, אַזוי 23 איז נאָך די מינימום.
ווייַטער איז די 4 וואָס איז ווייניקער ווי 23, אַזוי מיר וועט געדענקען 4
ווי די נייַ מינימום.
ווייַטער איז 16 וואָס איז גרעסערע ווי 4, אַזוי 4
איז נאָך די מינימום.
8 איז גרעסערע ווי 4, און 15 איז גרעסערע ווי 4, אַזוי 4 מוזן זייַן
דער קלענסטער ונסאָרטעד עלעמענט.
אַזוי אַפֿילו כאָטש ווי יומאַנז מיר קענען תיכף זען אַז 4 איז
די מינימום עלעמענט, אונדזער אַלגערידאַם דאַרף צו קוקן בייַ
יעדער ונסאָרטעד עלעמענט, אַפֿילו נאָך מיר ווע געפונען די 4 - דער
מינימום עלעמענט.
אַזוי איצט אַז מיר ווע געפונען די מינימום עלעמענט, 4, מיר וועט וועלן
צו מאַך עס אין די אויסגעשטעלט חלק פון די רשימה.
זינט דאס איז דער ערשטער שריט, דעם מיטל מיר וועלן צו שטעלן 4 בייַ
דער אָנהייב פון דער רשימה.
רעכט איצט 23 איז בייַ דעם אָנהייב פון דער רשימה, אַזוי
לאָזן ס ויסבייַטן די 4 און די 23.
אַזוי איצט אונדזער רשימה קוקט ווי דעם.
מיר וויסן אַז 4 מוזן זייַן אין זייַן לעצט אָרט, ווייַל עס איז
ביידע דער קלענסטער עלעמענט און די עלעמענט אין די אָנהייב
פון די רשימה.
אַזוי דעם מיטל וואָס מיר טאָן ניט אלץ דאַרפֿן צו מאַך עס ווידער.
אַזוי לאָזן ס איבערחזרן דעם פּראָצעס צו לייגן אן אנדער עלעמענט צו די
אויסגעשטעלט חלק פון די רשימה.
מיר וויסן אַז מיר טאָן ניט דאַרפֿן צו קוקן בייַ די 4, ווייַל עס ס
שוין אויסגעשטעלט.
אַזוי מיר קענען אָנהייבן בייַ די 42, וואָס מיר וועט געדענקען ווי דער
מינימום עלעמענט.
אַזוי ווייַטער מיר וועט קוקן אין די 23 וואָס איז ווייניקער ווי 42, אַזוי מיר
געדענקען 23 איז די נייַ מינימום.
ווייַטער מיר זען די 16 וואָס איז ווייניקער ווי 23, אַזוי
16 איז די נייַ מינימום.
איצט מיר קוקן אין די 8 וואָס איז ווייניקער ווי 16, אַזוי
8 איז די נייַ מינימום.
און לעסאָף 8 איז ווייניקער ווי 15, אַזוי מיר וויסן אַז 8 איז אַ מינימום
ונסאָרטעד עלעמענט.
אַזוי אַז מיטל מיר זאָל צוגעבן 8 צו די אויסגעשטעלט
חלק פון די רשימה.
רעכט איצט 4 איז דער בלויז אויסגעשטעלט עלעמענט, אַזוי מיר ווילן צו אָרט
די 8 ווייַטער צו די 4.
זינט 42 איז דער ערשטער עלעמענט אין דער ונסאָרטעד חלק פון די
רשימה, מיר וועט ווילן צו ויסבייַטן די 42 און די 8.
אַזוי איצט אונדזער רשימה קוקט ווי דעם.
4 און 8 פאָרשטעלן די אויסגעשטעלט חלק פון דער רשימה, און די
רוען נומערן פאָרשטעלן די ונסאָרטעד
חלק פון די רשימה.
אַזוי לאָזן ס פאָרזעצן מיט אנדערן יטעראַטיאָן.
מיר אָנהייבן מיט 23 דעם צייַט, זינט מיר טאָן ניט דאַרפֿן צו קוקן בייַ
די 4 און דער 8 ענימאָר ווייַל זיי ווע
שוין געווען אויסגעשטעלט.
16 איז ווייניקער ווי 23, אַזוי מיר וועט געדענקען
16 ווי די נייַ מינימום.
16 איז ווייניקער ווי 42, אָבער 15 איז ווייניקער ווי 16, אַזוי 15 מוזן זייַן
די מינימום ונסאָרטעד עלעמענט.
אַזוי איצט מיר ווילן צו ויסבייַטן די 15 און די 23 צו
געבן אונדז דעם רשימה.
די אויסגעשטעלט חלק פון דער רשימה באשטייט פון 4, 8 און 15, און
די יסודות זענען נאָך ונסאָרטעד.
אבער עס פּונקט אַזוי כאַפּאַנז אַז דער ווייַטער ונסאָרטעד עלעמענט, 16,
איז שוין אויסגעשטעלט.
אבער, עס ס קיין וועג פֿאַר אונדזער אַלגערידאַם צו וויסן אַז 16
איז שוין אין זייַן ריכטיק אָרט, אַזוי מיר נאָך דאַרפֿן צו
איבערחזרן פּונקט דער זעלביקער פּראָצעס.
אַזוי מיר זען אַז 16 איז ווייניקער ווי 42, און 16 איז ווייניקער ווי 23, אַזוי
16 מוזן זייַן די מינימום עלעמענט.
עס ס אוממעגלעך צו ויסבייַטן דעם עלעמענט מיט זיך, אַזוי מיר קענען
פשוט לאָזן עס אין דעם אָרט.
אַזוי מיר דאַרפֿן איינער מער פאָרן פון אונדזער אַלגערידאַם.
42 איז גרעסער ווי 23, אַזוי 23 מוזן זייַן די
מינימום ונסאָרטעד עלעמענט.
אַמאָל מיר ויסבייַטן די 23 און די 42, מיר סוף זיך מיט אונדזער לעצט
אויסגעשטעלט רשימה -
4, 8, 15, 16, 23, 42.
מיר וויסן 42 מוזן זייַן אין די ריכטיק אָרט זינט עס ס די
בלויז עלעמענט לינקס, און אַז ס סעלעקציע סאָרט.
זאל ס איצט פאָרמאַלייז אונדזער אַלגערידאַם מיט עטלעכע
פּסעודאָקאָדע.
אויף שורה איין, מיר קענען זען אַז מיר דאַרפֿן צו ויסשטימען איבער
יעדער עלעמענט פון דער רשימה.
אַחוץ די לעצטע עלעמענט, זינט די 1 עלעמענט
רשימה איז שוין אויסגעשטעלט.
אויף שורה צוויי, מיר באַטראַכטן די ערשטער עלעמענט פון דער ונסאָרטעד
חלק פון דער רשימה צו זייַן דעם מינימום, ווי מיר האט מיט אונדזער
בייַשפּיל, אַזוי מיר האָבן עפּעס צו פאַרגלייַכן צו.
שורה דרייַ הייבט אַ רגע שלייף אין וואָס מיר יטעראַטע איבער
יעדער ונסאָרטעד עלעמענט.
מיר וויסן אַז נאָך איך יטעראַטיאָנס, די אויסגעשטעלט חלק
פון אונדזער רשימה מוזן האָבן איך יסודות אין עס זינט יעדער שריט
סאָרץ איין עלעמענט.
אַזוי דער ערשטער ונסאָרטעד עלעמענט מוזן זייַן אין שטעלע איך פּלוס 1.
אויף שורה פיר, מיר פאַרגלייַכן די קראַנט עלעמענט צו די מינימום
עלעמענט וואָס מיר ווע געזען אַזוי ווייַט.
אויב די קראַנט עלעמענט איז קלענערער ווי די מינימום
עלעמענט, דעמאָלט מיר געדענקען די קראַנט עלעמענט ווי די נייַ
מינימום אויף שורה פינף.
צום סוף, אויף שורות זעקס און זיבן, מיר ויסבייַטן די מינימום
עלעמענט מיט דעם ערשטער ונסאָרטעד עלעמענט, דערמיט
אַדינג עס צו די אויסגעשטעלט חלק פון די רשימה.
אַמאָל מיר האָבן אַ אַלגערידאַם, אַ וויכטיק קשיא צו פרעגן
זיך ווי פּראָוגראַמערז איז ווי לאַנג האט וואָס נעמען?
מיר וועט ערשטער פרעגן די קשיא ווי לאַנג טוט עס נעמען פֿאַר דעם
אַלגערידאַם צו לויפן אין די ערגסט פאַל?
צוריקרופן מיר פאָרשטעלן דעם פליסנדיק
צייַט מיט גרויס אָ נאָוטיישאַן.
אין סדר צו באַשליסן די מינימום ונסאָרטעד עלעמענט, מיר
יסענשאַלי האט צו פאַרגלייַכן יעדער עלעמענט אין דער רשימה צו
יעדער אַנדערער עלעמענט אין דער רשימה.
ינטויטיוולי, דעם סאָונדס ווי אַן אָ פון N סקווערד אָפּעראַציע.
קוקן בייַ אונדזער פּסעודאָקאָדע, מיר אויך האָבן אַ שלייף נעסטעד ין
אן אנדער שלייף, וואָס טאַקע סאָונדס ווי אַן אָ
פון N סקווערד אָפּעראַציע.
אבער, געדענקען אַז מיר האבן נישט דאַרפֿן צו קוק איבער די
גאנצע רשימה ווען דיטערמאַנינג די מינימום ונסאָרטעד עלעמענט?
אַמאָל מיר געוואוסט אַז די 4 איז געווען אויסגעשטעלט, פֿאַר בייַשפּיל, מיר האבן ניט
דאַרפֿן צו קוקן בייַ אים ווידער.
אַזוי טוט דעם נידעריקער דער פליסנדיק צייַט?
פֿאַר אונדזער רשימה פון לענג 6, מיר דארף צו מאַכן פינף
קאַמפּעראַסאַנז פֿאַר דער ערשטער עלעמענט, פיר קאַמפּעראַסאַנז פֿאַר
די רגע עלעמענט, און אַזוי אויף.
אַז מיטל אַז די גאַנץ נומער פון טריט איז דער סאַכאַקל פון
די ינטאַדזשערז פון 1 צו די לענג פון די רשימה מינוס 1.
מיר קענען פאָרשטעלן דעם מיט אַ סאַמיישאַן.
מיר וועלן נישט גיין אין סאַמיישאַנז דאָ.
אבער עס טורנס אויס אַז דעם סאַמיישאַן איז גלייַך צו N מאל
N מינוס 1 איבער 2.
אָדער עקוויוואַלענטלי, N סקווערד איבער 2 מינוס N איבער 2.
ווען גערעדט וועגן אַסימפּטאָטיק רונטימע, דעם N סקווערד טערמין
איז געגאנגען צו באַהערשן דעם N טערמין.
אַזוי סעלעקציע סאָרט איז אָ פון N סקווערד.
צוריקרופן אַז אין אונדזער בייַשפּיל, סעלעקציע סאָרט נאָך דארף צו
טשעק אויב אַ נומער וואָס איז שוין אויסגעשטעלט
דארף צו זייַן אריבערגעפארן.
אַזוי אַז מיטל אַז אויב מיר געלאפן סעלעקציע סאָרט איבער אַן שוין
אויסגעשטעלט רשימה, עס וואָלט דאַרפן די זעלבע נומער פון טריט ווי עס
וואָלט ווען פליסנדיק איבער אַ גאָר ונסאָרטעד רשימה.
אַזוי סעלעקציע סאָרט האט אַ בעסטער פאַל פאָרשטעלונג פון N סקווערד,
וואָס מיר פאָרשטעלן מיט תוו N סקווערד.
און אַז ס עס פֿאַר סעלעקציע סאָרט.
נאָר איינער פון די פילע אַלגערידאַמז מיר קענען
נוצן צו סאָרט אַ רשימה.
מייַן נאָמען איז טאַמי, און דאָס איז קס50.