Рубрики

Пузырьковая сортировка

Bubble Sort — это самый простой алгоритм сортировки, который работает путем многократного обмена смежными элементами, если они находятся в неправильном порядке.

Пример:
Первый проход:
( 5 1 4 2 8) -> ( 1 5 4 2 8), Здесь алгоритм сравнивает первые два элемента и переставляет с 5> 1.
(1 5 4 2 8) -> (1 4 5 2 8), поменять местами с 5> 4
(1 4 5 2 8) -> (1 4 2 5 8), поменять местами с 5> 2
(1 4 2 5 8 ) -> (1 4 2 5 8 ), Теперь, так как эти элементы уже в порядке (8> 5), алгоритм не меняет их местами.

Второй проход:
( 1 4 2 5 8) -> ( 1 4 2 5 8)
(1 4 2 5 8) -> (1 2 4 5 8), поменять местами с 4> 2
(1 2 4 5 8) -> (1 2 4 5 8)
(1 2 4 5 8 ) -> (1 2 4 5 8 )
Теперь массив уже отсортирован, но наш алгоритм не знает, завершен ли он. Алгоритму нужен один полный проход без какого-либо обмена, чтобы знать, что он отсортирован.

Третий проход:
( 1 2 4 5 8) -> ( 1 2 4 5 8)
(1 2 4 5 8) -> (1 2 4 5 8)
(1 2 4 5 8) -> (1 2 4 5 8)
(1 2 4 5 8 ) -> (1 2 4 5 8 )

Ниже приведены реализации Bubble Sort.

C ++

// C ++ программа для реализации Bubble sort
#include <bits/stdc++.h>

using namespace std;

  

void swap(int *xp, int *yp) 

    int temp = *xp; 

    *xp = *yp; 

    *yp = temp; 

  
// Функция для реализации пузырьковой сортировки

void bubbleSort(int arr[], int n) 

    int i, j; 

    for (i = 0; i < n-1; i++)     

      

    // Последние элементы i уже на месте

    for (j = 0; j < n-i-1; j++) 

        if (arr[j] > arr[j+1]) 

            swap(&arr[j], &arr[j+1]); 

  
/ * Функция для печати массива * /

void printArray(int arr[], int size) 

    int i; 

    for (i = 0; i < size; i++) 

        cout << arr[i] << " "

    cout << endl; 

  
// Код драйвера

int main() 

    int arr[] = {64, 34, 25, 12, 22, 11, 90}; 

    int n = sizeof(arr)/sizeof(arr[0]); 

    bubbleSort(arr, n); 

    cout<<"Sorted array: \n"

    printArray(arr, n); 

    return 0; 

  
// Этот код предоставлен rathbhupendra

С

// C программа для реализации Bubble sort
#include <stdio.h>

  

void swap(int *xp, int *yp)

{

    int temp = *xp;

    *xp = *yp;

    *yp = temp;

}

  
// Функция для реализации пузырьковой сортировки

void bubbleSort(int arr[], int n)

{

   int i, j;

   for (i = 0; i < n-1; i++)      

  

       // Последние элементы i уже на месте

       for (j = 0; j < n-i-1; j++) 

           if (arr[j] > arr[j+1])

              swap(&arr[j], &arr[j+1]);

}

  
/ * Функция для печати массива * /

void printArray(int arr[], int size)

{

    int i;

    for (i=0; i < size; i++)

        printf("%d ", arr[i]);

    printf("\n");

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    int arr[] = {64, 34, 25, 12, 22, 11, 90};

    int n = sizeof(arr)/sizeof(arr[0]);

    bubbleSort(arr, n);

    printf("Sorted array: \n");

    printArray(arr, n);

    return 0;

}

Джава

// Java-программа для реализации Bubble Sort

class BubbleSort

{

    void bubbleSort(int arr[])

