همه به خوبی می‌دانند که از کلاس انواع مبادله، بیشتر از همه روش سریعبه اصطلاح است مرتب سازی سریع. پایان نامه هایی در مورد آن نوشته شده است، مقالات زیادی در مورد هابره به آن اختصاص داده شده است، الگوریتم های ترکیبی پیچیده بر اساس آن اختراع شده اند. اما امروز ما در مورد آن صحبت نمی کنیم مرتب سازی سریع، اما در مورد روش تبادل دیگری - قدیمی خوب مرتب سازی حبابیو بهبودها، اصلاحات، جهش ها و تغییرات آن.
خروجی عملی این روش ها چندان داغ نیست و بسیاری از habrausers در کلاس اول همه اینها را پشت سر گذاشتند. لذا مخاطب این مقاله کسانی است که به تازگی به نظریه الگوریتم ها علاقه مند شده اند و اولین گام های خود را در این راستا برمی دارند.
تصویر: حباب
امروز در مورد ساده ترین آنها صحبت خواهیم کرد مرتب سازی مبادلات.
اگر کسی علاقه مند است، می گویم که کلاس های دیگری نیز وجود دارد - مرتب سازی انتخابی, مرتب سازی درج, مرتب سازی ادغام, توزیع مرتب سازی, انواع هیبریدیو انواع موازی. به هر حال، وجود دارد دسته بندی های باطنی. اینها الگوریتم های مختلف جعلی، اساسا غیرقابل تحقق، کمیک و دیگر شبه الگوریتم ها هستند که من به نوعی در مورد آنها چند مقاله در هاب طنز فناوری اطلاعات خواهم نوشت.
اما این ربطی به سخنرانی امروز ندارد، ما اکنون فقط به انواع مبادله ساده علاقه مندیم. همچنین خود چندین نوع مبادله وجود دارد (من بیش از ده ها را می شناسم) ، بنابراین ما به اصطلاح را در نظر خواهیم گرفت مرتب سازی حبابیو برخی دیگر که ارتباط نزدیکی با آن دارند.
من از قبل به شما هشدار می دهم که تقریباً همه روش های فوق بسیار کند هستند و هیچ تحلیل عمیقی از پیچیدگی زمانی آنها وجود نخواهد داشت. بعضی ها سریع تر، بعضی ها کندتر هستند، اما، به طور کلی، می توان گفت که به طور متوسط O(n 2). همچنین، دلیلی برای شلوغ کردن مقاله با پیاده سازی در هر زبان برنامه نویسی نمی بینم. علاقه مندان می توانند به راحتی نمونه های کد را در روزتا، ویکی پدیا یا جای دیگری بیابند.
اما برگردیم به مرتب سازی مبادلات. ترتیب در نتیجه تکرار پی در پی مکرر آرایه و مقایسه جفت عناصر با یکدیگر رخ می دهد. اگر عناصر مقایسه شده نسبت به یکدیگر مرتب نشده باشند، آنها را تعویض می کنیم. تنها سوال این است که دقیقا چگونه می توان آرایه را دور زد و بر چه اساسی جفت ها را برای مقایسه انتخاب کرد.
اجازه دهید نه با مرتب سازی حباب مرجع، بلکه با الگوریتمی به نام ... شروع کنیم.
مرتب سازی احمقانه
مرتب سازی واقعا احمقانه است. ما از طریق آرایه از چپ به راست نگاه می کنیم و همسایگان را در طول مسیر مقایسه می کنیم. اگر با یک جفت عنصر مرتب‌نشده متقابل مواجه شدیم، آنها را عوض می‌کنیم و به نقطه اول یعنی همان ابتدا برمی‌گردیم. دوباره آرایه را مرور می کنیم و بررسی می کنیم، اگر دوباره جفت "اشتباه" عناصر همسایه را ملاقات کنیم، مکان ها را عوض می کنیم و همه چیز را از نو شروع می کنیم. ادامه می دهیم تا آرایه به آرامی مرتب شود."بنابراین هر احمقی می داند چگونه مرتب کند" - شما می گویید و کاملاً درست خواهید بود. به همین دلیل است که مرتب سازی "احمقانه" نامیده می شود. در این سخنرانی، ما به طور مداوم بهبود و اصلاح خواهیم کرد این روش. اکنون او پیچیدگی زمانی دارد O(n 3، پس از انجام یک اصلاح، قبلاً به آن خواهیم پرداخت O(n 2) سپس کمی بیشتر سرعت دهید، سپس کمی بیشتر، و در پایان به دست می آوریم O(nورود به سیستم n) - و اصلاً «مرتب‌سازی سریع» نخواهد بود!
بیایید یک پیشرفت واحد در مرتب سازی احمقانه ایجاد کنیم. با یافتن دو عنصر مرتب نشده مجاور در طول عبور و تعویض آنها، به ابتدای آرایه برنمی گردیم، بلکه با آرامش پیمایش آن را تا آخر ادامه می دهیم.
در این مورد، ما چیزی بیش از معروف ...
مرتب سازی حبابی
یا مرتب سازی بر اساس مبادلات ساده. کلاسیک جاودانه این ژانر. اصل عمل ساده است: ما آرایه را از ابتدا تا انتها دور می زنیم و همزمان مرتب نشده را عوض می کنیم. عناصر همسایه. در نتیجه اولین گذر، عنصر حداکثر تا آخرین مکان ظاهر می شود. اکنون دوباره قسمت مرتب نشده آرایه (از عنصر اول تا عنصر ماقبل آخر) را دور می زنیم و همسایه های مرتب نشده را در طول مسیر تغییر می دهیم. دومین عنصر بزرگ در مکان ماقبل آخر خواهد بود. با همین روحیه ادامه می دهیم، بخش مرتب نشده آرایه رو به کاهش را دور می زنیم و ماکزیمم های یافت شده را تا انتها فشار می دهیم.اگر نه تنها اوج ها را به انتها فشار دهیم، بلکه پایین ترین ها را نیز به آغاز حرکت دهیم، آنگاه به ...
مرتب سازی تکان دهنده
او است مرتب سازی درهم، او است دسته بندی کوکتل. این روند مانند یک "حباب" شروع می شود: ما حداکثر را به حیاط خلوت فشار می دهیم. پس از آن، ما در اطراف 180 0 می چرخیم و در جهت مخالف می رویم، در حالی که از قبل به ابتدا نه حداکثر، بلکه حداقل می چرخیم. پس از مرتب کردن اولین و آخرین عناصر در آرایه، دوباره یک سالتو انجام می دهیم. پس از چندین بار دور زدن و عقب نشینی، در پایان کار را به پایان می رسانیم و در وسط لیست قرار می گیریم.مرتب‌سازی تکان‌دهنده کمی سریعتر از مرتب‌سازی حبابی کار می‌کند، زیرا هر دو بالا و پایین به طور متناوب از طریق آرایه در جهت‌های درست حرکت می‌کنند. همانطور که می گویند، پیشرفت ها مشهود است.
همانطور که می بینید، اگر خلاقانه به فرآیند تکرار نزدیک شوید، فشار دادن عناصر سنگین (سبک) به انتهای آرایه سریعتر است. بنابراین، صنعتگران برای دور زدن لیست، "نقشه راه" غیر استاندارد دیگری را پیشنهاد کردند.
مرتب سازی زوج-فرد
این بار ما در اطراف آرایه به جلو و عقب نمی چرخیم، بلکه دوباره به ایده دور زدن سیستماتیک از چپ به راست باز می گردیم، بلکه فقط یک قدم گسترده تر برداریم. در اولین پاس، عناصر دارای کلید فرد با همسایگان بر اساس مکان های زوج مقایسه می شوند (اول با 2، سپس 3 با 4، 5 با 6، و غیره مقایسه می شود). سپس برعکس - عناصر "زوج" با "فرد" مقایسه / تغییر می کنند. سپس دوباره «فرد- زوج»، سپس دوباره «زوج-فرد». این فرآیند زمانی متوقف می شود که، پس از دو عبور متوالی از آرایه («فرد- زوج» و «زوج-فرد»)، هیچ تبادلی رخ نداده باشد. بنابراین، مرتب شده است.در "حباب" معمول در طول هر پاس، ما به طور سیستماتیک حداکثر فعلی را به انتهای آرایه فشار می دهیم. اگر از امتداد شاخص‌های زوج و فرد بگذریم، به یکباره همه عناصر کم و بیش بزرگ آرایه به طور همزمان با یک موقعیت در یک اجرا به سمت راست هل داده می‌شوند. اینجوری سریعتر میشه
بیایید آخرین مورد را تحلیل کنیم نوسازی* برای مرتب سازی لامپ** - مرتب سازی بر اساس شانه*** این روش خیلی سریع مرتب می شود، O(n 2) بدترین پیچیدگی آن است. به طور متوسط در طول زمان، ما داریم O(nورود به سیستم n) و حتی بهترین ها، آن را باور نکنید O(n). یعنی یک رقیب بسیار شایسته برای هر "مرتب سازی سریع" و این، بدون استفاده از بازگشت، توجه داشته باشید. با این حال، من قول دادم که امروز به سرعت های کروز نخواهیم پرداخت، بنابراین سکوت می کنم و مستقیماً به الگوریتم می روم.
همش تقصیر لاک پشت هاست
کمی پیشینه در سال 1980، Włodzimierz Dobosiewicz توضیح داد که چرا مرتب‌سازی حبابی و مشتقات آن بسیار کند است. همه چیز در مورد لاک پشت ها است. "لاک پشت ها" اقلام کوچکی هستند که در انتهای لیست قرار دارند. همانطور که ممکن است متوجه شده باشید، انواع حباب بر روی "خرگوش" متمرکز شده است (با "خرگوش" بابوشکین اشتباه نشود) - عناصر بزرگ در ابتدای لیست. آنها خیلی سریع به سمت خط پایان حرکت می کنند. اما خزندگان کند با اکراه تا شروع می خزند. شما می توانید "تورتیلو" را با استفاده از آن سفارشی کنید شانه ها.تصویر: لاک پشت گناهکار
مرتب سازی شانه
در "حباب"، "تکان دهنده" و "زوج-فرد"، هنگام تکرار روی یک آرایه، عناصر مجاور با هم مقایسه می شوند. ایده اصلی "شانه" این است که در ابتدا مقدار کافی مصرف شود مسافت طولانیبین عناصر مقایسه شده و با مرتب شدن آرایه، این فاصله را به حداقل کاهش دهید. بنابراین، ما، همانطور که بود، آرایه را شانه می کنیم، و به تدریج آن را به رشته های دقیق تر و دقیق تر تبدیل می کنیم.بهتر است شکاف اولیه بین عناصر مقایسه شده را نه به هر حال، بلکه با در نظر گرفتن مقدار خاصی به نام در نظر بگیرید عامل کاهندهکه مقدار بهینه آن تقریباً 1.247 است. اول، فاصله بین عناصر برابر است با اندازه آرایه تقسیم بر عامل کاهش(نتیجه به طور طبیعی به نزدیکترین عدد صحیح گرد می شود). سپس پس از گذشتن از آرایه با این مرحله، دوباره گام را بر تقسیم می کنیم عامل کاهشو دوباره لیست را مرور کنید. این تا زمانی ادامه می یابد که اختلاف شاخص به یک برسد. در این مورد، آرایه با یک حباب معمولی دوباره مرتب می شود.
مقدار بهینه به صورت تجربی و تئوری تعیین شده است عامل کاهش:
زمانی که این روش اختراع شد، افراد کمی در اواخر دهه 70 و 80 به آن توجه کردند. یک دهه بعد، زمانی که برنامه نویسی دیگر مورد توجه دانشمندان و مهندسان IBM نبود، بلکه به سرعت در حال افزایش شخصیت بود، این روش در سال 1991 توسط استیون لیسی و ریچارد باکس دوباره کشف، تحقیق و محبوبیت یافت.
این در واقع تمام چیزی است که می خواستم در مورد مرتب سازی حبابی و موارد مشابه به شما بگویم.
- یادداشت
* کوتاه شده ( اوکراینی) - بهبود
** مرتب سازی با لامپ ( اوکراینی) – مرتب سازی حبابی
*** مرتب سازی بر اساس شانه ( اوکراینی) – مرتب سازی شانه
تخمین زده شده است که یک چهارم زمانی که رایانه های متمرکز صرف مرتب سازی داده ها می کنند. این به این دلیل است که یافتن یک مقدار در آرایه ای که از قبل مرتب شده است بسیار آسان تر است. در غیر این صورت، جستجو کمی شبیه به دنبال سوزن در انبار کاه است.
برنامه نویسانی هستند که تمام وقت کاری خود را صرف مطالعه و اجرای الگوریتم های مرتب سازی می کنند. این به این دلیل است که اکثریت قریب به اتفاق نرم افزارها در تجارت شامل مدیریت پایگاه داده هستند. مردم همیشه اطلاعات را در پایگاه های داده جستجو می کنند. این بدان معناست که الگوریتم های جستجو تقاضای بالایی دارند.
اما یک "اما" وجود دارد. الگوریتم های جستجوبا پایگاه های داده ای که قبلا مرتب شده اند بسیار سریع تر کار کنید. در این حالت فقط به جستجوی خطی نیاز است.
در حالی که کامپیوترها در برخی مقاطع زمانی بدون کاربر هستند، الگوریتم های مرتب سازی همچنان با پایگاه های داده کار می کنند. یک بار دیگر، جستجوگران وارد می شوند و پایگاه داده قبلاً بر اساس یک هدف جستجو مرتب شده است.
در این مقاله نمونه هایی از پیاده سازی الگوریتم های مرتب سازی استاندارد ارائه شده است.
مرتب سازی انتخابی
برای مرتب کردن یک آرایه به ترتیب صعودی، در هر تکرار، عنصر با را پیدا کنید بالاترین ارزش. با آن، باید آخرین عنصر را تعویض کنید. عنصر بعدی با بالاترین مقدار به عنصر ماقبل آخر تبدیل می شود. این باید تا زمانی اتفاق بیفتد که عناصری که در اولین مکان های آرایه قرار دارند به ترتیب مناسب باشند.
کد ++C
void SortAlgo::selectionSort(int data, int lenD) (int j = 0; int tmp = 0; for (int i=0; i
مرتب سازی حبابی
مرتب‌سازی حبابی عناصر مجاور را با هم مقایسه می‌کند و اگر عنصر بعدی کوچکتر از عنصر قبلی باشد، مبادله می‌کند. نیاز به گذرهای متعدد از طریق داده ها دارد. در طی اولین پاس، دو عنصر اول آرایه با هم مطابقت دارند. اگر آنها نامرتب باشند، با هم عوض می شوند و سپس عناصر جفت بعدی با هم مقایسه می شوند. با همین شرایط، آنها نیز جای خود را تغییر می دهند. بنابراین مرتب سازی در هر چرخه تا رسیدن به انتهای آرایه انجام می شود.
کد ++C
void SortAlgo::bubbleSort(int data, int lenD) ( int tmp = 0; for (int i = 0;i مرتب سازی درج یک آرایه را به دو منطقه تقسیم می کند: مرتب و نامرتب. در ابتدا، کل آرایه یک منطقه نامرتب است. در پاس اول، اولین عنصر از ناحیه نامرتب حذف شده و در موقعیت صحیح در ناحیه مرتب شده قرار می گیرد. در هر پاس، اندازه منطقه سفارش داده شده 1 افزایش می یابد و اندازه منطقه نامرتب 1 کاهش می یابد. حلقه اصلی در محدوده 1 تا N-1 اجرا می شود. در تکرار j، عنصر [i] در موقعیت صحیح در ناحیه مرتب شده قرار می گیرد. این کار با جابجایی تمام عناصر ناحیه مرتب شده که بزرگتر از [i] یک موقعیت به سمت راست هستند انجام می شود. [i] در فاصله بین عناصری که کمتر از [i] و بزرگتر از [i] هستند درج می شود. کد ++C
void SortAlgo::insertionSort(int data, int lenD) (int key = 0; int i = 0; for (int j = 1; j کد ++C
void SortAlgo::mergeSort(int data, int lenD) ( if (lenD>1)( int middle = lenD/2; int rem = lenD-middle; int * L = new int ; int * R = new int ; for ( int i=0;i Quicksort از الگوریتم تقسیم و غلبه استفاده می کند. با تقسیم آرایه اصلی به دو منطقه شروع می شود. این قسمت ها در سمت چپ و راست عنصر مشخص شده قرار دارند که به آن Pivot می گویند. در پایان فرآیند، یک قسمت حاوی عناصر کوچکتر از پیوت و قسمت دیگر حاوی عناصر بزرگتر از محور خواهد بود. کد ++C
void SortAlgo::quickSort(int * data, int const len) (int const lenD = len؛ int pivot = 0؛ int ind = lenD/2؛ int i,j = 0, k = 0؛ if (lenD>1) (int * L = new int ; int * R = new int ; pivot = data ; for (i=0;i سلام به همه! امروز مرتب سازی را با روش "حباب" تجزیه و تحلیل خواهیم کرد. این الگوریتم اغلب در مدارس و دانشگاه ها تصویب می شود، بنابراین ما از زبان پاسکال استفاده خواهیم کرد. بنابراین، مرتب سازی چیست؟ مرتب سازی عبارت است از ترتیب عناصر از کوچکترین به بزرگترین (مرتب سازی صعودی) یا از بزرگترین به کوچکترین عنصر (مرتب سازی نزولی). آرایه ها معمولا مرتب شده اند. الگوریتم های مرتب سازی مختلفی وجود دارد. برخی در مرتب‌سازی تعداد زیادی اقلام خوب هستند، برخی دیگر در موارد بسیار کمی کارآمدتر هستند. روش حباب ما مشخصه است: الگوریتم:
یک عنصر آرایه را می گیریم، آن را با عنصر بعدی مقایسه می کنیم، اگر عنصر ما بزرگتر از عنصر بعدی باشد، آنها را عوض می کنیم. پس از بررسی کل آرایه، می توانیم مطمئن باشیم که حداکثر عنصر "پاپ" خواهد شد - و آخرین عنصر خواهد بود. بنابراین، ما قبلاً یک عنصر را دقیقاً در جای خود داریم. زیرا ما باید همه آنها را در جای خود قرار دهیم، بنابراین، باید این عمل را تکرار کنیم، هر چند بار که عناصر آرایه منهای 1 داشته باشیم. اگر بقیه در جای خود باشند، آخرین عنصر به طور خودکار ظاهر می شود.
بیایید به آرایه خود برگردیم: 3 1 4 2 حال باقی مانده است که این الگوریتم را در پاسکال برنامه ریزی کنیم. const n = 4; (یک ثابت را شروع می کنیم، طول آرایه خواهد بود) var i, j, k:integer; (دو متغیر برای حلقه تودرتو، یکی برای تعویض عناصر) m:آرایه عدد صحیح; (ایجاد یک آرایه) begin (ما یک آرایه از صفحه کلید درخواست خواهیم کرد:) Writeln("Array Enter:"); برای i:=1 تا n شروع Writeln(i، " عنصر:"); readln(m[i]); پایان؛ (حلقه بیرونی مسئول این واقعیت است که باید حلقه داخلی را به تعداد دفعاتی که عناصر آرایه منهای 1 داشته باشیم تکرار کنیم.) زیرا i:=1 تا n-1 شروع می شود (حلقه داخلی از قبل روی عناصر تکرار می شود و مقایسه می شود. با یکدیگر.) برای j :=1 تا n-i شروع می شود (اگر عنصر بزرگتر از عنصر بعدی است، مبادله کنید.) اگر m[j]>m پس از آن k:=m[j] شروع شود; m[j]:=m; m:=k; پایان؛ پایان؛ پایان؛ (نتیجه چاپ:) برای i:=1 تا n انجام Write(m[i], " "); پایان. هنگام کار با آرایه های داده، برای آنها غیر معمول نیست مرتب سازی به ترتیب صعودی یا نزولی، یعنی. ساده سازی. این بدان معنی است که عناصر یک آرایه باید دقیقاً به ترتیب مرتب شوند. به عنوان مثال، در مورد مرتب سازی به ترتیب صعودی، عنصر قبل باید کمتر از (یا مساوی) عنصر بعدی باشد. روش های مرتب سازی زیادی وجود دارد. برخی از آنها کارآمدتر هستند، برخی دیگر آسان تر قابل درک هستند. به اندازه کافی ساده برای درک مرتب سازی است روش حبابی، که به آن نیز می گویند روش تبادل ساده. چیست و چرا چنین نام عجیبی دارد: "روش حباب"؟ همانطور که می دانید، هوا سبک تر از آب است، بنابراین حباب های هوا شناور هستند. این فقط یک قیاس است. در مرتب‌سازی حبابی صعودی، عناصر سبک‌تر (مقدار پایین‌تر) به تدریج به سمت ابتدای آرایه شناور می‌شوند، در حالی که عناصر سنگین‌تر یکی یکی به پایین (تا انتهای آرایه) فرو می‌روند. برنامه پاسکال: const m = 10 ; var arr: آرایه [ 1 .. m ] از عدد صحیح ; i, j, k: عدد صحیح ; شروع تصادفی سازی؛ نوشتن ( "آرایه منبع:") ؛ برای i : = 1 تا m do start arr[i] : = random(256) ; نوشتن (arr[ i] : 4 ) ; پایان ؛ نوشتن ; نوشتن ; برای i : = 1 تا m- 1 do for j : = 1 تا m- i do if arr[j] > arr[j+ 1 ] سپس k : = arr[j] ; arr[ j] := arr[ j+ 1 ] ; arr[ j+ 1 ] : = k end ; نوشتن ( "آرایه مرتب شده:") ؛ برای i := 1 تا m do write (arr[i] : 4 ) ; نوشتن ; پایان خواندن . بیایید آرایه را از بالا به پایین، از عنصر صفر تا آخرین عنصر مرتب کنیم. ایده روش: مرحله مرتب سازی شامل رفتن از پایین به بالا از طریق آرایه است. در طول مسیر به جفت عناصر مجاور نگاه می شود. اگر عناصر برخی از جفت‌ها در ترتیب اشتباهی باشند، آنها را عوض می‌کنیم. پس از عبور صفر از آرایه، "سبک ترین" عنصر "بالا" است - از این رو قیاس با یک حباب است. پاس بعدی تا عنصر دوم از بالا انجام می شود، بنابراین دومین عنصر بزرگ به موقعیت صحیح بالا می رود ... ما در امتداد قسمت پایینی آرایه که همیشه در حال کاهش است عبور می کنیم تا زمانی که فقط یک عنصر در آن باقی بماند. اینجا جایی است که مرتب سازی به پایان می رسد، زیرا دنباله به ترتیب صعودی مرتب شده است. قالب میانگین تعداد مقایسه‌ها و مبادلات دارای ترتیب درجه دوم رشد است: تتا(n2)، از این رو می‌توان نتیجه گرفت که الگوریتم حباب بسیار کند و ناکارآمد است. ابتدا وضعیتی را در نظر بگیرید که در هیچ یک از پاس ها مبادله ای صورت نگرفته است. چه مفهومی داره؟ این بدان معنی است که همه جفت ها در ترتیب صحیح هستند، بنابراین آرایه از قبل مرتب شده است. و ادامه روند بی معنی است (به خصوص اگر آرایه از همان ابتدا مرتب شده باشد!). بنابراین، اولین بهبود الگوریتم این است که به یاد بیاوریم که آیا تبادلی در یک پاس مشخص انجام شده است یا خیر. اگر نه، الگوریتم خاتمه می یابد. روند بهبود را می توان ادامه داد اگر نه تنها واقعیت خود مبادله، بلکه شاخص آخرین مبادله k را نیز به خاطر بسپاریم. در واقع: همه جفت‌های عناصر همسایه با شاخص‌های کمتر از k در حال حاضر به ترتیب مورد نیاز هستند. پاس‌های بیشتر می‌توانند به جای بالا رفتن به کران بالای از پیش تنظیم شده i، به شاخص k ختم شوند. بهبود کیفی متفاوتی از الگوریتم را می توان از مشاهدات زیر بدست آورد. اگرچه حباب نور از پایین در یک گذر به سمت بالا بالا می رود، حباب های سنگین با حداقل سرعت یک قدم در هر تکرار پایین می آیند. بنابراین آرایه 2 3 4 5 6 1 در 1 پاس مرتب می شود، در حالی که مرتب سازی دنباله 6 1 2 3 4 5 به 5 پاس نیاز دارد. برای جلوگیری از این اثر، می توانید جهت پاس های متوالی را تغییر دهید. الگوریتم حاصل گاهی اوقات به عنوان " تکان دهنده". قالب تغییرات توصیف شده تا چه اندازه بر اثربخشی روش تأثیر گذاشت؟ میانگین تعداد مقایسه ها اگرچه کاهش یافته است، اما O(n2) باقی می ماند، در حالی که تعداد مبادلات اصلاً تغییر نکرده است. میانگین (همچنین بدترین) تعداد عملیات درجه دوم باقی می ماند. بدیهی است که حافظه اضافی مورد نیاز نیست. رفتار روش بهبود یافته (اما نه اولیه) کاملا طبیعی است، یک آرایه تقریبا مرتب شده بسیار سریعتر از یک آرایه تصادفی مرتب می شود. مرتب سازی حبابی پایدار است، اما مرتب سازی شیکر این کیفیت را از دست می دهد. در عمل، روش حباب، حتی با بهبود، متاسفانه بسیار کند است. بنابراین، تقریباً هرگز استفاده نمی شود.مرتب سازی درج
ادغام مرتب سازی
مرتب سازی سریع
طرفداران:
معایب:
فرض کنید یک آرایه داریم: 3 1 4 2
اولین عنصر "3" را می گیریم و آن را با "1" بعدی مقایسه می کنیم. زیرا "3" > "1"، سپس مبادله کنید:
1 3 4 2
حالا «3» و «4» را با هم مقایسه می کنیم، سه تا چهار بیشتر نیست، بنابراین هیچ کاری انجام نمی دهیم. در مرحله بعد، "4" و "2" را با هم مقایسه می کنیم. چهار بیشتر از دو است - بنابراین ما جای خود را عوض می کنیم: 1 3 2 4. چرخه تمام شده است. بنابراین بزرگترین عنصر باید از قبل در جای خود باشد!! می بینیم که این اتفاق افتاده است. هر کجا که "4" (بزرگترین عنصر ما) قرار دارد - پس از حلقه زدن در کل آرایه همچنان آخرین عنصر خواهد بود. قیاس - درست مانند یک حباب هوا که در آب شناور است - بنابراین عنصر ما در یک آرایه شناور است. بنابراین، الگوریتم "مرتب سازی حباب" نامیده می شود. برای قرار دادن عنصر بعدی، لازم است چرخه از نو شروع شود، اما دیگر نمی توان آخرین عنصر را در نظر گرفت، زیرا در جای خود ایستاده است.
ما "1" و "3" را با هم مقایسه می کنیم - هیچ چیز را تغییر نمی دهیم.
"3" و "2" را مقایسه کنید - سه بیشتر از دو است، بنابراین ما مکان را تغییر می دهیم. معلوم می شود: 1 2 3 4. چرخه دوم به پایان رسید. ما قبلاً دو چرخه را انجام داده ایم - به این معنی که می توانیم با اطمینان بگوییم که دو عنصر آخر را قبلا مرتب کرده ایم. برای ما باقی می ماند که عنصر سوم را مرتب کنیم و عنصر چهارم به طور خودکار در جای مناسب قرار می گیرد. یک بار دیگر، عنصر اول و عنصر دوم را با هم مقایسه می کنیم - می بینیم که ما قبلاً همه چیز را در جای خود داریم، به این معنی که آرایه را می توان به ترتیب صعودی عناصر مرتب شده در نظر گرفت.
در اینجا نتیجه است: 
و اینم فیلم آموزشی
راه حل
الگوریتم و ویژگی های این نوع به شرح زیر است:
با این حال، یک مزیت بزرگ دارد: ساده است و به هر طریقی قابل بهبود است. حالا قراره چیکار کنیم