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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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