    {

        int n = arr.length;

        for (int i = 0; i < n-1; i++)

            for (int j = 0; j < n-i-1; j++)

                if (arr[j] > arr[j+1])

                {

                    // поменять местами arr [j + 1] и arr [i]

                    int temp = arr[j];

                    arr[j] = arr[j+1];

                    arr[j+1] = temp;

                }

    }

  

    / * Печатает массив * /

    void printArray(int arr[])

    {

        int n = arr.length;

        for (int i=0; i<n; ++i)

            System.out.print(arr[i] + " ");

        System.out.println();

    }

  

    // Метод драйвера для тестирования выше

    public static void main(String args[])

    {

        BubbleSort ob = new BubbleSort();

        int arr[] = {64, 34, 25, 12, 22, 11, 90};

        ob.bubbleSort(arr);

        System.out.println("Sorted array");

        ob.printArray(arr);

    }

}
/ * Этот код предоставлен Раджатом Мишрой * /

питон

# Python программа для реализации Bubble Sort

  

def bubbleSort(arr):

    n = len(arr)

  

    # Обход всех элементов массива

    for i in range(n):

  

        # Последние элементы i уже на месте

        for j in range(0, n-i-1):

  

            # пройти массив от 0 до ni-1

            # Поменяйте местами, если найденный элемент больше

            # чем следующий элемент

            if arr[j] > arr[j+1] :

                arr[j], arr[j+1] = arr[j+1], arr[j]

  
# Код драйвера для проверки выше

arr = [64, 34, 25, 12, 22, 11, 90]

  
bubbleSort(arr)

  

print ("Sorted array is:")

for i in range(len(arr)):

    print ("%d" %arr[i]), 

C #

// C # программа для реализации
// пузырьковой сортировки

using System;

  

class GFG

    static void bubbleSort(int []arr)

    {

        int n = arr.Length;

        for (int i = 0; i < n - 1; i++)

            for (int j = 0; j < n - i - 1; j++)

                if (arr[j] > arr[j + 1])

                {

                    // поменяйте местами temp и arr [i]

                    int temp = arr[j];

                    arr[j] = arr[j + 1];

                    arr[j + 1] = temp;

                }

    }

  

    / * Печатает массив * /

    static void printArray(int []arr)

    {

        int n = arr.Length;

        for (int i = 0; i < n; ++i)

            Console.Write(arr[i] + " ");

        Console.WriteLine();

    }

  

    // Метод драйвера

    public static void Main()

    {

        int []arr = {64, 34, 25, 12, 22, 11, 90};

        bubbleSort(arr);

        Console.WriteLine("Sorted array");

        printArray(arr);

    }

  
}

  
// Этот код предоставлен Sam007

PHP

<?php 
// PHP программа для реализации
// пузырьковой сортировки

  

function bubbleSort(&$arr)

{

    $n = sizeof($arr);

  

    // Обход всех элементов массива

    for($i = 0; $i < $n; $i++) 

    {

        // Последние элементы i уже на месте

        for ($j = 0; $j < $n - $i - 1; $j++) 

        {

            // пройти массив от 0 до ni-1

            // Меняем местами, если найденный элемент больше

            // чем следующий элемент

            if ($arr[$j] > $arr[$j+1])

            {

                $t = $arr[$j];

                $arr[$j] = $arr[$j+1];

                $arr[$j+1] = $t;

            }

        }

    }

}

  
// Код драйвера для проверки выше

$arr = array(64, 34, 25, 12, 22, 11, 90);

  

$len = sizeof($arr);

bubbleSort($arr);

  

echo "Sorted array : \n";

  

for ($i = 0; $i < $len; $i++)

    echo $arr[$i]." "

  
// Этот код предоставлен ChitraNayal.
?>


Выход:

Sorted array:
11 12 22 25 34 64 90

<! —- Иллюстрация:

->

