Bubble сортиране на едномерен масив: алгоритъм, програмен код на език C

При работа с информацията най-изгодните начини за съхраняването й са структури и масиви. Последният може да съдържа данни от един тип, които са удобни за използване в програмата. Те често се използват в работата на онлайн магазини и в развитието на игри. Поради това данните, съдържащи се в тях, се сортират и сменят многократно и се извършват логически или математически операции. Един от начините да въведете ред в масива е сортирането на балончетата. Тази публикация ще изследва своя С код и логиката на пермутациите.

Сортиране на алгоритъма

Техническите трудности за програмиста не са сортиране на балона на едноизмерния масив, въпреки че се използва рядко поради ниската си ефективност. Тя по-често се разглежда на етапа на обучение като най-проста. Това обаче далеч не е най-ефективното. Неговият алгоритъм се състои от алтернативно сравняване на цифрите и взаимно заместване на клетките, ако условието е изпълнено.

Стъпка по стъпка описание на сортирането

При първото повторение постепенно се сравняват два съседни числа. Ако левият е по-голям, тогава той се пренаписва на места с правилния. Минуси 8 и 0 условията не отговарят. Ето защо те не се променят на места. Нула и 5 също не се поберат. 5 и 3 са подходящи. Въпреки това, при тази итерация рамката за четене не пада върху първите пет, но се премества надясно, тъй като 5, преди това да се сравнява с нула. Това означава, че следващата двойка - 3 и 9 променя местата, след което на четеца се предлага да прегледа всички замествания независимо без авторски коментари и да изучи алгоритъма за сортиране на балончета.

В резултат на всички повторения, масивът постепенно се сортира и това е в основата си: големите положителни числа се движат бързо надясно, а по-малките и отрицателните бавно се пренареждат наляво. Изглежда, че балонът на газ в течност бързо се издига. Поради тази аналогия алгоритъмът се нарича сортиране на балончетата.

Оценка на изчислителната сложност

Идеалният алгоритъм за сортиране трябва да бъде възможно най-бърз. В същото време тя трябва да заема малко количество ресурси на процесора и паметта. И такъв процес като сортиране на балон на масив не може да бъде най-енергийно ефективен и печеливш. Поради широко приложение, той не откри. Ако в момента има по-малко проблеми с паметта, тогава ресурсите на процесора трябва да се притесняват. Тъй като цифровите масиви могат да бъдат не само големи, но огромни, тогава потреблението на компютърни ресурси ще бъде непредвидимо.

Ако сортирането на балона по принцип бързо се справя с установяването на ред в сравнително малък масив, то в по-голямата си част може да има недостатъци, дължащи се на прекалено изразходване на ресурси. Това означава, че универсалната собственост, присъща на алгоритъма, ще бъде нарушена. и балон сортиране има N-квадратен сложност и е много далеч от логаритъма на N сложност. Освен това рискът от повреда при обработката на голям масив увеличава шансовете за загуба на данни поради презаписване на клетки. Много по-изгодно в това отношение ще бъде сортирането на вмъкването или алгоритъма на Shell.

Код на софтуера

Компютърният код за езика C, който се намира по-долу в графичното приложение, ви позволява да извършвате сортиране на балони. Тя се представя като отделна функция от тип void. Той не връща никакви стойности, но с помощта на указатели суаповете на елементите зависят от условията за сортиране. В този случай кодът решава проблема със сортирането на балончетата на масив от числа в нарастващ ред.

За да изпълни тази функция, потребителят трябва да създаде масив, който трябва да бъде попълнен с необходимите стойности. Това може да се направи ръчно, като се зададе размерът и броят на елементите в началото на програмата. След това можете да запълнете масива с постоянни стойности. Вторият вариант е да се създаде универсална програма, като се декларира голям едномерен масив от 100 елемента.

Деклариране и инициализиране на масив

Чрез задаване на целочислена променлива и задаване на стойност, четена от клавиатурата, можете да ограничите броя на клетките, които ще бъдат запълнени. Можете също така да внедрите функцията за въвеждане на елементи от масив от потребителя от клавиатурата, като използвате функцията scanf ("% d", " стойност). В този пример "% d" е модифициращ низ, който казва на компилатора, че след сканирането ще бъде получена стойност на цялото число. Променливата стойност ще съхранява стойност, която е размерът на едномерен цялостен масив.

За да използвате алгоритъма за сортиране, трябва да предадете името на масива и неговия размер на функцията. В ситуацията, представена в графичното приложение, повикването към функцията за сортиране ще изглежда така: BubleSort (dataArray, sizeDataArray). Разбира се, в края на реда след функцията трябва да поставите точка и запетая вместо период, както се изисква от правилата за синтактичност на програмата. Така че, dataArray е името на масива, който искате да сортирате, а sizeDataArray е неговият размер.

Предаването на тези параметри на функцията BubleSort () ще доведе до извършването на операциите с sizeDataArray, вместо да се използва sizeArray, както е показано на фигурата, в реална програма. Това също означава, че функцията BubleSort () ще използва цяло число dataArray. По същия начин се извикват функцията printArrayFunction () и ArrayIntegerInputFunction (). Първият е отговорен за печата, т.е. за изход към конзолата на елементите. И втората е необходима, за да се запълни с елементи, въведени от потребителя от клавиатурата.

Този стил на програмиране, когато изолираните операции се предават под формата на функции, значително увеличава четивността на кода и ускорява нейното развитие. При такава програма масивът се попълва отделно от клавиатурата, отпечатан и самият балон се сортира. Последният може да се използва за организиране на данните или като второстепенна функция, предназначена да намери минималния и максимумния масив.

Сортиране по вмъкване

При сортиране чрез вмъкване се приема, че всеки елемент се сравнява на свой ред и се изгражда верига от елементи, които вече са сортирани според състоянието. В резултат на това, резултатът от всяко следващо сравнение е търсенето на клетка, в която може да се постави нова стойност. Но вмъкването на всеки от тях се извършва в вече сортираната част на масива.

Такава обработка е по-бърза и има по-малко изчислителна сложност. С кодът е представен в графичното приложение.

Той се представя и като функция, в която името на масива, което ще бъде подредено, и размерът на масива се предават като аргументи. Тук можете да видите колко бавно е сортирането на балона. Вмъква подобна работа е много по-бързо и има компактен код.