مرتب سازی تکنیک های برنامه نویسی در: مرتب سازی "حباب"

مرتب سازی حبابی است که نه تنها نظر گرفته می شود سریع ترین روش، علاوه بر این، آن را می بندد لیست کندترین راه هایی برای سازماندهی کنند. با این حال، مزایای آن است. بنابراین، روش های مرتب سازی حباب - بیشتر که نه یک راه حل طبیعی و منطقی برای این مشکل است، اگر شما می خواهید به ترتیب موارد در یک نظم خاص است. یک فرد عادی به صورت دستی، برای مثال، آن را به آنها استفاده - فقط با شهود.

از کجا چنین نام غیر معمول است؟

نام روش آمد، با استفاده از قیاس از حباب های هوا در آب است. این یک استعاره است. فقط به عنوان حباب های هوا کمی افزایش یابد به سمت بالا - به دلیل تراکم خود را بیشتر از یک سیال (در این مورد - آب) است، و هر عنصر آرایه، کوچکتر از آن ارزش، راه تدریجی به بالا از اعداد لیست است.

شرح الگوریتم

مرتب سازی حبابی است به شرح زیر انجام:

• در اولین گذر: عناصر از اعداد آرایه توسط دو جفت گرفته شده و همچنین مقایسه شده است. اگر برخی از عناصر از دو مرد تیم ارزش برای اولین بار بیشتر از دومی است، این برنامه آنها را می سازد مکان مبادله؛
• در نتیجه، بیشترین تعداد نتواند پایان آرایه. در حالی که تمام عناصر دیگر باقی می مانند، به شیوه ای پر هرج و مرج، و نیاز به بیشتر مرتب سازی؛
• و در نتیجه نیاز یک پاس دوم: آن است که در قیاس با ساخته شده قبلی (در حال حاضر شرح) است که تعدادی از مقایسه و - منهای یک.
• در تعداد عبور سه مقایسه، یکی کمتر از دوم، و این دو، از اول است. و به همین ترتیب.
• خلاصه که هر یک از گذشت است (تمام مقادیر موجود در آرایه، تعداد خاص) منهای مقایسه (تعداد عبور).

الگوریتم حتی کوتاه تر از یک برنامه می تواند به عنوان نوشته شده است:

• آرایه ای از اعداد به عنوان طولانی به عنوان بررسی هر دو عدد یافت می شوند، دوم از آنها موظف است به بیشتر از اولین.
• اشتباه در رابطه با هر یک از عناصر دیگر از سواپ نرم افزار آرایه قرار گرفته است.

شبه در الگوریتم بر اساس

ساده ترین پیاده سازی شده است به صورت زیر انجام:

روش Sortirovka_Puzirkom؛

شروع

چرخه برای j از nachalnii_index به konechii_index؛

چرخه برای من از nachalnii_index به konechii_index-1؛

اگر massiv [من]> massiv [من + 1] (اولین عنصر بیشتر از یک ثانیه)، و سپس:

(تغییر مکان ارزش).

پایان

البته این سادگی تنها تشدید این وضعیت: الگوریتم ساده، بیشتر از آن آشکار تمام معایب. نسبت سرمایه گذاری از زمان حتی برای یک آرایه کوچک بیش از حد بزرگ است (در اینجا می آید در نسبیت: مقدار زمان برای شخص غیر روحانی ممکن است به نظر می رسد کوچک، اما در واقع یک برنامه نویس هر فقره دوم و یا حتی میلی ثانیه).

آن را در زمان اجرای بهتر است. به عنوان مثال، با توجه به تبادل ارزش ها در مکان های آرایه:

روش Sortirovka_Puzirkom؛

شروع

sortirovka = درست؛

چرخه تا زمانی که sortirovka = درست؛

sortirovka = کاذب؛

چرخه برای من از nachalnii_index به konechii_index-1؛

اگر massiv [من]> massiv [من + 1] (اولین عنصر بیشتر از یک ثانیه)، و سپس:

(تغییر عناصر مکان)؛

sortirovka = درست؛ (شناسایی که مبادله شده است).

پایان.

محدودیت ها

نقطه ضعف اصلی - مدت زمان این فرآیند است. چقدر زمان انجام می شود الگوریتم مرتب سازی حبابی؟

زمان سرب است از تعداد اعداد مربع در آرایه محاسبه - نتیجه نهایی از آن متناسب است.

اگر بدترین حالت آرایه به عنوان چند بار گذشت که آن را تا عناصر منهای یک ارزش است. این اتفاق می افتد چرا که در پایان تنها یک عنصر وجود دارد، که چیزی برای مقایسه، و آخرین پاس از طریق آرایه عمل بی فایده می شود.

علاوه بر این، روش موثر مرتب سازی تبادل ساده، آن را به عنوان نامیده می شود، تنها برای آرایه از اندازه کوچک است. مقادیر زیادی از داده را با کمک فرآیند کار نخواهد کرد: نتیجه این خواهد بود یا خطا یا شکست برنامه است.

وقار

مرتب سازی حبابی است بسیار آسان به درک. برنامه آموزشی دانشگاه فنی در این مطالعه از عناصر ترتیب آرایه خود را منتقل می کند در وهله اول. این روش ساده است که برای اجرای هر دو زبان دلفی برنامه نویسی (L (دلفی)، و 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

8 22 4 1 7 74 44 37

8 22 4 1 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

4 7 8 1 22 37 74 44

مرحله 1 4 7 4 8 22 37 44 74

4 7 8 1 22 37 44 74

4 7 8 1 22 37 44 74

4 7 8 1 22 37 44 74

مرحله 5 1 4 7 8 22 37 44 74

4 7 8 1 22 37 44 74

4 7 8 1 22 37 44 74

مرحله 1 4 7 6 8 22 37 44 74

4 7 8 1 22 37 44 74

مرحله 1 4 7 7 8 22 37 44 74

حباب مثال sort به زبان پاسکال

به عنوان مثال:

kol_mas توایع = 10؛

ور massiv: آرایه [1..kol_mas] از عدد صحیح است؛

A، B، K: عدد صحیح؛

آغاز

writeln ( 'ورودی، kol_mas، از عناصر آرایه')؛

برای: = 1 تا kol_mas انجام readln (massiv [یک ])؛

برای: = 1 تا kol_mas-1 شروع

برای b: = A + 1 به kol_mas شروع

اگر massiv [A]> massiv [ B] پس از آن شروع

K: = massiv [A]؛ massiv [A]: = massiv [ B]؛ massiv [B]: = K؛

پایان؛

پایان؛

پایان؛

writeln ( 'پس از مرتب کردن')؛

برای: = 1 تا kol_mas انجام writeln (massiv [یک ])؛

پایان.

حباب مثال مرتب سازی در زبان C (C)

به عنوان مثال:

کد: #include

کد: #include

اعضای هیات تحریریه اصلی (INT تعداد آنها، کاراکتر * ی argv [])

{

اعضای هیات massiv [8] = {36، 697، 73، 82، 68، 12، 183، 88}، من، FF؛

برای (؛؛) {

FF = 0؛

برای (من = 7؛ من> 0؛ من -) {

اگر (massiv [من] [I- 1]) {

مبادله (massiv [i] یا massiv [I- 1])؛

FF ++؛

}

}

اگر (FF == 0) شکستن؛

}

getch ()؛ // تاخیر نمایش

بازگشت 0؛

}.