Оптимизированная реализация:
Вышеуказанная функция всегда запускает O (n ^ 2) раз, даже если массив отсортирован. Его можно оптимизировать, остановив алгоритм, если внутренний цикл не вызвал перестановки.

CPP

// Оптимизированная реализация Bubble sort
#include <stdio.h>

  

void swap(int *xp, int *yp)

{

    int temp = *xp;

    *xp = *yp;

    *yp = temp;

}

  
// Оптимизированная версия Bubble Sort

void bubbleSort(int arr[], int n)

{

   int i, j;

   bool swapped;

   for (i = 0; i < n-1; i++)

   {

     swapped = false;

     for (j = 0; j < n-i-1; j++)

     {

        if (arr[j] > arr[j+1])

        {

           swap(&arr[j], &arr[j+1]);

           swapped = true;

        }

     }

  

     // Если два внутренних элемента не были заменены внутренним циклом, то разрыв

     if (swapped == false)

        break;

   }

}

  
/ * Функция для печати массива * /

void printArray(int arr[], int size)

{

    int i;

    for (i=0; i < size; i++)

        printf("%d ", arr[i]);

    printf("n");

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    int arr[] = {64, 34, 25, 12, 22, 11, 90};

    int n = sizeof(arr)/sizeof(arr[0]);

    bubbleSort(arr, n);

    printf("Sorted array: \n");

    printArray(arr, n);

    return 0;

}

Джава

// Оптимизированная реализация Java
// пузырьковой сортировки

import java.io.*;

  

class GFG 

{

    // Оптимизированная версия Bubble Sort

    static void bubbleSort(int arr[], int n)

    {

        int i, j, temp;

        boolean swapped;

        for (i = 0; i < n - 1; i++) 

        {

            swapped = false;

            for (j = 0; j < n - i - 1; j++) 

            {

                if (arr[j] > arr[j + 1]) 

                {

                    // меняем местами arr [j] и arr [j + 1]

                    temp = arr[j];

                    arr[j] = arr[j + 1];

                    arr[j + 1] = temp;

                    swapped = true;

                }

            }

  

            // Если двух элементов не было

            // меняем местами по внутреннему циклу, затем ломаем

            if (swapped == false)

                break;

        }

    }

  

    // Функция для печати массива

    static void printArray(int arr[], int size)

    {

        int i;

        for (i = 0; i < size; i++)

            System.out.print(arr[i] + " ");

        System.out.println();

    }

  

    // Драйвер программы

    public static void main(String args[])

    {

        int arr[] = { 64, 34, 25, 12, 22, 11, 90 };

        int n = arr.length;

        bubbleSort(arr, n);

        System.out.println("Sorted array: ");

        printArray(arr, n);

    }

}

  

  
// Этот код добавлен
// Никита Тивари.

python3

# Python3 Оптимизированная реализация
№ пузырькового сорта

  
# Оптимизированная версия Bubble Sort

def bubbleSort(arr):

    n = len(arr)

   

    # Обход всех элементов массива

    for i in range(n):

        swapped = False

  

        # Последние элементы i уже

        # на месте

        for j in range(0, n-i-1):

   

            # пройти массив от 0 до

            # ni-1. Поменяйте местами, если элемент

            # найдено больше, чем

            # следующий элемент

            if arr[j] > arr[j+1] :

                arr[j], arr[j+1] = arr[j+1], arr[j]

                swapped = True

  

        # Если два элемента не были поменяны местами

        # по внутреннему циклу, затем перерыв

        if swapped == False:

            break

           
# Код драйвера для проверки выше

arr = [64, 34, 25, 12, 22, 11, 90]

   
bubbleSort(arr)

   

print ("Sorted array :")

for i in range(len(arr)):

    print ("%d" %arr[i],end=" ")

  
# Этот код предоставлен Shreyanshi Arun

C #

// Оптимизированная реализация C #
// пузырьковой сортировки

using System;

  

