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

У овом упутству ћете научити како сортирање мехурића функционише. Такође, наћи ћете и радне примере мехурића у Ц, Ц ++, Јава и Питхон.

Буббле сорт је алгоритам који упоређује суседне елементе и замењује њихове положаје ако нису у предвиђеном редоследу. Поредак може бити узлазни или силазни.

Како сортирање мехурића функционише?

Полазећи од првог индекса, упоредите први и други елемент. Ако је први елемент већи од другог, они се замењују.
Сада упоредите други и трећи елемент. Замените их ако нису у реду.
Горњи поступак се наставља до последњег елемента. Упоредите суседне елементе
Исти поступак се наставља и за преостале понављања. После сваке итерације, највећи елемент међу несортираним елементима ставља се на крај.
У свакој итерацији поређење се одвија до последњег несортираног елемента.
Низ се сортира када се сви несортирани елементи поставе на тачне положаје. Упоредите суседне елементе Упоредите суседне елементе Упоредите суседне елементе

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

 бубблеСорт (низ) за и ригхтЕлемент замените лефтЕлемент и ригхтЕлемент крај бубблеСорт

Примери за Питхон, Јава и Ц / Ц ++

Питхон Јава Ц Ц ++

 # Bubble sort in Python def bubbleSort(array): # run loops two times: one for walking throught the array # and the other for comparison for i in range(len(array)): for j in range(0, len(array) - i - 1): # To sort in descending order, change> to array(j + 1): # swap if greater is at the rear position (array(j), array(j + 1)) = (array(j + 1), array(j)) data = (-2, 45, 0, 11, -9) bubbleSort(data) print('Sorted Array in Asc ending Order:') print(data)

 // Bubble sort in Java import java.util.Arrays; class BubbleSort ( void bubbleSort(int array()) ( int size = array.length; // run loops two times: one for walking throught the array // and the other for comparison for (int i = 0; i < size - 1; i++) for (int j = 0; j  to array(j + 1)) ( // swap if greater is at the rear position int temp = array(j); array(j) = array(j + 1); array(j + 1) = temp; ) ) // driver code public static void main(String args()) ( int() data = ( -2, 45, 0, 11, -9 ); BubbleSort bs = new BubbleSort(); bs.bubbleSort(data); System.out.println("Sorted Array in Ascending Order:"); System.out.println(Arrays.toString(data)); ) )

 // Bubble sort in C #include void bubbleSort(int array(), int size) ( // run loops two times: one for walking throught the array // and the other for comparison for (int step = 0; step < size - 1; ++step) ( for (int i = 0; i " to " array(i + 1)) ( // swap if greater is at the rear position int temp = array(i); array(i) = array(i + 1); array(i + 1) = temp; ) ) ) ) // function to print the array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( printf("%d ", array(i)); ) printf(""); ) // driver code int main() ( int data() = (-2, 45, 0, 11, -9); int size = sizeof(data) / sizeof(data(0)); bubbleSort(data, size); printf("Sorted Array in Ascending Order:"); printArray(data, size); )

 // Bubble sort in C++ #include using namespace std; void bubbleSort(int array(), int size) ( // run loops two times: one for walking throught the array // and the other for comparison for (int step = 0; step < size - 1; ++step) ( for (int i = 0; i to array(i + 1)) ( // swap if greater is at the rear position int temp = array(i); array(i) = array(i + 1); array(i + 1) = temp; ) ) ) ) // function to print the array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( cout << " " << array(i); ) cout << ""; ) // driver code int main() ( int data() = (-2, 45, 0, 11, -9); int size = sizeof(data) / sizeof(data(0)); bubbleSort(data, size); cout << "Sorted Array in Ascending Order:"; printArray(data, size); )

Оптимизирана сорта мехурића

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

Код се може оптимизовати увођењем додатне променљиве променљиве. Након сваке итерације, ако тада не дође до замене, нема потребе за извођењем даљњих петљи.

У том случају, променљива променљиве постављена је на фалсе. Тако можемо спречити даље понављање.

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

 бубблеСорт (низ) замењен <- нетачно за и ригхтЕлемент замењен лефтЕлемент и ригхтЕлемент замењен <- истинит крај бубблеСорт

