Мени

Мехурићи сортирани на Ц ++ са примерима

bubble sort c with examples

Испробајте Наш Инструмент За Елиминисање Проблема

Техника сортирања мехурића у Ц ++.

Сортирање мехурића је најједноставнија од техника сортирања.

У техници разврставања облачића, сваки од елемената на листи се упоређује са суседним елементом. Дакле, ако на листи А има н елемената, онда се А (0) упоређује са А (1), А (1) се упоређује са А (2) и тако даље.

Након упоређивања да ли је први елемент већи од другог, два елемента се тада замењују.

=> Посетите овде за комплетан курс за стручњаке на Ц ++.

БУББЛЕ СОРТ

Шта ћете научити:

која је фаза имплементације у сдлц

Техника сортирања мехурића

Техником сортирања мехурића сортирање се врши у пролазима или итерацијама. Тако се на крају сваке итерације најтежи елемент поставља на одговарајуће место на листи. Другим речима, највећи елемент на листи се подиже.

У наставку смо дали општи алгоритам технике сортирања мехурића.

Општи алгоритам

Корак 1 : За и = 0 до Н-1 поновите 2. корак
Корак 2 : За Ј = и + 1 до Н - понављам
3. корак : ако је А (Ј)> А (и)
Замените А (Ј) и А (и)
(Крај унутрашње фор петље)
(Енд иф Оутер фор лооп)
4. корак : Излаз

Ево псеудо-кода за алгоритам сортирања облачића, где прелазимо листу користећи две итеративне петље.

У првој петљи почињемо од 0тхелемент и у следећој петљи почињемо од суседног елемента. У телу унутрашње петље упоређујемо сваки суседни елемент и замењујемо их ако нису у реду. На крају сваке итерације спољне петље, најтежи елемент на крају се облачи.

Псеудоцоде

Procedure bubble_sort (array , N) array – list of items to be sorted N – size of array begin swapped = false repeat for I = 1 to N-1 if array(i-1) > array(i) then swap array(i-1) and array(i) swapped = true end if end for until not swapped end procedure

Горе дато је псеудо-код за технику сортирања мехурића. Хајде да сада илуструјемо ову технику користећи детаљну илустрацију.

Илустрација

Узимамо низ величине 5 и илуструјемо алгоритам сортирања мехурића.

Илустрација сортирања мехурића - пролаз 1

Илустрација сортирања мехурића - пролаз 2

Илустрација мехурића - пролаз 3

Низ је у потпуности сортиран.

Горња илустрација може се резимирати у табеларном облику као што је приказано доле:

ПассНесортирана листапоређењеСортирана листа
{5,0,10,12,15}{10.12}{5,0,10,12,15}
1{10,5,15,0,12}{10.5}{5,10,15,0,12}
{5,10,15,0,12}{10.15}{5,10,15,0,12}
{5,10,15,0,12}{15.0}{5,10,0,15,12}
{5,10,0,15,12}{15.12}{5,10,0,12,15}
два{5,10,0,12,15}{5,10}{5,10,0,12,15}
{5,10,0,12,15}{10.0}{5,0,10,12,15}
3{5,0,10,12,15}{5,0}{0,5,10,12,15}
{5,0,10,12,15}{5,10}{5,0,10,12,15}
{5,0,10,12,15}СОРТЕД

Као што је приказано на илустрацији, при сваком пролазу, највећи елемент се облачи до последњег, сортирајући тако листу са сваким пролазом. Као што је поменуто у уводу, сваки елемент се упоређује са суседним елементом и замењује један с другим ако нису у реду.

Дакле, као што је приказано на горњој илустрацији, на крају првог проласка, ако се низ жели сортирати у растућем редоследу, највећи елемент се ставља на крај листе. За други пролаз, други највећи елемент налази се на другом последњем месту на листи и тако даље.

Када дођемо до пролаза Н-1 (где је Н укупан број елемената на листи), имаћемо сортирану целу листу.

пл / скл интервју питања и одговори

Техника сортирања облачића може се применити на било ком програмском језику. Имплементирали смо алгоритам сортирања облачића користећи Ц ++ и Јава језик доле.

Пример Ц ++

Погледајмо пример програмирања за демонстрацију врсте мехурића.

#include using namespace std; int main () { int i, j,temp,pass=0; int a(10) = {10,2,0,14,43,25,18,1,5,45}; cout <<'Input list ... '; for(i = 0; i<10; i++) { cout <

Излаз:

Листа уноса…

10 2 0 14 43 25 18 1 5 45

Сортирана листа елемената…

0 1 2 5 10 14 18 25 43 45

Број пролаза за сортирање листе: 10

Пример Јаве

class Main { public static void main(String() args) { int pass = 0; int() a = {10,-2,0,14,43,25,18,1,5,45}; System.out.println('Input List...'); for(int i=0;i<10;i++) { System.out.print(a(i) + ' '); } for(int i=0;i<10;i++) { for (int j=0;j<10;j++) { if(a(i)

Излаз:

буббле_сорт Јава Оутпут

У оба програма користили смо низ од 10 елемената и сортирали смо га техником сортирања облачића. У оба програма користили смо две фор петље за итерацију кроз суседне елементе низа.

На крају сваког пролаза (спољна петља), највећи елемент у низу се облачи до краја низа. Такође рачунамо број пролаза који су потребни за сортирање читавог низа.

Анализа сложености алгоритма сортирања мехурића

На основу псеудо кода и илустрације коју смо видели горе, у мехурићу сортирамо Н-1 поређење у првом пролазу, Н-2 поређење у другом пролазу и тако даље.

Отуда је укупан број поређења у мехурићастој сорти:

И = (н-1) + (н-2) + (н-3) + ... + 3 + 2 + 1

= Н (Н-1) / 2

= О (ндва) => Временска сложеност технике сортирања мехурића

Стога су у наставку дате разне сложености технике сортирања мехурића:

Најгора временска сложеностО (н 2)
Најбоља временска сложеностНа)
Просечна временска сложеностО (н 2)
Сложеност простораО (1)

Техника сортирања облачића захтева само један додатни простор меморије за променљиву привремена да би олакшала замену. Отуда је сложеност простора за алгоритам сортирања мехурића О (1).

Имајте на уму да ће најбоља временска сложеност за технику сортирања облачића бити када је листа већ сортирана и то ће бити О (н).

Закључак

Главна предност сортирања облачића је једноставност алгоритма. У разврставању облачића, при сваком пролазу, највећи елемент се облачи до краја листе ако је низ сортиран у растућем редоследу.

Слично томе, да би се листа сортирала у опадајућем редоследу, најмањи елемент ће бити на свом месту на крају сваког проласка.

листа веза у ц ++

Будући да је сортирање мехурића најједноставније и најједноставније за примену, сортирање мехурића обично се користи за представљање сортирања публици. Друго, сортирање мехурића такође се користи у апликацијама попут рачунарске графике при чему попуњавање ивица полигона итд. Захтева сортирање облачића за сортирање врхова који облажу полигоне.

У нашем предстојећем упутству детаљно ћемо научити о Сортирању избора.

=> Посетите овде да бисте научили Ц ++ из огреботина.

Препоручено читање

^