class GFG

    // Оптимизированная версия Bubble Sort

    static void bubbleSort(int []arr, int n)

    {

        int i, j, temp;

        bool swapped;

        for (i = 0; i < n - 1; i++) 

        {

            swapped = false;

            for (j = 0; j < n - i - 1; j++) 

            {

                if (arr[j] > arr[j + 1]) 

                {

                    // меняем местами arr [j] и arr [j + 1]

                    temp = arr[j];

                    arr[j] = arr[j + 1];

                    arr[j + 1] = temp;

                    swapped = true;

                }

            }

  

            // Если двух элементов не было

            // меняем местами по внутреннему циклу, затем ломаем

            if (swapped == false)

                break;

        }

    }

  

    // Функция для печати массива

    static void printArray(int []arr, int size)

    {

        int i;

        for (i = 0; i < size; i++)

            Console.Write(arr[i] + " ");

        Console.WriteLine();

    }

  

    // Метод драйвера

    public static void Main()

    {

        int []arr = {64, 34, 25, 12, 22, 11, 90};

        int n = arr.Length;

        bubbleSort(arr,n);

        Console.WriteLine("Sorted array");

        printArray(arr,n);

    }

  
}
// Этот код предоставлен Sam007

PHP

<?php 
// PHP оптимизированная реализация
// пузырьковой сортировки

  
// Оптимизированная версия Bubble Sort

function bubbleSort(&$arr)

{

    $n = sizeof($arr);

  

    // Обход всех элементов массива

    for($i = 0; $i < $n; $i++)

    {

        $swapped = False;

  

        // Последние элементы i уже

        // на месте

        for ($j = 0; $j < $n - $i - 1; $j++)

        {

              

            // пройти массив от 0 до

            // ni-1. Поменяйте местами, если элемент

            // найдено больше чем

            // следующий элемент

            if ($arr[$j] > $arr[$j+1])

            {

                $t = $arr[$j];

                $arr[$j] = $arr[$j+1];

                $arr[$j+1] = $t;

                $swapped = True;

            }

        }

  

        // Если два элемента не были поменяны местами

        // по внутреннему циклу, затем разрыв

        if ($swapped == False)

            break;

    }

}

          
// Код драйвера для проверки выше

$arr = array(64, 34, 25, 12, 22, 11, 90); 

$len = sizeof($arr);

bubbleSort($arr);

  

echo "Sorted array : \n";

  

for($i = 0; $i < $len; $i++)

    echo $arr[$i]." ";

      
// Этот код предоставлен ChitraNayal.
?>


Выход:

Sorted array:
11 12 22 25 34 64 90

Наихудшая и средняя сложность времени дела: O (n * n). В худшем случае происходит обратная сортировка массива.

Сложность времени в лучшем случае: O (n). Лучший случай происходит, когда массив уже отсортирован.

Вспомогательное пространство: O (1)

Boundary Cases: Bubble sort занимает минимальное время (порядок n), когда элементы уже отсортированы.

Сортировка на месте: да

Стабильно: да

Из-за своей простоты пузырьковая сортировка часто используется для представления концепции алгоритма сортировки.
В компьютерной графике он популярен благодаря своей способности обнаруживать очень маленькую ошибку (например, замену всего двух элементов) в почти отсортированных массивах и исправлять ее просто линейной сложностью (2n). Например, он используется в алгоритме заполнения полигонов, где ограничивающие линии сортируются по их координате x на конкретной линии сканирования (линия, параллельная оси x), а с увеличением y их порядок изменяется (два элемента меняются местами) только на пересечениях. из двух строк (Источник: Википедия )

Фотосъёмка:





Викторина по пузырьковой сортировке

Другие алгоритмы сортировки на GeeksforGeeks / GeeksQuiz:

Рекурсивная сортировка по пузырькам

Практика кодирования для сортировки.

Ссылка:

Рекомендуемые посты:

Пузырьковая сортировка

0.00 (0%) 0 votes