Массив пузырьковый метод. Сортировка пузырьком. Во всём виноваты черепашки
Теги: Сортировка пузырьком си, си пузырьковая сортировка, сортировка пузырьком двумерного массива
Сортировка пузырьком
И дея алгоритма очень простая. Идём по массиву чисел и проверяем порядок (следующее число должно быть больше и равно предыдущему), как только наткнулись на нарушение порядка, тут же обмениваем местами элементы, доходим до конца массива, после чего начинаем сначала.
Отсортируем массив {1, 5, 2, 7, 6, 3}
Идём по массиву, проверяем первое число и второе, они идут в порядке возрастания. Далее идёт нарушение порядка, меняем местами эти элементы
1, 2, 5, 7, 6, 3
Продолжаем идти по массиву, 7 больше 5, а вот 6 меньше, так что обмениваем из местами
1, 2, 5, 6, 7, 3
3 нарушает порядок, меняем местами с 7
1, 2, 5, 6, 3, 7
Возвращаемся к началу массива и проделываем то же самое
1, 2, 5, 3, 6, 7
1, 2, 3, 5, 6, 7
Говорят, что это похоже на "всплытие" более "лёгких" элементов, как пузырьков, отчего алгоритм и получил такое название. void bubbleSort(int *a, size_t size) { size_t i, j; int tmp; for (i = 1; i < size; i++) { for (j = 1; j < size; j++) { if (a[j] > a) { tmp = a[j]; a[j] = a; a = tmp; } } } }
Этот алгоритм всегда будет делать (n-1) 2 шагов, независимо от входных данных. Даже если массив отсортирован, всё равно он будет пройден (n-1) 2 раз. Более того, будут в очередной раз проверены уже отсортированные данные.
Пусть нужно отсортировать массив 1, 2, 4, 3
1 2 4 3
1 2 4 3
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
После того, как были поменяны местами элемента a и a нет больше необходимости проходить этот участок массива. Примем это во внимание и переделаем алгоритм
Void bubbleSort2(int *a, size_t size) { size_t i, j; int tmp; for (i = 1; i < size; i++) { for (j = i; j > 0; j--) { if (a[j] < a) { tmp = a[j]; a[j] = a; a = tmp; } } } }
Ещё одна реализация
Void bubbleSort2b(int *a, size_t size) { size_t i, j; int tmp; for (i = 1; i < size; i++) { for (j = 1; j <= size-i; j++) { if (a[j] < a) { tmp = a[j]; a[j] = a; a = tmp; } } } }
В данном случае будет уже вполовину меньше шагов, но всё равно остаётся проблема сортировки уже отсортированного массива: нужно сделать так, чтобы отсортированный массив функция просматривала один раз. Для этого введём переменную-флаг: он будет опущен (flag = 0), если массив отсортирован. Как только мы наткнёмся на нарушение порядка, то флаг будет поднят (flag = 1) и мы начнём сортировать массив как обычно.
Void bubbleSort3(int *a, size_t size) { size_t i; int tmp; char flag; do { flag = 0; for (i = 1; i < size; i++) { if (a[i] < a) { tmp = a[i]; a[i] = a; a = tmp; flag = 1; } } } while (flag); }
В этом случае сложность также порядка n 2 , но в случае отсортированного массива будет всего один проход.
Теперь усовершенствуем алгоритм. Напишем функцию общего вида, чтобы она сортировала массив типа void. Так как тип переменной не известен, то нужно будет дополнительно передавать размер одного элемента массива и функцию сравнения.
Int intSort(const void *a, const void *b) { return *((int*)a) > *((int*)b); } void bubbleSort3g(void *a, size_t item, size_t size, int (*cmp)(const void*, const void*)) { size_t i; void *tmp = NULL; char flag; tmp = malloc(item); do { flag = 0; for (i = 1; i < size; i++) { if (cmp(((char*)a + i*item), ((char*)a + (i-1)*item))) { memcpy(tmp, ((char*)a + i*item), item); memcpy(((char*)a + i*item), ((char*)a + (i-1)*item), item); memcpy(((char*)a + (i-1)*item), tmp, item); flag = 1; } } } while (flag); free(tmp); }
Функция выглядит некрасиво – часто вычисляется адрес текущего и предыдущего элемента. Выделим отдельные переменные для этого.
Void bubbleSort3gi(void *a, size_t item, size_t size, int (*cmp)(const void*, const void*)) { size_t i; void *tmp = NULL; void *prev, *cur; char flag; tmp = malloc(item); do { flag = 0; i = 1; prev = (char*)a; cur = (char*)prev + item; while (i < size) { if (cmp(cur, prev)) { memcpy(tmp, prev, item); memcpy(prev, cur, item); memcpy(cur, tmp, item); flag = 1; } i++; prev = (char*)prev + item; cur = (char*)cur + item; } } while (flag); free(tmp); }
Теперь с помощью этих функций можно сортировать массивы любого типа, например
Void main() { int a = {1, 0, 9, 8, 7, 6, 2, 3, 4, 5}; int i; bubbleSort3gi(a, sizeof(int), 10, intSort); for (i = 0; i < 10; i++) { printf("%d ", a[i]); } _getch(); }
Сортировка многомерного массива
С ортировка статического многомерного массива по существу не отличается от сортировки одномерного. Можно воспользоваться тем свойством, что статический одномерный и многомерный массивы имеют одинаковое представление в памяти.
Void main() {
int a = {1, 9, 2, 8, 3, 7, 4, 6, 5};
int i, j;
bubbleSort3gi(a, sizeof(int), 9, intSort);
for (i = 0; i < 3; i++) {
for (j = 0; j < 3; j++) {
printf("%d ", a[i][j]);
}
}
}
Сортировка динамически созданного двумерного массива может быть произведена двумя способами. Во-первых, можно по определённому алгоритму находить индекс i-го и j-го элемента по порядковому номеру k от 0 до n * m.
#include
Во-вторых, можно сначала переместить массив в одномерный, отсортировать одномерный массив, после чего переместить его обратно в двумерный.
Void bubbleSort3gi2d(void **a, size_t item, size_t m, size_t n, int (*cmp)(const void*, const void*)) { size_t size = m*n, sub_size = n*item; size_t i, j, k; void *arr = malloc(size * item); char *p1d = (char*)arr; char *p2d = (char*)a; //Копируем двумерный массив типа void в одномерный for (i = 0; i < m; i++) { memcpy(p1d + i*sub_size, *((void**)(p2d + i*item)), sub_size); } bubbleSort3gi(arr, item, size, cmp); //Копируем одномерный массив обратно в двумерный for (i = 0; i < m; i++) { memcpy(*((void**)(p2d + i*item)), p1d + i*sub_size, sub_size); } }
Если вас смущает эта функция, то воспользуйтесь типизированной. Вызов, из предыдущего примера
Существует довольно большое количество алгоритмов сортировки, многие из них весьма специфические и разрабатывались для решения узкого круга задач и работы с конкретными типами данных. Но среди всего этого многообразия самым простейшим алгоритмом заслуженно является пузырьковая сортировка, которую можно реализовать на любом языке программирования. Несмотря на свою простоту, она лежит в основе многих довольно сложных алгоритмов. Другим ее не менее важным достоинством является ее простота, а, следовательно, ее можно вспомнить и реализовать сходу, не имея перед глазами какой-либо дополнительной литературы.
Введение
Весь современный интернет представляет из себя огромное количество разнотипных структур данных, собранных в базы данных. В них хранится всевозможная информация, начиная от личных данных пользователей и заканчивая семантическим ядром высокоинтеллектуальных автоматизированных системами. Стоит-ли говорить о том, что сортировка данных играет крайне важную роль в этом огромном количестве структурированной информации. Сортировка может стать обязательным шагом перед поиском какой-либо информации в базе, и знание алгоритмов сортировки играет крайне важную роль в программировании. Существует довольно большое количество алгоритмов сортировки, многие из них весьма специфические и разрабатывались для решения узкого круга задач и работы с конкретными типами данных. Но среди всего этого многообразия самым простейшим алгоритмом заслуженно является пузырьковая сортировка , которую можно реализовать на любом языке программирования. Несмотря на свою простоту, она лежит в основе многих довольно сложных алгоритмов. Другим ее не менее важным достоинством является ее простота, а, следовательно, ее можно вспомнить и реализовать сходу, не имея перед глазами какой-либо дополнительной литературы.Сортировка глазами машины и глазами человека
Давайте представим, что вам нужно отсортировать по возрастанию 5 столбиков разной высоты. Под этими столбиками может пониматься какая угодно информация (цены на акции, пропускная способность канала связи и пр.), можете представить какой-то свой вариант этой задачи, чтобы было более наглядно. Ну а мы, в качестве примера, будем сортировать мстителей по росту:Вам, в отличие от компьютерной программы сортировка не составит никого труда, ведь вы способны видеть картину в целом и сразу сможете прикинуть, какого героя, куда нужно переместить, чтобы сортировка по росту была выполнена успешно. Вы уже наверняка догадались, что для сортировки по возрастанию этой структуры данных достаточно поменять местами Халка и Железного человека:
Done!
И на этом сортировка будет успешно завершена. Однако, вычислительная машина в отличие от вас несколько туповата не видит всю структуру данных целиком. Ее программа управления может сравнивать лишь два значения в один промежуток времени. Для решения этой задачи ей продеться помесить в свою память два числа и выполнить над ними операцию сравнения, после чего перейти к другой паре чисел, а так до тех пор, пока не будут проанализированы все данные. Поэтому любой алгоритм сортировки очень упрощенно можно представить виде трех шагов:- Сравнить два элемента;
- Поменять местами или скопировать один из них;
- Перейти к следующему элементу;
Алгоритм пузырьковой сортировки
Пузырьковая сортировка считается самой простой, но перед тем как описывать этот алгоритм давайте представим, как бы вы отсортировали мстителей по росту, если бы могли, как и машина сравнивать между собой лишь двух героев в один промежуток времени. Скорее всего, вы бы поступили (самым оптимальным) следующим образом:- Вы перемещаетесь к нулевому элементу нашего массива (Черная Вдова);
- Сравниваете нулевой элемент (Черную Вдову) с первым (Халком);
- Если элемент на нулевой позиции оказался выше, вы меняете их местами;
- Иначе, если элемент на нулевой позиции меньше, вы оставляете их на своих местах;
- Производите переход на позицию правее и повторяете сравнение (сравниваете Халка с Капитаном)
После того, как вы пройдете с таким алгоритмом по всему списку за один проход, сортировка будет произведена не полностью. Но зато, самый большой элемент в списке будет перемещен в крайнюю правую позицию. Это будет происходить всегда, ведь как только вы найдете самый большой элемент, вы все время будете менять его местами пока не переместите в самый конец. То есть, как только программа «найдет» Халка в массиве, она будет двигать его дальше в самый конец списка:
Именно поэтому этот алгоритм называется пузырьковой сортировкой, так как в результате его работы самый большой элемент в списке оказывается в самом верху массива, а все более мелкие элементы будут смещены на одну позицию влево:
Чтобы завершить сортировку нужно будет вернуться к началу массива и повторить описанные выше пять шагов еще раз, снова перемещаясь слева направо, сравнивая и по необходимости перемещая элементы. Но на этот раз вам нужно остановить алгоритм за один элемент до конца массива, ведь мы уже знаем, что в крайней правой позиции абсолютно точно находится самый большой элемент (Халк):
Таким образом, программа должна иметь два цикла. Для большей наглядности, перед тем как мы перейдем к рассмотрению программного кода, по этой ссылке можно ознакомиться с визуализацией работы пузырьковой сортировки: Визуализация работы пузырьковой сортировки
Реализация пузырьковой сортировки на языке Java
Для демонстрации работы сортировки на Java, приведем программный код, который:- создает массив на 5 элементов;
- загружает в него рост мстителей;
- выводит на экран содержимое массива;
- реализует пузырьковую сортировку;
- осуществляет повторный вывод на экран отсортированного массива.
- into – метод вставки элементов в массив;
- printer – выводит содержимое массива построчно;
bubbleSorter – который производит основную работу и сортирует данные, хранящиеся в массиве, еще раз приведем его отдельно:
public void bubbleSorter () { //МЕТОД ПУЗЫРЬКОВОЙ СОРТИРОВКИ for (int out = elems - 1 ; out >= 1 ; out-- ) { //Внешний цикл for (int in = 0 ; in out; in++ ) { //Внутренний цикл if (a[ in] > a[ in + 1 ] ) //Если порядок элементов нарушен toSwap (in, in + 1 ) ; //вызвать метод, меняющий местами } } }
toSwap – переставляет местами элементы в случае необходимости. Для этого используется временная переменная dummy , в которую записывается значение первого числа, а на место первого записывается значение из второго числа. После этого содержимое из временной переменной записывается во второе число. Это стандартный прием перестановки местами двух элементов;
и, наконец, главный метод:
Заключение
Алгоритм пузырьковой сортировки является одним из самых медленных. Если массив состоит из N элементов, то на первом проходе будет выполнено N-1 сравнений, на втором N-2, далее N-3 и т.д. То есть всего будет произведено проходов: (N-1) + (N-2) + (N-3) + … + 1 = N x (N-1)/2 Таким образом, при сортировке алгоритм выполняет около 0.5х(N^2) сравнений. Для N = 5 , количество сравнений будет примерно 10, для N = 10 количество сравнений вырастит до 45. Таким образом, с увеличением количества элементов сложность сортировки значительно увеличивается:На скорость алгоритма влияет не только количество проходов, но и количество перестановок, которые потребуется совершить. Для случайных данных количество перестановок в среднем составляет (N^2) / 4, то есть примерно в половину меньше, чем количество проходов. Однако, в худшем случае количество перестановок также может составить N^2 / 2 – это в том случае, если данные изначально отсортированы в обратном порядке. Не смотря на то, что это достаточно медленный алгоритм сортировки, знать и понимать как он работает довольно важно, к тому же, как было сказано ранее, он является основой для более сложных алгоритмов. Jgd!
Было подсчитано, что до четверти времени централизованных компьютеров уделяется сортировке данных. Это потому, что намного легче найти значение в массиве, который был заранее отсортирован. В противном случае поиск немного походит на поиск иголки в стоге сена.
Есть программисты, которые всё рабочее время проводят в изучении и внедрении алгоритмов сортировки. Это потому, что подавляющее большинство программ в бизнесе включает в себя управление базами данных. Люди ищут информацию в базах данных всё время. Это означает, что поисковые алгоритмы очень востребованы.
Но есть одно "но". Поисковые алгоритмы работают намного быстрее с базами данных, которые уже отсортированы. В этом случае требуется только линейный поиск.
В то время как компьютеры находятся без пользователей в некоторые моменты времени, алгоритмы сортировки продолжают работать с базами данных. Снова приходят пользователи, осуществляющие поиск, а база данных уже отсортирована, исходя из той или иной цели поиска.
В этой статье приведены примеры реализации стандартных алгоритмов сортировки.
Сортировка выбором (Selection sort)
Для того, чтобы отсортировать массив в порядке возрастания, следует на каждой итерации найти элемент с наибольшим значением. С ним нужно поменять местами последний элемент. Следующий элемент с наибольшим значением становится уже на предпоследнее место. Так должно происходить, пока элементы, находящиеся на первых местах в массивe, не окажутся в надлежащем порядке.
Код C++
void
SortAlgo::selectionSort(int
data, int
lenD)
{
int
j = 0;
int
tmp = 0;
for
(int
i=0; i
Пузырьковая сортировка (Bubble sort)
При пузырьковой сортировке сравниваются соседние элементы и меняются местами, если следующий элемент меньше предыдущего. Требуется несколько проходов по данным. Во время первого прохода сраваются первые два элемента в массиве. Если они не в порядке, они меняются местами и затем сравнивается элементы в следующей паре. При том же условии они так же меняются местами. Таким образом сортировка происходит в каждом цикле пока не будет достигнут конец массива.
Код C++
void
SortAlgo::bubbleSort(int
data, int
lenD)
{
int
tmp = 0;
for
(int
i = 0;i При сортировке вставками массив разбивается на две области: упорядоченную и
и неупорядоченную. Изначально весь массив является неупорядоченной областью.
При первом проходе первый элемент из неупорядоченной области изымается и помещается
в правильном положении в упорядоченной области. На каждом проходе размер упорядоченной области возрастает на 1, а размер неупорядоченной
области сокращается на 1. Основной цикл работает в интервале от 1 до N-1. На j-й итерации элемент [i] вставлен в
правильное положение в упорядоченной области. Это сделано путем сдвига всех
элементов упорядоченной области, которые больше, чем [i], на одну позицию вправо. [i]
вставляется в интервал между теми элементами, которые меньше [i], и теми, которые больше [i]. Код C++
void
SortAlgo::insertionSort(int
data, int
lenD)
{
int
key = 0;
int
i = 0;
for
(int
j = 1;j Код C++
void
SortAlgo::mergeSort(int
data, int
lenD)
{
if
(lenD>1){
int
middle = lenD/2;
int
rem = lenD-middle;
int
* L = new int
;
int
* R = new int
;
for
(int
i=0;i Быстрая сортировка использует алгоритм "разделяй и властвуй". Она начинается с разбиения
исходного массива на две области. Эти части находятся слева и справа от отмеченного
элемента, называемого опорным. В конце процесса одна часть будет
содержать элементы меньшие, чем опорный, а другая часть будет содержать элементы больше
опорного. Код C++
void
SortAlgo::quickSort(int
* data, int const
len)
{
int const
lenD = len;
int
pivot = 0;
int
ind = lenD/2;
int
i,j = 0,k = 0;
if
(lenD>1){
int
* L = new int
;
int
* R = new int
;
pivot = data;
for
(i=0;i Сортировка пузырьком (обменная сортировка) – простой в реализации и малоэффективный алгоритм сортировки. Метод изучается одним из первых на курсе теории алгоритмов, в то время как на практике используется очень редко.
Алгоритм состоит из повторяющихся проходов по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются раз или до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает - массив отсортирован. При каждом проходе алгоритма по внутреннему циклу, очередной наибольший элемент массива ставится на своё место в конце массива рядом с предыдущим «наибольшим элементом», а наименьший элемент перемещается на одну позицию к началу массива («всплывает» до нужной позиции как пузырёк в воде, отсюда и название алгоритма).
Возьмём массив с числами «5 1 4 2 8» и отсортируем значения по возрастанию, используя сортировку пузырьком. Выделены те элементы, которые сравниваются на данном этапе.
Первый проход:
Второй проход:
Теперь массив полностью отсортирован, но алгоритм не знает так ли это. Поэтому ему необходимо сделать полный проход и определить, что перестановок элементов не было.
Третий проход:
Теперь массив отсортирован и алгоритм может быть завершён.
Реализация алгоритма на различных языках программирования:
Mov bx, offset array
mov cx, n
for_i:
dec cx
xor dx, dx
for_j:
cmp dx, cx
jae exit_for_j
jbe no_swap
mov ah, byte ptr bx
mov byte ptr bx, al
mov byte ptr bx, ah
no_swap:
inc dx
jmp for_j
exit_for_j:
loop for_i Text
# void bubble_sort (unsigned *array, unsigned length);
.globl bubble_sort
.type bubble_sort, @function
bubble_sort:
mov 8(%esp), %ecx # unsigned length
cmp $1, %ecx
jbe exit
mov 4(%esp), %eax # unsigned *array
dec %ecx
for_ecx:
xor %edi, %edi
for_edi:
mov (%eax,%edi,4), %ebx
cmp %ebx, 4(%eax,%edi,4)
jae no_xchng
mov 4(%eax,%edi,4), %edx
mov %edx, (%eax,%edi,4)
mov %ebx, 4(%eax,%edi,4)
no_xchng:
inc %edi
cmp %edi, %ecx
jne for_edi
loop for_ecx
exit:
ret
#define SWAP(A, B) { int t = A; A = B; B = t; }
void bubblesort(int *a, int n)
{
int i, j;
for (i = n - 1; i > 0; i--)
{
for (j = 0; j < i; j++)
{
if (a[j] > a)
SWAP(a[j], a);
}
}
}
#include Void bubble(int* a, int n)
{
for (int i = n - 1; i >= 0; i--)
{
for (int j = 0; j < i; j++)
{
if (a[j] > a)
{
int tmp = a[j];
a[j] = a;
a = tmp;
}
}
}
}
Void BubbleSort(int A)
{
for (int i = 0; i < A.Length; i++)
{
for (int j = i+1; j < A.Length; j++)
{
if (A[j] < A[i])
{
var temp = A[i];
A[i] = A[j];
A[j] = temp;
}
}
}
}
Сортировка одномерного динамического целочисленного массива: Type
TIntVec = array of Integer;
...
procedure BubbleSort(var a: TIntVec);
var i,p,n: Integer; b: boolean;
begin
n:= Length(a);
if n < 2 then exit;
repeat
b:= false;
Dec(n);
if n > 0 then
for i:= 0 to n-1 do
if a[i] > a then
begin
p:= a[i];
a[i]:= a;
a:= p;
b:= true;
end;
until not b;
end;
Void bubbleSort(alias op, T)(T inArray) {
foreach (i, ref a; inArray) {
foreach (ref b; inArray) {
if (mixin(op)) {
auto tmp = a;
a = b;
b = tmp;
}
}
}
}
Do i=n-1,1,-1
do j=1,i
if (a(j).gt.a(j+1)) then
t=a(j)
a(j)=a(j+1)
a(j+1)=t
endif
enddo
enddo
Void bubblesort(int arr) {
for (int i = 0; i < arr.length-1; i++){
for (int j = i+1; j < arr.length; j++){
if (arr[i] < arr[j]) {
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
}
}
}
For i:=n-1 downto 1 do {n - размер массива M}
for j:=1 to i do
if M[j]>M then
begin
tmp:= M[j];
M[j]:= M;
M:= tmp;
end;
write("вывод значений M: ");
for i:=1 to n do
write(M[i]:4);
writeln;
Усовершенствованный алгоритм сортировки пузырьком: P:=True; {есть перестановка?}
K:=1; {Номер просмотра}
While P Do
Begin
P:=false;
For i:=1 To n-k Do
If X[i] > X Then
Begin
A:=X[i];
X[i]:=X;
X:=A;
P:=true;
End;
k:=k+1;
End;
For(@out){
for(0..$N-1){
if($out[$_]gt$out[$_+1]){
($out[$_],$out[$_+1])=($out[$_+1],$out[$_]);
}
}
}
Arr =
swap = true
size = arr.length - 1
while swap
swap = false
for i in 0...size
swap |= arr[i] > arr
arr[i], arr = arr, arr[i] if arr[i] > arr
end
size -= 1
end
puts arr.join(" ")
# output => 1 3 3 5 8 10 11 12 17 20
Def swap(arr, i, j):
arr[i], arr[j] = arr[j], arr[i]
def bubble_sort(arr):
i = len(arr)
while i > 1:
for j in xrange(i - 1):
if arr[j] > arr:
swap(arr, j, j + 1)
i -= 1
Sub Sort(Mus() As Long)
Dim i As Long, tmp As Long, t As Boolean
t = True
Do While t
t = False
For i = 0 To UBound(Mus()) - 1
If Mus(i) > Mus(i + 1) Then
tmp = Mus(i)
Mus(i) = Mus(i + 1)
Mus(i + 1) = tmp
t = True
End If
Next
Loop
End Sub
$size = sizeof($arr)-1;
for ($i = $size; $i>=0; $i--) {
for ($j = 0; $j<=($i-1); $j++)
if ($arr[$j]>$arr[$j+1]) {
$k = $arr[$j];
$arr[$j] = $arr[$j+1];
$arr[$j+1] = $k;
}
}
Function sortBubble(data) {
var tmp;
for (var i = data.length - 1; i > 0; i--) {
for (var j = 0; j < i; j++) {
if (data[j] > data) {
tmp = data[j];
data[j] = data;
data = tmp;
}
}
}
return data;
}
Function bubbleSort(seq:Number):Number{
var sort = seq;
var elem:Number;
for(n in reverse ){
for(i in ){
if(sort < sort[i]){
elem = sort[i];
sort[i] = sort;
sort = elem;
}
}
}
return sort;
}
Using System.Console;
using Nemerle.Collections;
def arr = array ;
foreach (i in )
foreach (j in )
when (arr[j] > arr)
(arr[j], arr) = (arr, arr[j]);
WriteLine($"Sorted list is a $(arr.ToList())");
CLS
RANDOMIZE TIMER
DEFINT X, Y, N, I, J, D
N = 10 " 32 766 - 62.7 SEC
DIM Y[N], Y1[N], Y2[N], Y3[N], Y4[N] "FRE(-1)=21440-21456
PRINT " ZAPOLNENIE MASSIVA ELEMENTAMI"
FOR X = 1 TO N
Y[X] = X
PRINT Y[X];
NEXT X:PRINT
PRINT " PEREMESHIVANIJE ELEMENTOV MASSIVA"
PRINT " SLUCHAINYE CHISLA"
FOR X = 1 TO N
YD=Y[X]
XS=INT(RND*N)+1
PRINT XS;
Y[X]=Y
Y=YD
NEXT X:PRINT
PRINT " PEREMESHANNYJ MASSIV"
FOR X=1 TO N
PRINT Y[X];
NEXT X:PRINT
"ALGORITM "SORTIROVKA PROSTYM OBMENOM" O(N^2)
MTIMER
FOR J=1 TO N-1 STEP 1
F=0
FOR I=1 TO N-J STEP 1
"IF Y[I] > Y THEN D=Y[I]:Y[I]=Y:Y=D:F=1
IF Y[I] > Y THEN SWAP Y[I],Y:F=1
LOCATE 8,1 REM
PRINT " ANYMACIJA SORTIROVKI" REM
FOR X1=1 TO N REM ANIMATION BLOCK
PRINT Y; REM
NEXT X1:PRINT REM
DELAY .5 REM
NEXT I
IF F=0 THEN EXIT FOR
NEXT J
T1=MTIMER
PRINT " OTSORTIROVANNYJ MASSIV"
FOR X=1 TO N
PRINT Y[X];
NEXT X:PRINT
PRINT "ELAPSED TIME=";T1
Как отмечалось, алгоритм редко используется на практике, поскольку имеет низкую производительность. В лучшем случае сортировка пузырьком потребует O(n) времени, а в среднем и худшем – O(n2).
При написании статьи были использованы открытые источники сети интернет:
При работе с массивами данных не редко возникает задача их сортировки по возрастанию или убыванию, т.е. упорядочивания
. Это значит, что элементы того же массива нужно расположить строго по порядку. Например, в случае сортировки по возрастанию предшествующий элемент должен быть меньше последующего (или равен ему). Существует множество методов сортировки. Одни из них являются более эффективными, другие – проще для понимания. Достаточно простой для понимания является сортировкаметодом пузырька
, который также называют методом простого обмена
. В чем же он заключается, и почему у него такое странное название: "метод пузырька"? Как известно воздух легче воды, поэтому пузырьки воздуха всплывают. Это просто аналогия. В сортировке методом пузырька по возрастанию более легкие (с меньшим значением) элементы постепенно "всплывают" в начало массива, а более тяжелые друг за другом опускаются на дно (в конец массива). Программа на языке Паскаль: const
m =
10
;
var
arr:
array
[
1
..
m
]
of
integer
;
i,
j,
k:
integer
;
begin
randomize;
write
("Исходный массив: "
)
;
for
i :
=
1
to
m do
begin
arr[
i]
:
=
random(256
)
;
write
(arr[
i]
:
4
)
;
end
;
writeln
;
writeln
;
for
i :
=
1
to
m-
1
do
for
j :
=
1
to
m-
i do
if
arr[
j]
> arr[
j+
1
]
then
begin
k :
=
arr[
j]
;
arr[
j]
:
=
arr[
j+
1
]
;
arr[
j+
1
]
:
=
k
end
;
write
("Отсортированный массив: "
)
;
for
i :
=
1
to
m do
write
(arr[
i]
:
4
)
;
writeln
;
readln
end
.
Сортировка вставками (Insertion sort)
Сортировка слиянием (Merge sort)
Быстрая сортировка (Quick sort)
Худшее время
Лучшее время
Среднее время
Затраты памяти
Пример работы алгоритма
Синтаксис Intel
Синтаксис AT&T (GNU)
C
C++
С использованием Template
Без использования Template
C#
Delphi
D
Fortran
Java
Pascal
Perl
Ruby
Python
VBA
PHP
JavaScript
JavaFX
Nemerle
TurboBasic 1.1
Решение
Алгоритм и особенности этой сортировки таковы: