[Powered by Google Translate] [ינסערטיאָן סאָרט] [טאַמי מאַקווילליאַם] [האַרוואַרד אוניווערסיטעט] [דאס איז CS50.TV] זאל ס נעמען אַ קוק בייַ ינסערשאַן סאָרט, אַ אַלגערידאַם פֿאַר גענומען אַ רשימה פון נומערן און סאָרטינג זיי. אַ אַלגערידאַם, געדענקען, איז פשוט אַ שריט-דורך-שריט פּראָצעדור פֿאַר אַקאַמפּלישינג אַ אַרבעט. די גרונט געדאַנק הינטער ינסערשאַן סאָרט, איז צו טיילן אונדזער רשימה אין צוויי פּאָרשאַנז, אַ אויסגעשטעלט חלק און אַ ונסאָרטעד חלק. 

אין יעדער שריט פון די אַלגערידאַם, אַ נומער איז אריבערגעפארן פון די ונסאָרטעד חלק צו די אויסגעשטעלט חלק ביז יווענטשאַוואַלי די גאנצע רשימה איז אויסגעשטעלט. דאָ איז די רשימה פון זעקס ונסאָרטעד נומערן - 23, 42, 4, 16, 8, און 15. זינט די נומערן זענען נישט אַלע אין אַסענדינג סדר, זיי ניטאָ ונסאָרטעד. זינט מיר האָבן נישט אנגעהויבן סאָרטינג נאָך, מיר וועט באַטראַכטן אַלע זעקס עלעמענטן אונדזער ונסאָרטעד חלק. 

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

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

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

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

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

אַלע רעכט. איצט, מיר האָבן פיר אויסגעשטעלט יסודות און צוויי ונסאָרטעד עלעמענטן. אַזוי, לאָזן ס מאַך די 8 אין די אויסגעשטעלט חלק. אַכט איז ווייניקער ווי 42. אַכט איז ווייניקער ווי 23. און 8 איז ווייניקער ווי 16. אבער 8 איז גרעסער ווי 4. אַזוי, מיר 'ד ווי צו אַרייַנלייגן די 8 צווישן די 4 און די 16. און איצט מיר נאָר האָבן איינער מער עלעמענט לינקס צו סאָרט - די 15. פופצן איז ווייניקער ווי 42, פופצן איז ווייניקער ווי 23. און 15 איז ווייניקער ווי 16. אבער 15 איז גרעסער ווי 8. 

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

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

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

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

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

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

אַז מיטל וואָס ינסערשאַן סאָרט האט אַ בעסטער-פאַל פאָרשטעלונג פון N, וואָס מיר פאָרשטעלן מיט Ω (N). און אַז ס עס פֿאַר ינסערשאַן סאָרט, נאָר איינער פון די פילע אַלגערידאַמז מיר קענען נוצן צו סאָרט אַ רשימה. מייַן נאָמען איז טאַמי, און דאָס איז קס50. [CS50.TV] אָה, איר נאָר קענען נישט האַלטן אַז אַמאָל עס סטאַרץ. אָה, מיר האבן וואָס - >> בום!