סאָרטינג טעקניקס אין פּראָגראַממינג: סאָרטינג "בלאָז"

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

ווו האט אַזאַ אַ ומגעוויינטלעך נאָמען?

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

באַשרייַבונג פון די אַלגערידאַם

בלאָז סאָרט איז געטאן ווי גייט:

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

אַפֿילו קירצער אַלגערידאַם פון אַ פּראָגראַם קענען זיין געשריבן ווי:

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

פּסעודאָקאָדע באזירט אויף די אַלגערידאַם דיסקרייבד

די סימפּלאַסט ימפּלאַמענטיישאַן איז געטראגן אויס ווי גייט:

סאָרטיראָווקאַ_פּוזירקאָם פּראָצעדור;

אָנהייב

ציקל פֿאַר דזש פֿון נאַטשאַלניי_ינדעקס צו קאָנעטשיי_ינדעקס;

ציקל פֿאַר איך פֿון נאַטשאַלניי_ינדעקס צו קאָנעטשיי_ינדעקס-1;

אויב מאַססיוו [איך]> מאַססיוו [איך , + 1] (ערשטער עלעמענט גרעסער ווי אַ רגע), דעמאָלט:

(טוישן ערטער וואַלועס);

עק

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

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

סאָרטיראָווקאַ_פּוזירקאָם פּראָצעדור;

אָנהייב

סאָרטיראָווקאַ = אמת;

ציקל ביז סאָרטיראָווקאַ = אמת;

סאָרטיראָווקאַ = פאַלש;

ציקל פֿאַר איך פֿון נאַטשאַלניי_ינדעקס צו קאָנעטשיי_ינדעקס-1;

אויב מאַססיוו [איך]> מאַססיוו [איך , + 1] (ערשטער עלעמענט גרעסער ווי אַ רגע), דעמאָלט:

(טוישן יסודות ערטער);

סאָרטיראָווקאַ = אמת; (ידענטיפיעד אַז דער וועקסל האט שוין געמאכט).

סוף.

לימיטיישאַנז

די הויפּט כיסאָרן - די געדויער פון דעם פּראָצעס. ווי פיל צייַט איז געטאן סאָרטינג אַלגערידאַם בלאָז?

פירן צייַט איז קאַלקיאַלייטיד פון די נומער פון קוואַדראַט נומערן אין די מענגע - דער סוף רעזולטאַט פון עס איז פּראַפּאָרשאַנאַל.

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

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

כשיוועס

בלאָז סאָרט איז זייער גרינג צו פֿאַרשטיין. די קורריקולאַ פון טעכניש אוניווערסיטעטן אין דעם לערנען פון די אָרדערינג יסודות פון זייַן מענגע פאָרן אין דער ערשטער אָרט. דעם אופֿן איז גרינג צו ינסטרומענט ביידע די Delphi פּראָגראַממינג שפּראַך (ל (Delphi), און די C / C ++ (C / C פּלוס פּלוס), אַ ינקרעדאַבלי פּשוט וואַלועס פון אָרט אַלגערידאַם אין די רעכט סדר און אין די פּאַסקאַל (פּאַסקאַל). בלאָז סאָרט איז ידעאַל פֿאַר ביגינערז.

רעכט צו דער דראָבאַקס פון די אַלגערידאַם איז ניט געוויינט אין עקסטראַקורריקולאַר צוועקן.

וויסואַל סאָרטינג פּרינציפּ

דער ערשט מיינונג פון די מענגע 8 22 4 74 44 37 1 7

שריט 1 8 22 4 74 44 37 1 7

8 22 4 74 44 1 37 7

8 22 4 74 1 44 37 7

8 22 4 1 74 44 37 7

8 22 1 4 74 44 37 7

8 1 22 4 74 44 37 7

1 8 22 4 74 44 37 7

שריט 2 1 8 22 4 74 44 7 37

1 8 22 4 74 7 44 37

1 8 22 4 7 74 44 37

1 8 22 4 7 74 44 37

1 8 4 22 7 74 44 37

1 4 8 22 7 74 44 37

שריט 3 1 4 8 22 7 74 37 44

1 4 8 22 7 37 74 44

1 4 8 22 7 37 74 44

1 4 8 7 22 37 74 44

1 4 7 8 22 37 74 44

שריט 4 1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

שריט 5 1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

שריט 6 1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

שריט 7 1 4 7 8 22 37 44 74

בלאָז סאָרט למשל אין פּאַסקאַל

למשל:

קאָנסט קאָל_מאַס = 10;

וואַר מאַססיוו: מענגע [1..קאָל_מאַס] פון ינטעגער;

אַ, ב, ק: ינטעגער;

אָנהייבן

ווריטעלן ( 'ינפּוט', קאָל_מאַס, 'יסודות פון מענגע');

פֿאַר אַ: = 1 צו קאָל_מאַס טאָן רעאַדלן (מאַססיוו [אַ ]);

פֿאַר אַ: = 1 צו קאָל_מאַס-1 טאָן נעמען

פֿאַר ב: = אַ 1 צו קאָל_מאַס טאָן נעמען

אויב מאַססיוו [אַ]> מאַססיוו [ ב] דעריבער נעמען

ק: = מאַססיוו [אַ]; מאַססיוו [אַ]: = מאַססיוו [ ב]; מאַססיוו [b]: = ק;

סוף;

סוף;

סוף;

ווריטעלן ( 'נאָך סאָרט');

פֿאַר אַ: = 1 צו קאָל_מאַס טאָן ווריטעלן (מאַססיוו [אַ ]);

סוף.

לעמאָשל בלאָז סאָרטינג אין C שפּראַך (C)

למשל:

#ינקלודע

#ינקלודע

ינט הויפּט (ינט אַרגק, טשאַר * אַרגוו [])

{

ינט מאַססיוו [8] = {36, 697, 73, 82, 68, 12, 183, 88}, איך, FF;

פֿאַר (;;) {

FF = 0;

פֿאַר (איך = 7; איך> 0; איך -) {

אויב (מאַססיוו [איך] <מאַססיוו [י- 1]) {

ויסבייַטן (מאַססיוו [איך], מאַססיוו [י- 1]);

FF ++;

}

}

אויב (FF == 0) ברעכן;

}

געטטש (); // אַרויסווייַזן פאַרהאַלטן

צוריקקומען 0;

}.