Тема данной лекции, пузырьковая сортировка массива. Расскажу как она работает и как она выглядит на примере анимации и с подробный объяснением в разных языках программирования, например python, java, C++
Пузырьковая сортировка массива
Задача стоит следующем образом нам необходимо рассортировать какой то неопределенный массив в порядке возрастания. Сделать можно это применяя пузырьковую сортировку массива. Начинаем сортировку мы с самого начала нашей имеющийся последовательности, и постепенно шаг за шагом сравниваем последовательно каких либо два числа. Сравниваются два числа — правое и левое. Если левое число меньше правого то они меняются местами, В другом случае они остаются на своих местах и алгоритм продолжает перебирать цифры дальше, прямо как танцоры в видео, (обязательно посмотрите, там очень наглядно показано как работает такого рода пузырьковая сортировка)
Анимация пузырьковая сортировка
Подробный разбор пузырьковой сортировки
Давайте разберем подробно как работает пузырьковая сортировка
Первая итереация (первый повтор алгоритма) меняет между собой 4 и 2 так как цифра два меньше чем четыре 2<4, повторюсь что алгоритм меняет значения между собой если, слева оно меньше чем справа. Далее происходит сверка между 4 и 3, и так как 3 меньше чем 4 (3<4) происходит обмен значениями. Потом проходит проверку между 4 и 8 и так как значение 4 меньше чем 8 то не происходит обмена, ведь уже и так всё на своих местах. 🙂
Далее сравнивается 8 и 1 и так как 1 меньше чем 8 (1<8) и оно не находиться слева то происходит обмен значениями.После это первый повтор алгоритма заканчивается, на анимации я выделил это зеленым фоном.
В итоге по окончанию работы алгоритма пузырьковой сортировки мы имеем следующий порядок числового массива: 2 3 4 1 8
и начинается второй повтор алгоритма.
Далее сравнивается 2 и 3 и так как два меньше чем три и оно находиться слева то просто идем дальше ничего не трогая. Также проверяем и 3 и 4 и тоже самое условие выполняется 3<4 и оно слева. Дальше проверяется 4 и 1 и тут мы видим что число 1<4 и не находиться слева, поэтому алгоритм меняет их местами. В крайний раз для второго повторения алгоритма проверяется 4 и 8, но тут всё в порядке, и мы дошли до конца начинаем третье повторение. Итоги для второго повторения такие : 2 3 1 4 8
Третье повторение пузырькового алгоритма начинается с сравнения 2 и 3, тут алгоритм проверяет что 2<3 и 2 находиться слева и оставляет их в покое и идет дальше. Сравнение же 3 и 1 показывает что 1 то меньше чем три, но почему то не слева и меняет их местами. Далее идет сравнение 3 и 4, тут всё в порядке и так далее до сравнения 4 и 8.
После этого получается следующий результат: 2 1 3 4 8
Как мы видим почти все цифры уже на своих местах и в порядке возрастания! Осталось только в последнем повторении пузырькового алгоритма поменять местами 2 и 1 и всё. После того как алгоритм закончил свою работу и проверил что цифры больше нельзя поменять местами он перестает работать с таким вот результатом: 1 2 3 4 8
Краткое объяснение:
Главное надо запомнить что алгоритм пузырьковой сортировки работает следующим образом — меняет в порядке возрастания последовательно два элемента до тех пор пока они все не будут расположены по порядку в массиве.
Видео как работает пузырьковая сортировка
Пузырьковая сортировка Python пример кода
Давайте теперь я продемонстрирую реализацию данного алгоритма на языке python
from random import randint
def bubblesort(array):
for i in range(N-1):
for j in range(N-i-1):
if array[j] > array[j+1]:
buff = array[j]
array[j] = array[j+1]
array[j+1] = buff
N = 10
a = []
for i in range(N):
a.append(randint(1, 99))
print(a)
bubblesort(a)
print(a)
Пузырьковая сортировка Java пример кода
Давайте теперь я продемонстрирую реализацию данного алгоритма на языке java
public static void main(String[] args) throws Exception {
BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
int a = Integer.parseInt(read.readLine());
int b = Integer.parseInt(read.readLine());
int c = Integer.parseInt(read.readLine());
int d = Integer.parseInt(read.readLine());
int e = Integer.parseInt(read.readLine());
int arr[] = {a, b, c, d, e};
bubbleSort(arr);
}
public static void bubbleSort(int[] arr) {
for (int i = arr.length-1; i > 0; i--) {
for (int j = 0; j < i; j++) {
if (arr[j] > arr[j + 1]) {
int a = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = a;
}
}
}
for (int i = 0; i < arr.length; i++)
System.out.println(arr[i]);
}
Пузырьковая сортировка с++ пример кода
Давайте теперь я продемонстрирую реализацию данного алгоритма на языке си++.
#include "stdafx.h"
#include <iostream>
#include <fstream>
#include <clocale>
using namespace std;
int main()
{
setlocale(LC_CTYPE,"rus");
const int N=5; //размер массива
int array[N];// массив куда будут считываться пять чисел
ifstream f("arr.txt");// файл содержащий последовательность чисел
cout<<"Неотсортированный массив:";
for(int i=0;i<N;i++)
{
f>>array[i];// запись в массив чисел из файла
cout<<array[i]<<" ";
}
cout<<endl;
// собственно сам алгоритм сортировки пузырьком
for(int i=N-1;i>=1;i--)
for(int j=0;j<i;j++)
{
if(array[j]>array[j+1])
{// меняем местами элементы
int temp(0);
temp=array[j];
array[j]=array[j+1];
array[j+1]=temp;
}
}
// выводим отсортированный с помощью пузырька массив
cout<<"Пузырьковая сортировка:";
for(int i=0;i<N;i++)cout<<array[i]<<" ";
cout<<endl;
return 0;
}
Результат выполненной программы:
Спасибо, что прочитали лекцию!