[Powered by Google Translate] [בלאָז סאָרט]
[זשעקסאן סטיינגקאַמפּ האַרוואַרד אוניווערסיטעט]
[דעם איז קס50. קס50טוו]
בלאָז סאָרט איז אַ בייַשפּיל פון אַ סאָרטינג אַלגערידאַם -
וואָס איז, אַ פּראָצעדור פֿאַר סאָרטינג אַ גאַנג פון עלעמענטן אין
אַסענדינג אָדער אראפנידערן סדר.
פֿאַר בייַשפּיל, אויב איר געוואלט צו סאָרט אַ מענגע קאַנסיסטינג פון די נומערן
[3, 5, 2, 9], אַ ריכטיק ימפּלאַמענטיישאַן פון בלאָז סאָרט וואָלט צוריקקומען די
אויסגעשטעלט מענגע [2, 3, 5, 9] אין אַסענדינג סדר.
איצט, איך בין געגאנגען צו דערקלערן אין פּסעודאָקאָדע ווי די אַלגערידאַם אַרבעט.
>> זאל ס זאָגן מיר רע סאָרטינג אַ רשימה פון 5 ינטאַדזשערז - 3, 2, 9, 6, און 5.
די אַלגערידאַם סטאַרץ דורך קוקן בייַ די ערשטער צוויי עלעמענטן, 3 און 2,
און קאָנטראָלירונג אויב זיי ניטאָ אויס פון סדר קאָרעוו צו יעדער אַנדערער.
זיי זענען - 3 איז גרעסער ווי 2.
צו זייַן אין אַסענדינג סדר, זיי זאָל זייַן די אנדערע וועג אַרום.
אַזוי, מיר ויסבייַטן זיי.
איצט דער רשימה קוקט ווי דאָס: [2, 3, 9, 6, 5].
>> ווייַטער, מיר קוקן אין די רגע און דריט עלעמענטן, 3 און 9.
זיי ניטאָ אין דער ריכטיק סדר קאָרעוו צו יעדער אַנדערער.
וואָס איז, 3 איז ווייניקער ווי 9 אַזוי די אַלגערידאַם טוט נישט ויסבייַטן זיי.
ווייַטער, מיר קוקן בייַ 9 און 6. זיי ניטאָ אויס פון סדר.
>> אַזוי, מיר דאַרפֿן צו ויסבייַטן זיי ווייַל 9 איז גרעסער ווי 6.
לאַסטלי, מיר קוקן אין די לעצטע צוויי ינטאַדזשערז, 9 און 5.
זיי ניטאָ אויס פון סדר, אַזוי זיי מוזן זייַן סוואָפּט.
נאָך דער ערשטער גאַנץ פאָרן דורך דער רשימה,
עס קוקט ווי דאָס: [2, 3, 6, 5, 9].
נישט שלעכט. עס ס כּמעט אויסגעשטעלט.
אבער מיר דאַרפֿן צו לויפן דורך דער רשימה ווידער צו באַקומען עס גאָר אויסגעשטעלט.
צוויי איז ווייניקער ווי 3, אַזוי מיר טאָן ניט ויסבייַטן זיי.
>> דרייַ איז ווייניקער ווי 6, אַזוי מיר טאָן ניט ויסבייַטן זיי.
זעקס איז גרעסער ווי 5. מיר סוואָפּט.
זעקס איז ווייניקער ווי 9. מיר טאָן ניט ויסבייַטן.
נאָך די רגע פאָרן דורך, עס קוקט ווי דאָס: [2, 3, 5, 6, 9]. גאנץ.
איצט, לאָזן ס שרייַבן עס אין פּסעודאָקאָדע.
בייסיקלי, פֿאַר יעדער עלעמענט אין דער רשימה, מיר דאַרפֿן צו קוקן בייַ אים
און די עלעמענט גלייַך צו זייַן רעכט.
אויב זיי זענען אויס פון סדר קאָרעוו צו יעדער אנדערע - וואָס איז, אויב דער עלעמענט אויף די לינקס
איז גרעסער ווי דער איינער אויף די רעכט - מיר זאָל ויסבייַטן די צוויי יסודות.
>> מיר טאָן דעם פֿאַר יעדער עלעמענט פון דער רשימה, און מיר 'ווע געמאכט איינער פאָרן דורך.
איצט מיר נאָר האָבן צו טאָן דעם פאָרן-דורך גענוג מאל צו ענשור די רשימה
איז גאָר, רעכט אויסגעשטעלט.
אבער ווי פילע מאל טאָן מיר האָבן צו פאָרן דורך די רשימה צו
גאַראַנטירן אַז מיר רע געטאן?
נו, די ערגסט-פאַל סצענאַר איז אויב מיר האָבן אַ גאָר קאַפּויער רשימה.
דעמאָלט עס נעמט אַ נומער פון פאָרן-טרוז גלייַך צו די נומער
פון עלעמענטן N-1.
אויב דאָס טוט נישט מאַכן זינען ינטויטיוולי, טראַכטן פון אַ פּשוט פאַל - דער רשימה [2, 1].
>> דאס איז געגאנגען צו נעמען איין פאָרן-דורך צו סאָרט ריכטיק.
[3, 2, 1] - די ערגסט פאַל איז אַז מיט 3 יסודות אויסגעשטעלט קאַפּויער,
עס ס געגאנגען צו נעמען 2 יטעראַטיאָנס צו סאָרט.
נאָך איינער יטעראַטיאָן, עס ס [2, 1, 3].
די רגע ייעלדס די אויסגעשטעלט מענגע [1, 2, 3].
אַזוי איר וויסן איר קיינמאָל האָבן צו גיין דורך די מענגע, אין אַלגעמיין,
מער ווי N-1 מאל, ווו ען איז די נומער פון עלעמענטן אין דער מענגע.
עס ס גערופן בלאָז סאָרט ווייַל דער גרעסטער יסודות טענד צו 'בלאָז-אַרויף'
צו די רעכט שיין געשווינד.
אין פאַקט, דעם אַלגערידאַם האט זייער טשיקאַווע נאַטור.
>> נאָך עם יטעראַטיאָנס דורך די גאנצע מענגע,
די ריגהטמאָסט ב עלעמענטן זענען געראַנטיד
צו זייַן אויסגעשטעלט אין זייער ריכטיק אָרט.
אויב איר ווילן צו זען דאָס פֿאַר זיך,
מיר קענען פּרובירן עס אויף אַ גאָר קאַפּויער רשימה [9, 6, 5, 3, 2].
נאָך איינער פאָרן דורך די גאנצע רשימה,
[געזונט פון שרייבן]
[6, 9, 5, 3, 2], [6, 5, 9, 3, 2], [6, 5, 3, 9, 2], [6, 5, 3, 2, 9]
די ריגהטמאָסט עלעמענט 9 איז אין זייַן געהעריק אָרט.
נאָך די רגע פאָרן-דורך, די 6 וועט האָבן 'באַבאַלד-אַרויף' צו די
רגע ריגהטמאָסט אָרט.
די צוויי עלעמענטן אויף די רעכט - 6 און 9 - וועט זייַן אין זייער ריכטיק ערטער
נאָך דער ערשטער צוויי פאָרן-טרוז.
>> אַזוי, ווי קענען מיר נוצן דאָס צו אַפּטאַמייז די אַלגערידאַם?
נו, נאָך איינער יטעראַטיאָן דורך די מענגע
מיר טאָן נישט פאקטיש דאַרפֿן צו קאָנטראָלירן די ריגהטמאָסט עלעמענט
ווייַל מיר וויסן עס ס אויסגעשטעלט.
נאָך צוויי יטעראַטיאָנס, מיר וויסן פֿאַר זיכער די ריגהטמאָסט צוויי עלעמענטן זענען אין פּלאַץ.
אַזוי, אין אַלגעמיין, נאָך ק יטעראַטיאָנס דורך די פול מענגע,
קאָנטראָלירונג די לעצטע ק עלעמענטן איז יבעריק זינט מיר וויסן
זיי ניטאָ אין דער ריכטיק אָרט שוין.
>> אַזוי אויב איר ניטאָ סאָרטינג אַ מענגע פון ​​N עלעמענטן,
אויף דער ערשטער יטעראַטיאָן - יול האָבן צו סאָרט אַלע פון ​​די יסודות - דער ערשטער N-0.
אויף דער רגע יטעראַטיאָן, איר וועט האָבן צו קוקן אין אַלע פון ​​די יסודות אָבער די לעצט -
דער ערשטער N-1.
אן אנדער אַפּטאַמאַזיישאַן זאל זייַן צו טשעק אויב די רשימה איז שוין אויסגעשטעלט
נאָך יעדער יטעראַטיאָן.
אויב עס ס 'שוין אויסגעשטעלט, מיר טאָן ניט דאַרפֿן צו מאַכן קיין מער יטעראַטיאָנס
דורך דער רשימה.
ווי קענען מיר טאָן דעם?
נו, אויב מיר טאָן ניט מאַכן קיין סוואַפּס אויף אַ פאָרן-דורך פון דער רשימה,
עס ס 'קלאָר אַז די רשימה איז שוין אויסגעשטעלט ווייַל מיר האבן נישט ויסבייַטן עפּעס.
אַזוי מיר באשטימט טאָן ניט האָבן צו סאָרט ווידער.
>> טאָמער איר קען ינישאַלייז אַ פאָן בייַטעוודיק גערופן 'נישט אויסגעשטעלט' צו
פאַלש און טוישן עס צו אמת אויב איר האָבן צו ויסבייַטן קיין יסודות אויף
איינער יטעראַטיאָן דורך די מענגע.
אָדער סימילאַרלי, מאַכן אַ קאָונטער צו ציילן ווי פילע סוואַפּס איר מאַכן
אויף קיין געגעבן יטעראַטיאָן.
אין די סוף פון אַ יטעראַטיאָן, אויב איר האט ניט ויסבייַטן קיין פון די עלעמענטן,
איר וויסן די רשימה איז שוין אויסגעשטעלט און איר ניטאָ געטאן.
בלאָז סאָרט, ווי אנדערע סאָרטינג אַלגערידאַמז, קענען זייַן
טוויקט צו אַרבעטן פֿאַר קיין עלעמענטן וואָס האָבן אַן אָרדערינג אופֿן.
>> וואָס איז, געגעבן צוויי עלעמענטן איר האָבן אַ וועג צו זאָגן אויב דער ערשטער איינער
איז גרעסער ווי, גלייַך צו אָדער ווייניקער ווי די רגע.
פֿאַר בייַשפּיל, איר קען סאָרט אותיות פון דעם אלפאבעט דורך זאגן
אַז אַ <בייטן, בייטן <C, אאז"ו ו
אָדער איר קען סאָרט טעג פון די וואָך ווו זונטאג איז ווייניקער ווי מאנטיק
וואָס איז ווייניקער ווי דינסטאג.
>> בלאָז סאָרט איז דורך קיין מיטל אַ זייער עפעקטיוו אָדער פעסט סאָרטינג אַלגערידאַם.
זייַן ערגסט-פאַל רונטימע איז גרויס אָ פון N ²
ווייַל איר האָבן צו מאַכן N יטעראַטיאָנס דורך אַ רשימה
קאָנטראָלירונג אַלע N יסודות יעדער פאָרן-דורך, נקסן = N ².
דאס לויפן צייַט מיטל וואָס ווי די נומער פון עלעמענטן איר ניטאָ סאָרטינג ינקריסיז,
די לויפן צייַט ינקריסיז קוואַדראַטיקאַללי.
>> אבער אויב עפעקטיווקייַט איז נישט אַ הויפּט דייַגע פון ​​דיין פּראָגראַם
אָדער אויב איר ניטאָ בלויז סאָרטינג אַ קליין נומער פון עלעמענטן,
איר זאל געפֿינען בלאָז סאָרט נוצלעך ווייַל
עס ס איינער פון די סימפּלאַסט סאָרטינג אַלגערידאַמז צו פֿאַרשטיין
און צו קאָד.
עס ס אויך אַ גרויס וועג צו באַקומען דערפאַרונג מיט איבערזעצן אַ טעאָרעטיש
אַלגערידאַם אין פאַקטיש פאַנגקשאַנינג קאָד.
נו, אַז ס בלאָז סאָרט פֿאַר איר. דאַנק פֿאַר וואַטשינג.
CS50.TV