Различия

Показаны различия между двумя версиями страницы.

@@ Строка 1: / Строка 1: @@
+====== Пузырьковая сортировка ======
+~~Title: Сортировка пузырьком С++ ~~
+{{htmlmetatags>
+metatag-description=(Самый известный алгоритм сортировки — пузырьковая сортировка. Алгоритм пузырьковой сортировки - это простой в реализации алгоритм для сортировки массивов.)
+}}
+Сортировка простыми обменами, сортировка пузырьком (англ. bubble sort) — простой алгоритм сортировки. Для понимания и реализации этот алгоритм — простейший, но эффективен он лишь для небольших массивов.
+<note important>Алгоритм считается учебным и практически не применяется вне учебной литературы, вместо него на практике применяется [[сортировка вставками]].</note>
+Суть алгоритма заключается в повторяющихся проходах по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован. При проходе алгоритма, элемент, стоящий не на своём месте, «всплывает» до нужной позиции как пузырёк в воде, отсюда и название алгоритма.
+Для реализации расположим массив сверху вниз, от нулевого элемента - к последнему. После нулевого прохода по массиву "вверху" оказывается самый "легкий" элемент - отсюда аналогия с пузырьком. Следующий проход делается до второго сверху элемента, таким образом второй по величине элемент поднимается на правильную позицию.
+{{:puz3.gif|}}
+Делаем проходы по все уменьшающейся нижней части массива до тех пор, пока в ней не останется только один элемент. На этом сортировка заканчивается, так как последовательность упорядочена по возрастанию.
+{{:puz4.gif|}}
+[[algoritm]]
+====== Пример кода PHP ======
+Пример кода на языке [[PHP]].
+<file>
+for ($i=(count($A)-1);$i>=0;$i--) {
+    for ($j=0;$j<=($i-1);$j++)
+        if ($A[]>$A[$j+1]) {
+            $tmp = $A[$j];
+            $A[$j] = $A[$j+1];
+            $A[$j+1] = $tmp;
+        }
+}
+</file>
+====== Пример кода C++ ======
+Пример кода на языке C++.
+<file>
+#include <iostream>
+#include <stdlib.h>
+#include <time.h>
+using namespace std;
+template <class T>
+void bubbleSort(T a[], long size){
+    long i, j;
+	T x;
+	for(i=0;i<size;i++){            // i - номер прохода
+		for(j=size-1;j>i;j--){     // внутренний цикл прохода
+			if(a[j-1]>a[j]){
+				x=a[j-1];
+				a[j-1]=a[j];
+				a[j]=x;
+			}
+		}
+	}
+}
+void main(){
+	srand(time(NULL));
+	const long SIZE=10;
+	int ar[SIZE];
+	// до сортировки
+	for(int i=0;i<SIZE;i++){
+		ar[i]=rand()%100;
+		cout<<ar[i]<<"\t";
+	}
+	cout<<"\n\n";
+	bubbleSort(ar,SIZE);
+	// после сортировки
+	for(int i=0;i<SIZE;i++){
+		cout<<ar[i]<<"\t";
+	}
+	cout<<"\n\n";
+}
+</file>
+====== Основные принципы метода ======
+Среднее число сравнений и обменов имеют квадратичный порядок роста, отсюда можно заключить, что алгоритм пузырька очень медленен и малоэффективен. Тем не менее, у него есть громадный плюс: он прост и его можно по-всякому улучшать. Чем мы сейчас и займемся.
+Рассмотрим ситуацию, когда на каком-либо из проходов не произошло ни одного обмена. Это значит, что все пары расположены в правильном порядке, так что массив уже отсортирован. И продолжать процесс не имеет смысла. Таким образом первый шаг оптимизации заключается в запоминании, производился ли на данном проходе какой-либо обмен. Если нет - алгоритм заканчивает работу.
+Процесс оптимизации можно продолжить, запоминая не только сам факт обмена, но и индекс последнего обмена k. Действительно: все пары соседих элементов с индексами, меньшими k, уже расположены в нужном порядке. Дальнейшие проходы можно заканчивать на индексе k, вместо того чтобы двигаться до установленной заранее верхней границы i.
+Качественно другое улучшение алгоритма можно получить из следующего наблюдения. Хотя "легкий" пузырек снизу поднимется наверх за один проход, "тяжелые" пузырьки опускаются со минимальной скоростью: один шаг за итерацию. Так что массив 2 3 4 5 6 1 будет отсортирован за 1 проход, а сортировка последовательности 6 1 2 3 4 5 потребует 5 проходов.
+Чтобы избежать подобного эффекта, можно менять направление следующих один за другим проходов. Получившийся алгоритм иногда называют "шейкер-сортировкой".
+<file>
+#include <iostream>
+#include <stdlib.h>
+#include <time.h>
+using namespace std;
+template <class T>
+void shakerSort(T a[], long size) {
+  long j, k=size-1;
+  long lb=1, ub=size-1; // границы неотсортированной части массива
+  T x;
+  do{
+      // проход снизу вверх
+	for(j=ub;j>0;j--){
+		if(a[j-1]>a[j]){
+			x=a[j-1];
+			a[j-1]=a[j];
+			a[j]=x;
+			k=j;
+		}
+	}
+    lb = k+1;
+    // проход сверху вниз
+    for(j=1;j<=ub;j++){
+		if(a[j-1]>a[j]){
+			x=a[j-1];
+			a[j-1]=a[j];
+			a[j]=x;
+			k=j;
+		}
+    }
+    ub=k-1;
+  }while (lb<ub);
+}
+void main(){
+	srand(time(NULL));
+	const long SIZE=10;
+	int ar[SIZE];
+	// до сортировки
+	for(int i=0;i<SIZE;i++){
+		ar[i]=rand()%100;
+		cout<<ar[i]<<"\t";
+	}
+	cout<<"\n\n";
+	shakerSort(ar,SIZE);
+	// после сортировки
+	for(int i=0;i<SIZE;i++){
+		cout<<ar[i]<<"\t";
+	}
+	cout<<"\n\n";
+}
+</file>
+Таким образом, мы выяснили, что можем оптимизировать сортировку "пузырьком" на свой вкус.

📌 Удобный подбор VPS по параметрам доступен на DIEGfinder.com - официальном инструменте проекта DIEG. Это часть единой экосистемы, созданной для того, чтобы помочь быстро найти подходящий VPS/VDS сервер для любых задач хостинга.

📌 Для тестирования скриптов, установщиков VPN и Python-ботов рекомендуем использовать надежные VPS на короткий срок. Подробнее о быстрой аренде VPS для экспериментов - читайте здесь.

💥 Подпишись в Телеграм 💥 и задай вопрос по сайтам и хостингам бесплатно!

Различия

7 Самых Популярных Статей

7 Самых Популярных Обзоров