Параллельная сортировка методом пузырька на cuda
Содержание:
- Сортировка многомерного массива
- Как улучшить пузырьковую сортировку
- Идея алгоритма
- Working of Bubble Sort
- Description
- Как работает Быстрая сортировка
- Пузырьковая сортировка массива
- Объяснение:
- Complexity Analysis of Bubble Sort
- Метод пузырька
- Программа
- Optimized Bubble Sort Algorithm
- Методы списков
- Пример работы алгоритма[править]
- Скорость сортировки в Python
- Алгоритм
- Сложность алгоритма
- Implementing the Bubble Sort Algorithm
- Pseudocode
- Заключение
- Заключение
Сортировка многомерного массива
Сортировка статического многомерного массива по существу не отличается от сортировки одномерного. Можно воспользоваться тем свойством, что статический одномерный и многомерный массивы имеют одинаковое представление в памяти.
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);
}
}
}
#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void bubbleSort2d(int **a, size_t m, size_t n) {
int tmp;
size_t i, j, k, jp, ip;
size_t size = m*n;
char flag;
do {
flag = 0;
for (k = 1; k < size; k++) {
//Вычисляем индексы текущего элемента
j = k / m;
i = k - j*m;
//Вычисляем индексы предыдущего элемента
jp = (k-1) / m;
ip = (k-1) - jp*m;
if (a > a) {
tmp = a;
a = a;
a = tmp;
flag = 1;
}
}
} while(flag);
}
#define SIZE_X 3
#define SIZE_Y 4
void main() {
int **a = NULL;
int i, j;
a = (int**) malloc(sizeof(int*) * SIZE_X);
for (i = 0; i < SIZE_X; i++) {
a = (int*) malloc(sizeof(int) * SIZE_Y);
for (j = 0; j < SIZE_Y; j++) {
a = rand();
printf("%8d ", a);
}
printf("\n");
}
printf("\nafter sort\n");
bubbleSort2d(a, SIZE_X, SIZE_Y);
for (i = 0; i < SIZE_X; i++) {
for (j = 0; j < SIZE_Y; j++) {
printf("%8d ", a);
}
printf("\n");
}
for (i = 0; i < SIZE_X; i++) {
free(a);
}
free(a);
_getch();
}
Во-вторых, можно сначала переместить массив в одномерный, отсортировать одномерный массив, после чего переместить его обратно в двумерный.
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);
}
}
Если вас смущает эта функция, то воспользуйтесь типизированной. Вызов, из предыдущего примера
bubbleSort3gi2d((void**)a, sizeof(int), SIZE_X, SIZE_Y, intSort);
Q&A
Всё ещё не понятно? – пиши вопросы на ящик
Как улучшить пузырьковую сортировку
Ниже вы можете видеть оптимизированную версию пузырьковой сортировки.
for (int i = 0; i < 10; i++) {
bool flag = true;
for (int j = 0; j < 10 — (i + 1); j++) {
if (digitals > digitals) {
flag = false;
swap (digitals, digitals);
}
}
if (flag) {
break;
}
}
|
1 |
for(inti=;i<10;i++){ boolflag=true; for(intj=;j<10-(i+1);j++){ if(digitalsj>digitalsj+1){ flag=false; swap(digitalsj,digitalsj+1); } } if(flag){ break; } } |
Давайте посмотрим, что мы сделали для ее оптимизации:
- В строке 17: изменили условие внутреннего цикла на .Поэтому чтобы лишний раз не сравнивать элементы массива тратя на это время, мы решили уменьшать отрезок внутреннего цикла на 1, после каждого полного прохода внешнего цикла.
- Вы могли заметить, что если даже массив стал отсортирован (или сразу был отсортирован) алгоритм все равно продолжает сравнивать элементы.
Для этого в строке 5: чтобы пузырьковая сортировка останавливалась (когда массив уже стал отсортирован), мы объявили булеву переменную (ее обычно называют флаг или флажок). Еще при ее инициализации мы поместили значение , но она меняется на:
false, если результат условия в строке 4: положительный.
А в строке 9: чтобы мы могли выйти из алгоритма мы проверяем:
- Если булева переменная равна , значит массив уже полностью отсортирован и можно выйти. Для этого используем оператор .
- Если же значение равно , то продолжаем сортировать массив.
В строке 6: вы (возможно) увидели незнакомую функцию . Если коротко описать что она делает, то она принимает два аргумента (через запятую) и меняет их значения местами. В нашем случаи она принимает ячейки и . Мы использовали эту функцию чтобы не писать вот эти 3 строчки:
int b = digitals;
digitals = digitals;
digitals = b;
|
1 |
intb=digitalsj; digitalsj=digitalsj+1; digitalsj+1=b; |
Использовать ее необязательно, потому что она не сделает код быстрее. Но как мы сказали выше, кода станет меньше.
Идея алгоритма
Соседние элементы последовательности сравниваются между собой и, в случае необходимости, меняются местами. В качестве примера рассмотрим упорядочивание методом пузырьковой сортировки массива, количество элементов n которого равно 5: 8, 2, 4, 7, 5. В итоге должен получиться массив с элементами, располагающимися в порядке возрастания их значений.Вначале сравниваются два первых элемента последовательности: 8 и 2, так как значение первого элемента больше значения второго, т. е. 8>2, они меняются местами. Далее, сравниваются второй и третий элементы: девятка больше четверки, следовательно, элементы снова обмениваются позициями. Аналогично алгоритм продолжает выполняться до тех пор, пока все элементы массива не окажутся на своих местах. Всего для этого потребуется n*(n-1) сравнений. В частности, на данной последовательности произведено 20 сравнений и только 5 перестановок.
.
Working of Bubble Sort
Suppose we are trying to sort the elements in ascending order.
1. First Iteration (Compare and Swap)
- Starting from the first index, compare the first and the second elements.
- If the first element is greater than the second element, they are swapped.
- Now, compare the second and the third elements. Swap them if they are not in order.
- The above process goes on until the last element.
Compare the Adjacent Elements
2. Remaining Iteration
The same process goes on for the remaining iterations.
After each iteration, the largest element among the unsorted elements is placed at the end.
Put the largest element at the end
In each iteration, the comparison takes place up to the last unsorted element.
Compare the adjacent elements
The array is sorted when all the unsorted elements are placed at their correct positions.
The array is sorted if all elements are kept in the right order
Description
We can imagine that sorted numbers are bubbles, the ones with lower value are lighter than the ones with higher value, hence they ascend to the surface faster.
Bubble sort advances similarly. In every step it compares two adjacent elements and if the lower value is on the left side of the higher, bubble sort swaps them (lighter value ascends to the end of the array) and with the same logic algorithm proceeds to the next item.
After one iteration the lowest value is located at the end of the array. Algorithm now repeats the procedure with reduced array (the last element is already sorted). After iterations is the array completely sorted, because the last bubble is sorted trivially.
Как работает Быстрая сортировка
Быстрая сортировка чаще всего не сможет разделить массив на равные части. Это потому, что весь процесс зависит от того, как мы выбираем опорный элемент. Нам нужно выбрать опору так, чтобы она была примерно больше половины элементов и, следовательно, примерно меньше, чем другая половина элементов. Каким бы интуитивным ни казался этот процесс, это очень сложно сделать.
Подумайте об этом на мгновение — как бы вы выбрали адекватную опору для вашего массива? В истории быстрой сортировки было представлено много идей о том, как выбрать центральную точку — случайный выбор элемента, который не работает из-за того, что «дорогой» выбор случайного элемента не гарантирует хорошего выбора центральной точки; выбор элемента из середины; выбор медианы первого, среднего и последнего элемента; и еще более сложные рекурсивные формулы.
Самый простой подход — просто выбрать первый (или последний) элемент. По иронии судьбы, это приводит к быстрой сортировке на уже отсортированных (или почти отсортированных) массивах.
Именно так большинство людей выбирают реализацию быстрой сортировки, и, так как это просто и этот способ выбора опоры является очень эффективной операцией, и это именно то, что мы будем делать.
Теперь, когда мы выбрали опорный элемент — что нам с ним делать? Опять же, есть несколько способов сделать само разбиение. У нас будет «указатель» на нашу опору, указатель на «меньшие» элементы и указатель на «более крупные» элементы.
Цель состоит в том, чтобы переместить элементы так, чтобы все элементы, меньшие, чем опора, находились слева от него, а все более крупные элементы были справа от него. Меньшие и большие элементы не обязательно будут отсортированы, мы просто хотим, чтобы они находились на правильной стороне оси. Затем мы рекурсивно проходим левую и правую сторону оси.
Рассмотрим пошагово то, что мы планируем сделать, это поможет проиллюстрировать весь процесс. Пусть у нас будет следующий список.
29 | 99 (low),27,41,66,28,44,78,87,19,31,76,58,88,83,97,12,21,44 (high)
Выберем первый элемент как опору 29), а указатель на меньшие элементы (называемый «low») будет следующим элементом, указатель на более крупные элементы (называемый «high») станем последний элемент в списке.
29 | 99 (low),27,41,66,28,44,78,87,19,31,76,58,88,83,97,12,21 (high),44
Мы двигаемся в сторону high то есть влево, пока не найдем значение, которое ниже нашего опорного элемента.
29 | 99 (low),27,41,66,28,44,78,87,19,31,76,58,88,83,97,12,21 (high),44
- Теперь, когда наш элемент high указывает на элемент 21, то есть на значение меньше чем опорное значение, мы хотим найти значение в начале массива, с которым мы можем поменять его местами. Нет смысла менять местами значение, которое меньше, чем опорное значение, поэтому, если low указывает на меньший элемент, мы пытаемся найти тот, который будет больше.
- Мы перемещаем переменную low вправо, пока не найдем элемент больше, чем опорное значение. К счастью, low уже имеет значение 89.
- Мы меняем местами low и high:
29 | 21 (low),27,41,66,28,44,78,87,19,31,76,58,88,83,97,12,99 (high),44
- Сразу после этого мы перемещает high влево и low вправо (поскольку 21 и 89 теперь на своих местах)
- Опять же, мы двигаемся high влево, пока не достигнем значения, меньшего, чем опорное значение, и мы сразу находим — 12
- Теперь мы ищем значение больше, чем опорное значение, двигая low вправо, и находим такое значение 41
Этот процесс продолжается до тех пор, пока указатели low и high наконец не встретятся в одном элементе:
29 | 21,27,12,19,28 (low/high),44,78,87,66,31,76,58,88,83,97,41,99,44
Мы больше не используем это опорное значение, поэтому остается только поменять опорную точку и high, и мы закончили с этим рекурсивным шагом:
28,21,27,12,19,29,44,78,87,66,31,76,58,88,83,97,41,99,44
Как видите, мы достигли того, что все значения, меньшие 29, теперь слева от 29, а все значения больше 29 справа.
Затем алгоритм делает то же самое для коллекции 28,21,27,12,19 (левая сторона) и 44,78,87,66,31,76,58,88,83,97,41,99,44 (правая сторона). И так далее.
Пузырьковая сортировка массива
Задача стоит следующем образом нам необходимо рассортировать какой то неопределенный массив в порядке возрастания. Сделать можно это применяя пузырьковую сортировку массива. Начинаем сортировку мы с самого начала нашей имеющийся последовательности, и постепенно шаг за шагом сравниваем последовательно каких либо два числа. Сравниваются два числа — правое и левое. Если левое число меньше правого то они меняются местами, В другом случае они остаются на своих местах и алгоритм продолжает перебирать цифры дальше, прямо как танцоры в видео, (обязательно посмотрите, там очень наглядно показано как работает такого рода пузырьковая сортировка)
Объяснение:
функция shell_sort ():
- Эта функция принимает список и его размер в качестве параметров
- Интервал ‘h’ is инициализируется до половины размера списка
- Теперь выполните следующие действия, пока значение h не станет меньше нуляПовторите список от h до конца, Храните каждый элемент во временной переменнойСравните элементы, находящиеся на интервале h, и при необходимости поменяйте местами
- Повторите форму списка h до конца
- Храните каждый элемент во временной переменной
- Сравните элементы, находящиеся на интервале h, и при необходимости поменяйте местами
Наконец, значение h обновляется, и процесс продолжается до тех пор, пока список не будет полностью отсортирован
Complexity Analysis of Bubble Sort
There are three types of Complexity are:
1) Sort complexity
The sort complexity is used to express the amount of execution times and space that it takes to sort the list. The bubble sort makes (n – 1) iterations to sort the list where n is the total number of elements in the list.
2) Time complexity
The time complexity of the bubble sort is O(n2)
The time complexities can be categorized as:
- Worst case – this is where the list provided is in descending order. The algorithm performs the maximum number of executions which is expressed as O(n2)
- Best case – this occurs when the provided list is already sorted. The algorithm performs the minimum number of executions which is expressed as ?(n)
- Average case – this occurs when the list is in random order. The average Complexity is represented as ?(n2)
3) Space complexity
The space complexity measures the amount of extra space that is needed for sorting the list. The bubble sort only requires one (1) extra space for the temporal variable used for swapping values. Therefore, it has a space complexity of O (1).
Summary
- The bubble sort algorithm works by comparing two adjacent values and swapping them if the value on the left is less than the value on the right.
- Implementing a bubble sort algorithm is relatively straight forward with Python. All you need to use are for loops and if statements.
- The problem that the bubble sort algorithm solves is taking a random list of items and turning it into an ordered list.
- The bubble sort algorithm in data structure performs best when the list is already sorted as it performs a minimal number of iterations.
- The bubble sort algorithm does not perform well when the list is in reverse order.
- The bubbler sort has a time complexity of O (n2) and a space complexity of O (1)
- The bubbler sort algorithm is best suited for academic purposes and not real-world applications.
- The optimized bubble sort makes the algorithm more efficient by skipping unnecessary iterations when checking values that have already been sorted.
Метод пузырька
Сортировка пузырьком в основном применяется в учебных проектах. В реальной практике её заменяют более эффективные алгоритмы, однако сортировка пузырьком лежит в основе некоторых из них.
В общем случае алгоритм сортировки пузырьком следующий:
- Сравнить текущий элемент со следующим.
- Если следующий элемент меньше/больше текущего, поменять их местами.
- Если массив отсортирован, закончить алгоритм, иначе перейти на шаг 1.
В алгоритме используется два цикла: основной и вложенный. В результате одного прохода вложенного цикла наибольший элемент помещается в конец массива, а наименьший смещается на одну позицию ближе к началу.
Внешний цикл в худшем случае совершает N (кол-во элементов) — 1 проходов, то есть внутренний цикл выполняется N-1 раз.
Таким образом, в каждом проходе совершается серия обменов элементов так, что наибольший элемент передвигается в конец массив перед элементом, который переместился туда в прошлой итерации. Процесс происходит до тех пор, пока массив не будет отсортирован.
Если рассмотреть реализацию алгоритма, то можно легко заметить, что время его работы (количество операций) значительно возрастает с увеличением количества элементов сортируемой последовательности.
Программа
Программа, в которой сначала необходимо ввести размер одномерного массива, после чего массив заполняется случайными числами и сортируется методом пузырька
// bu_sort.cpp: определяет точку входа для консольного приложения.
1 #include "stdafx.h"
2 #include <iostream>
3 using std::cout;
4 using std::cin;
5 using std::endl;
6
7 const int n = 100;
8
9 void Swap(int &x,int &y)
10 {
11 x = x + y;
12 y = x - y;
13 x = x - y;
14 }
15
16 void Bubble_Sort(int *a, int LeanghtArray)
17 {
18 for (int i = 1; i < LeanghtArray-1; ++i){
19 for (int i2 = 1; i2 < LeanghtArray-1; ++i2){
20 if (ai2 > ai2+1]){
21 Swap(ai2], ai2+1]);
22 }
23 }
24 }
25 }
26
27
28 int _tmain(int argc, _TCHAR* argv[])
29 {
30 int an], a1n], i, i2;
31 for (int i = 1; i < n; i++){ ai = rand(); a1i = ai]; }
32
33 Bubble_Sort(a, n);
34
35 for (int i = 1; i < n; i++){ cout << ai <<" "<<a1i<<endl; }
36 cin >> i;
37 return ;
38 }
Optimized Bubble Sort Algorithm
To optimize our bubble sort algorithm, we can introduce a to monitor whether elements are getting swapped inside the inner loop.
Hence, in the inner loop, we check whether swapping of elements is taking place or not, everytime.
If for a particular iteration, no swapping took place, it means the array has been sorted and we can jump out of the loop, instead of executing all the iterations.
Let’s consider an array with values
Below, we have a pictorial representation of how the optimized bubble sort will sort the given array.
As we can see, in the first iteration, swapping took place, hence we updated our value to , as a result, the execution enters the loop again. But in the second iteration, no swapping will occur, hence the value of will remain , and execution will break out of loop.
In the above code, in the function , if for a single complete cycle of iteration(inner loop), no swapping takes place, then will remain and then we will break out of the loops, because the array has already been sorted.
Методы списков
Давайте теперь
предположим, что у нас имеется список из чисел:
a = 1, -54, 3, 23, 43, -45,
и мы хотим в
конец этого списка добавить значение. Это можно сделать с помощью метода:
a.append(100)
И обратите
внимание: метод append ничего не возвращает, то есть, он меняет
сам список благодаря тому, что он относится к изменяемому типу данных. Поэтому
писать здесь конструкцию типа
a = a.append(100)
категорически не
следует, так мы только потеряем весь наш список! И этим методы списков
отличаются от методов строк, когда мы записывали:
string="Hello" string = string.upper()
Здесь метод upper возвращает
измененную строку, поэтому все работает как и ожидается. А метод append ничего не
возвращает, и присваивать значение None переменной a не имеет
смысла, тем более, что все работает и так:
a = 1, -54, 3, 23, 43, -45, a.append(100)
Причем, мы в методе
append можем записать
не только число, но и другой тип данных, например, строку:
a.append("hello")
тогда в конец
списка будет добавлен этот элемент. Или, булевое значение:
a.append(True)
Или еще один
список:
a.append(1,2,3)
И так далее. Главное,
чтобы было указано одно конкретное значение. Вот так работать не будет:
a.append(1,2)
Если нам нужно
вставить элемент в произвольную позицию, то используется метод
a.insert(3, -1000)
Здесь мы
указываем индекс вставляемого элемента и далее значение самого элемента.
Следующий метод remove удаляет элемент
по значению:
a.remove(True)
a.remove('hello')
Он находит
первый подходящий элемент и удаляет его, остальные не трогает. Если же
указывается несуществующий элемент:
a.remove('hello2')
то возникает
ошибка. Еще один метод для удаления
a.pop()
выполняет
удаление последнего элемента и при этом, возвращает его значение. В самом
списке последний элемент пропадает. То есть, с помощью этого метода можно
сохранять удаленный элемент в какой-либо переменной:
end = a.pop()
Также в этом
методе можно указывать индекс удаляемого элемента, например:
a.pop(3)
Если нам нужно
очистить весь список – удалить все элементы, то можно воспользоваться методом:
a.clear()
Получим пустой
список. Следующий метод
a = 1, -54, 3, 23, 43, -45, c = a.copy()
возвращает копию
списка. Это эквивалентно конструкции:
c = list(a)
В этом можно
убедиться так:
c1 = 1
и список c будет отличаться
от списка a.
Следующий метод count позволяет найти
число элементов с указанным значением:
c.count(1) c.count(-45)
Если же нам
нужен индекс определенного значения, то для этого используется метод index:
c.index(-45) c.index(1)
возвратит 0,
т.к. берется индекс только первого найденного элемента. Но, мы здесь можем
указать стартовое значение для поиска:
c.index(1, 1)
Здесь поиск
будет начинаться с индекса 1, то есть, со второго элемента. Или, так:
c.index(23, 1, 5)
Ищем число 23 с
1-го индекса и по 5-й не включая его. Если элемент не находится
c.index(23, 1, 3)
то метод
приводит к ошибке. Чтобы этого избежать в своих программах, можно вначале
проверить: существует ли такой элемент в нашем срезе:
23 in c1:3
и при значении True далее уже
определять индекс этого элемента.
Следующий метод
c.reverse()
меняет порядок
следования элементов на обратный.
Последний метод,
который мы рассмотрим, это
c.sort()
выполняет
сортировку элементов списка по возрастанию. Для сортировки по убыванию, следует
этот метод записать так:
c.sort(reverse=True)
Причем, этот
метод работает и со строками:
lst = "Москва", "Санкт-Петербург", "Тверь", "Казань" lst.sort()
Здесь
используется лексикографическое сравнение, о котором мы говорили, когда
рассматривали строки.
Это все основные
методы списков и чтобы вам было проще ориентироваться, приведу следующую
таблицу:
|
Метод |
Описание |
|
append() |
Добавляет |
|
insert() |
Вставляет |
|
remove() |
Удаляет |
|
pop() |
Удаляет |
|
clear() |
Очищает |
|
copy() |
Возвращает |
|
count() |
Возвращает |
|
index() |
Возвращает |
|
reverse() |
Меняет |
|
sort() |
Сортирует |
Пример работы алгоритма[править]
Возьмём массив и отсортируем значения по возрастанию, используя сортировку пузырьком. Выделены те элементы, которые сравниваются на данном этапе.
Первый проход:
| До | После | Описание шага |
|---|---|---|
| 5 1 4 2 8 | 1 5 4 2 8 | Здесь алгоритм сравнивает два первых элемента и меняет их местами. |
| 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 |
Теперь массив полностью отсортирован, но неоптимизированный алгоритм проведет еще два прохода, на которых ничего не изменится, в отличие от алгоритма, использующего вторую оптимизацию, который сделает один проход и прекратит свою работу, так как не сделает за этот проход ни одного обмена.
Скорость сортировки в Python
Python
# speed/main.py
import random
from boxx import timeit
def list_sort(arr):
return arr.sort()
def sorted_builtin(arr):
return sorted(arr)
def main():
arr =
with timeit(name=»sorted(list)»):
sorted_builtin(arr)
with timeit(name=»list.sort()»):
list_sort(arr)
if __name__ == «__main__»:
main()
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
# speed/main.py importrandom fromboxx importtimeit deflist_sort(arr) returnarr.sort() defsorted_builtin(arr) returnsorted(arr) defmain() arr=random.randint(,50)forrinrange(1_000_000) withtimeit(name=»sorted(list)») sorted_builtin(arr) withtimeit(name=»list.sort()») list_sort(arr) if__name__==»__main__» main() |
Указанный выше код выводит следующий результат:
Shell
$ python main.py
«sorted(list)» spend time: 0.1104379
«list.sort()» spend time: 0.0956471
|
1 2 3 |
$python main.py «sorted(list)»spend time0.1104379 «list.sort()»spend time0.0956471 |
Как видите, метод немного быстрее, чем функция . Почему так получается? Разберем обе функции и посмотрим, сможет ли байтовый код дать ответ:
Python
>>> import dis
>>> dis.dis(list_sort)
12 0 LOAD_FAST 0 (arr)
2 LOAD_METHOD 0 (sort)
4 CALL_METHOD 0
6 RETURN_VALUE
>>> dis.dis(sorted_builtin)
16 0 LOAD_GLOBAL 0 (sorted)
2 LOAD_FAST 0 (arr)
4 CALL_FUNCTION 1
6 RETURN_VALUE
|
1 2 3 4 5 6 7 8 9 10 11 |
>>>importdis >>>dis.dis(list_sort) 12LOAD_FAST(arr) 2LOAD_METHOD(sort) 4CALL_METHOD 6RETURN_VALUE >>>dis.dis(sorted_builtin) 16LOAD_GLOBAL(sorted) 2LOAD_FAST(arr) 4CALL_FUNCTION1 6RETURN_VALUE |
Байтовый код обеих функций практически идентичен. Единственное различие в том, что функция сначала загружает список, и за методом (sort) следует вызванный метод списка без аргументов. Если сравнить, функция сначала загружает встроенную функцию , а за ней следует список и вызов загруженной функции со списком в качестве аргумента.
Почему же временные результаты отличаются?
Можно предположить, что в то время как может работать с известным размером и менять элементы внутри данного размера, должен работать c неизвестным размером. Следовательно, если при добавлении нового элемента не хватает памяти, нужно изменить размер нового списка, созданного через . На это требуется время! Если просмотреть исходный код CPython, можно найти следующий комментарий об изменении размера списка объектов:
Помните, что сейчас мы работаем со списком из 1 000 000 элементов — изменений размера будет довольно много! К несчастью, пока что это лучший ответ на вопрос, почему на 13% быстрее, чем .
Python
new_array = arr.copy()
arr.sort()
|
1 2 |
new_array=arr.copy() arr.sort() |
Имплементация приводит к разнице во времени выполнения, поскольку создание копии списка занимает некоторое время.
Алгоритм
Алгоритм состоит из повторяющихся проходов по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются N−1{\displaystyle N-1} раз или до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован. При каждом проходе алгоритма по внутреннему циклу, очередной наибольший элемент массива ставится на своё место в конце массива рядом с предыдущим «наибольшим элементом», а наименьший элемент перемещается на одну позицию к началу массива («всплывает» до нужной позиции, как пузырёк в воде. Отсюда и название алгоритма).
Сложность алгоритма
Сложность алгоритма позволяет дать ему оценку по времени выполнения, то есть определяет его эффективность. Можно выражать сложность по-разному, но чаще всего используется асимптотическая сложность, которая определяет его эффективность при стремлении входных данных к бесконечности.
Точное время выполнения алгоритма не рассматривается, потому что оно зависит слишком от многих факторов: мощность процессора, тип данных массива, используемый язык программирования.
Алгоритм сортировки пузырьком имеет сложность , где – количество элементов массива. Из формулы видно, что сложность сортировки пузырьком квадратично зависит от количества сортируемых элементов. Это значит, что он неэффективен при работе с большими массивами данных.
Следует понимать, что с помощью асимптотической функции нельзя точно вычислить время работы алгоритма. Например, дана последовательность «6 5 4 3 2 1», для её сортировки придется сделать максимальное количество проходов. Такой случай называют наихудшим. Если дана последовательность «3 1 2 4 5», то количество проходов будет минимально, соответственно сортировка пройдет гораздо быстрее. Если же дан уже отсортированный массив, то алгоритму сортировки и вовсе не нужно совершать проходов. Это называется наилучшим случаем.
Implementing the Bubble Sort Algorithm
We will breakdown the implementation into three (3) steps, namely the problem, the solution, and the algorithm that we can use to write code for any language.
The problem
A list of items is given in random order, and we would like to arrange the items in an orderly manner
Consider the following list:
The solution
Iterate through the list comparing two adjacent elements and swapping them if the first value is higher than the second value.
The result should be as follows:
Algorithm
The bubble sort algorithm works as follows
Step 1) Get the total number of elements. Get the total number of items in the given list
Step 2) Determine the number of outer passes (n — 1) to be done. Its length is list minus one
Step 3) Perform inner passes (n — 1) times for outer pass 1. Get the first element value and compare it with the second value. If the second value is less than the first value, then swap the positions
Step 4) Repeat step 3 passes until you reach the outer pass (n — 1). Get the next element in the list then repeat the process that was performed in step 3 until all the values have been placed in their correct ascending order.
Step 5) Return the result when all passes have been done. Return the results of the sorted list
Step 6) Optimize Algorithm
Avoid unnecessary inner passes if the list or adjacent values are already sorted. For example, if the provided list already contains elements that have been sorted in ascending order, then we can break the loop early.
Pseudocode
We observe in algorithm that Bubble Sort compares each pair of array element unless the whole array is completely sorted in an ascending order. This may cause a few complexity issues like what if the array needs no more swapping as all the elements are already ascending.
To ease-out the issue, we use one flag variable swapped which will help us see if any swap has happened or not. If no swap has occurred, i.e. the array requires no more processing to be sorted, it will come out of the loop.
Pseudocode of BubbleSort algorithm can be written as follows −
procedure bubbleSort( list : array of items )
loop = list.count;
for i = 0 to loop-1 do:
swapped = false
for j = 0 to loop-1 do:
/* compare the adjacent elements */
if list > list then
/* swap them */
swap( list, list )
swapped = true
end if
end for
/*if no number was swapped that means
array is sorted now, break the loop.*/
if(not swapped) then
break
end if
end for
end procedure return list
Заключение
В этом уроке мы изучали, что такое сортировка и где он используется, то мы узнали, как Bubble Sort работает, мы придумали алгоритм и реализовали пузырь в Python.
Bubble Sort – один из многих сортировковных алгоритмов, и он далеко от лучшего, но это очень легко реализовать. Причина, по которой она не используется слишком часто, так это то, что у него сложность O (n 2 ), что означает, что количество элементов в списке удвоилось, время, необходимое для сортировки их использования этого алгоритма, увеличится в четыре раза.
Таким образом, для очень большого количества данных этот алгоритм становится неэффективным. Тем не менее, зная пузырь, как программист важен, и я надеюсь, что вы узнали что-то.
Заключение
Как мы уже упоминали ранее, эффективность быстрой сортировки сильно зависит от выбора точки опоры — он может «упростить или усложнить» сложность алгоритма во времени (и в пространстве стека). Нестабильность алгоритма также может стать препятствием для использования с пользовательскими объектами.
Тем не менее, несмотря на все это, средняя сложность времени O(n*logn) в быстрой сортировки, а также его относительно небольшое потребление памяти и простая реализация делают его очень эффективным и популярным алгоритмом.
Источники используемые для написания статьи: Olivera Popović — Quicksort in Pythonhttps://stackoverflow.com/questions/18262306/quicksort-with-pythonhttps://www.geeksforgeeks.org/python-program-for-quicksort/
Spread the love