Примери оптимизоване сорте мехурића

Питхон Јава Ц Ц +

 # Optimized bubble sort in python def bubbleSort(array): # Run loops two times: one for walking throught the array # and the other for comparison for i in range(len(array)): # swapped keeps track of swapping swapped = True for j in range(0, len(array) - i - 1): # To sort in descending order, change> to array(j + 1): # Swap if greater is at the rear position (array(j), array(j + 1)) = (array(j + 1), array(j)) swapped = False # If there is not swapping in the last swap, then the array is already sorted. if swapped: break data = (-2, 45, 0, 11, -9) bubbleSort(data) print('Sorted Array in Ascending Order:') print(data)

 // Optimized bubble sort in Java import java.util.Arrays; class BubbleSort ( void bubbleSort(int array()) ( int size = array.length; // Run loops two times: one for walking throught the array // and the other for comparison for (int i = 0; i < size - 1; i++) ( // swapped keeps track of swapping boolean swapped = true; for (int j = 0; j  to array(j + 1)) ( // Swap if greater is at the rear position int temp = array(j); array(j) = array(j + 1); array(j + 1) = temp; swapped = false; ) ) // If there is not swapping in the last swap, then the array is already sorted. if (swapped == true) break; ) ) // Driver code public static void main(String args()) ( int() data = ( -2, 45, 0, 11, -9 ); BubbleSort bs = new BubbleSort(); bs.bubbleSort(data); System.out.println("Sorted Array in Ascending Order:"); System.out.println(Arrays.toString(data)); ) )

 // Optimized bubble sort in C #include void bubbleSort(int arrayay(), int size) ( for (int step = 0; step < size - 1; ++step) ( // Swapped keeps track of swapping int swapped = 0; // Run loops two times: one for walking throught the array // and the other for comparison for (int i = 0; i to arrayay(i + 1)) ( // Swap if greater is at the rear position int temp = arrayay(i); arrayay(i) = arrayay(i + 1); arrayay(i + 1) = temp; swapped = 1; ) ) // If there is not swapping in the last swap, then the array is already sorted. if (swapped == 0) break; ) ) // Function to print an array void printarrayay(int arrayay(), int size) ( for (int i = 0; i < size; ++i) ( printf("%d ", arrayay(i)); ) printf(""); ) // Driver code int main() ( int data() = (-2, 45, 0, 11, -9); int size = sizeof(data) / sizeof(data(0)); bubbleSort(data, size); printf("Sorted Array in Ascending Order:"); printarrayay(data, size); )

 // Optimized bubble sort in C++ #include using namespace std; void bubbleSort(int array(), int size) ( for (int step = 0; step < size - 1; ++step) (

  // Run loops two times: one for walking throught the array // and the other for comparison int swapped = 0; for (int i = 0; i to array(i + 1)) ( // Swap if greater is at the rear position int temp = array(i); array(i) = array(i + 1); array(i + 1) = temp; swapped = 1; ) ) // If there is not swapping in the last swap, then the array is already sorted. if (swapped == 0) break; ) ) // Function to print an array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( cout << " " << array(i); ) cout << ""; ) // Driver code int main() ( int data() = (-2, 45, 0, 11, -9); int size = sizeof(data) / sizeof(data(0)); bubbleSort(data, size); cout << "Sorted Array in Ascending Order:"; printArray(data, size); )

Сложеност

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

Циклус	Број поређења
1ст	(н-1)
2нд	(н-2)
3.	(н-3)
…	…
последњи	1

Број поређења: (н - 1) + (н - 2) + (н - 3) + … + 1 = н (н - 1) / 2 готово једнако н ²

Сложеност: О (н ² )

Такође, можемо анализирати сложеност једноставним посматрањем броја петљи. Постоје 2 петље па је сложеностn*n = n²

Сложеност времена:

Најгоре сложеност случаја: Ако желимо да сортирамо у растућем редоследу, а низ је у опадајућем, тада се дешава најгори случај.O(n²)
Сложеност најбољег случаја:O(n)
Ако је низ већ сортиран, нема потребе за сортирањем.
Просечна сложеност случаја: Појављује се када су елементи низа у помешаном редоследу (ни растући ни силазни).O(n²)