bubble sort c with examples
Техника за сортиране на балончета в C ++.
Bubble Sort е най-простата от техниките за сортиране.
В техниката на сортиране на балончета всеки от елементите в списъка се сравнява със съседния му елемент. По този начин, ако в списък A има n елемента, тогава A [0] се сравнява с A [1], A [1] се сравнява с A [2] и т.н.
След сравнение, ако първият елемент е по-голям от втория, двата елемента се разменят.
=> Посетете тук за пълния курс на C ++ от експерти.
Какво ще научите:
къде е ключът за мрежова защита на рутера
- Техника за сортиране на балончета
- Илюстрация
- Пример за C ++
- Пример за Java
- Анализ на сложността на алгоритъма за сортиране на балончета
- Заключение
- Препоръчително четене
Техника за сортиране на балончета
Използвайки техниката за сортиране на балончета, сортирането се извършва в проходи или итерация. Така в края на всяка итерация най-тежкият елемент се поставя на правилното му място в списъка. С други думи, най-големият елемент в списъка се издига нагоре.
По-долу сме дали общ алгоритъм на техниката за сортиране на балончета.
Общ алгоритъм
Етап 1 : За i = 0 до N-1 повторете стъпка 2
Стъпка 2 : За J = i + 1 до N - повтарям
Стъпка 3 : ако A [J]> A [i]
Разменете A [J] и A [i]
[Край на Inner for loop]
[End if Outer for loop]
Стъпка 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 и илюстрираме алгоритъма за сортиране на балончета.
Масивът е изцяло сортиран.
Горната илюстрация може да бъде обобщена в таблична форма, както е показано по-долу:
| Подайте | Несортиран списък | сравнение | Сортиран списък |
|---|---|---|---|
| {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} | СОРТИРАН |
Както е показано на илюстрацията, при всяко преминаване най-големият елемент се мехурче до последния, като по този начин сортира списъка с всеки проход. Както бе споменато във въведението, всеки елемент се сравнява със съседния му елемент и се сменя помежду си, ако не са в ред.
Така, както е показано на илюстрацията по-горе, в края на първия проход, ако масивът ще бъде сортиран във възходящ ред, най-големият елемент се поставя в края на списъка. За второто преминаване вторият по големина елемент се поставя на втората последна позиция в списъка и така нататък.
Когато достигнем N-1 (където N е общ брой елементи в списъка) преминава, ще имаме сортиране на целия списък.
какъв добър YouTube към mp3 конвертор
Техниката за сортиране на балончета може да бъде внедрена на всеки език за програмиране. Ние внедрихме алгоритъма за сортиране на балончета, използвайки C ++ и Java език по-долу.
Пример за C ++
Нека видим пример за програмиране, за да демонстрираме сорта на балончета.
#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
Пример за Java
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 елемента и го сортираме с помощта на техниката за сортиране на балончета. И в двете програми сме използвали две за цикли за итерация през съседните елементи на масива.
В края на всеки проход (външен цикъл), най-големият елемент в масива се балонче до края на масива. Също така броим броя на проходите, които са необходими за сортиране на целия масив.
Анализ на сложността на алгоритъма за сортиране на балончета
От псевдо кода и илюстрацията, която видяхме по-горе, в сортиране на балончета правим сравнения N-1 при първия проход, сравнения N-2 при втория проход и т.н.
Следователно общият брой сравнения при сортиране на балончета е:
I = (n-1) + (n-2) + (n-3) + ... + 3 + 2 + 1
= N (N-1) / 2
= O (nдве) => Сложност във времето на техниката за сортиране на балончета
По този начин различните сложности за техниката на сортиране на балончета са дадени по-долу:
Най-лошата времева сложност O (n 2) Най-добрата сложност във времето На) Средна времева сложност O (n 2) Космическа сложност O (1)
Техниката за сортиране на балончета изисква само едно допълнително пространство в паметта за временната променлива, за да улесни размяната. Следователно пространствената сложност на алгоритъма за сортиране на балончета е O (1).
Имайте предвид, че най-добрата сложност във времето за техниката на сортиране на балончета ще бъде, когато списъкът вече е сортиран и това ще бъде O (n).
Заключение
Основното предимство на Bubble Sort е простотата на алгоритъма. При сортиране на балончета при всяко преминаване най-големият елемент се мехурче до края на списъка, ако масивът е сортиран във възходящ ред.
По същия начин за списъка, който ще бъде сортиран в низходящ ред, най-малкият елемент ще бъде на правилното му място в края на всеки проход.
Тъй като е най-простата и лесна за прилагане техника за сортиране, сортирането с балон обикновено се използва за представяне на сортирането на аудиторията. На второ място, сортирането на балончета също се използва в приложение като компютърна графика, при което запълването на ръбове на многоъгълници и др. Изисква сортиране на балончета за сортиране на върховете, облицоващи полигона.
Въпроси и отговори за интервю за sql сървър за 5-годишен опит
В нашия предстоящ урок ще научим подробно за Сортиране на избора.
=> Посетете тук, за да научите C ++ от нулата.
Препоръчително четене
- Сортиране на черупката в C ++ с примери
- Сортиране на избора в C ++ с примери
- Метод за сортиране на MongoDB () с примери
- Команда за сортиране на Unix със синтаксис, опции и примери
- Сортиране по вмъкване в C ++ с примери
- Обединяване на сортиране в C ++ с примери
- Сортиране на купчини в C ++ с примери
- Бързо сортиране в C ++ с примери
