Пузырьковый метод сортировки

Теги: Сортировка пузырьком си, си пузырьковая сортировка, сортировка пузырьком двумерного массива

Сортировка пузырьком

Идея алгоритма очень простая. Идём по массиву чисел и проверяем порядок (следующее число должно быть больше и равно предыдущему), как только наткнулись на нарушение порядка, тут же обмениваем местами элементы, доходим до конца массива, после чего начинаем сначала.

Отсортируем массив {1, 5, 2, 7, 6, 3}
Идём по массиву, проверяем первое число и второе, они идут в порядке возрастания. Далее идёт нарушение порядка, меняем местами эти элементы

Продолжаем идти по массиву, 7 больше 5, а вот 6 меньше, так что обмениваем из местами

3 нарушает порядок, меняем местами с 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[j-1]) { tmp = a[j]; a[j] = a[j-1]; a[j-1] = tmp; } } } }

Этот алгоритм всегда будет делать (n-1)2 шагов, независимо от входных данных. Даже если массив отсортирован, всё равно он будет пройден (n-1)2 раз. Более того, будут в очередной раз проверены уже отсортированные данные.

Пусть нужно отсортировать массив 1, 2, 4, 3

После того, как были поменяны местами элемента a[2] и a[3] нет больше необходимости проходить этот участок массива. Примем это во внимание и переделаем алгоритм

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[j-1]) { tmp = a[j]; a[j] = a[j-1]; a[j-1] = 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[j-1]) { tmp = a[j]; a[j] = a[j-1]; a[j-1] = 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[i-1]) { tmp = a[i]; a[i] = a[i-1]; a[i-1] = tmp; flag = 1; } } } while (flag); }

В этом случае сложность также порядка n2, но в случае отсортированного массива будет всего один проход.

Теперь усовершенствуем алгоритм. Напишем функцию общего вида, чтобы она сортировала массив типа 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[10] = {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[3][3] = {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 <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[i][j] > a[ip][jp]) { tmp = a[i][j]; a[i][j] = a[ip][jp]; a[ip][jp] = 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[i] = (int*) malloc(sizeof(int) * SIZE_Y); for (j = 0; j < SIZE_Y; j++) { a[i][j] = rand(); printf(«%8d «, a[i][j]); } 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[i][j]); } printf(«\n»); } for (i = 0; i < SIZE_X; i++) { free(a[i]); } 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);

ru-Cyrl18-tutorialSypachev S.S.1989-04-14sypachev_s_s@mail.ruStepanSypachevstudents

Q&A

Сортировка массива очень типичная задача на работу с массивами, наверное каждому (или почти каждому) прийдет сразу идея отсортировать массив простым перебором. Если это не так, то специально для вас мы добавили в пост видео, на котором Румынский ансамбль обыгрывает различные сортировки массива. Но в этой статье мы рассмотрим не только самый примитивный метод, доступный рядовому выпускнику ПТУ, но и довольно сложные алгоримы.


Сортировка пузырьком (Bubble sort)

Подробно пузырьку, больший элемент массива поднимается «вверх».

Описание алгоритма

Алгоритм состоит из повторяющихся проходов по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются N-1 раз или до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован. При каждом проходе алгоритма по внутреннему циклу, очередной наибольший элемент массива ставится на своё место в конце массива рядом с предыдущим «наибольшим элементом», а наименьший элемент перемещается на одну позицию к началу массива («всплывает» до нужной позиции как пузырёк в воде, отсюда и название алгоритма).

Реализация

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[j+1]) { int tmp = a[j]; a[j] = a[j+1]; a[j+1] = tmp; } } } }

.cpp.pas.py

Анализ алгоритма

Теоретическая оценка

Вывод

Метод пузырька оказывается крайне неэффективным на любом входном наборе данных.

Сортировка пузырьком

Единственный плюс алгоритма — простота его исполнения.


Сортировка вставками (Insertion sort)

Выбираем и вставляем элемент в нужную позицию.

Описание алгоритма

На каждом шаге алгоритма мы выбираем один из элементов входных данных и вставляем его на нужную позицию в уже отсортированном списке, до тех пор, пока набор входных данных не будет исчерпан. Метод выбора очередного элемента из исходного массива произволен; может использоваться практически любой алгоритм выбора. Обычно (и с целью получения устойчивого алгоритма сортировки), элементы вставляются по порядку их появления во входном массиве. Приведенный ниже алгоритм использует именно эту стратегию выбора.

Реализация

void insert_sort(int *a, int n) { int i, j, value; for(i = 1; i < n; i++) { value = a[i]; for (j = i — 1; j >= 0 && a[j] > value; j—) { a[j + 1] = a[j]; } a[j + 1] = value; } }

.cpp.pas.py

Анализ алгоритма

Теоретическая оценка

Вывод

Метод оказывается эффективным только на маленьких массивах (не более 10), на массивах больших размеров, в силу асимптотической сложности n^2, алгоритм оказывается крайне не эффективным.


Сортировка выбором (Selection sort)

Упорядочиваем постепенно массив, заполняя первую позицию неупорядоченной части минимальным элементом из неупорядоченной части.

Описание алгоритма

Шаги алгоритма: находим номер минимального значения в текущем списке, производим обмен этого значения со значением первой неотсортированной позиции (обмен не нужен, если минимальный элемент уже находится на данной позиции), теперь сортируем хвост списка, исключив из рассмотрения уже отсортированные элементы. Для реализации устойчивости алгоритма необходимо в пункте 2 минимальный элемент непосредственно вставлять в первую неотсортированную позицию, не меняя порядок остальных элементов.

Реализация

void select_sort(int *a, int length){ for (int i = 0; i < length - 1; i++) { /* устанавливаем начальное значение минимального индекса */ int min_i = i; /* находим индекс минимального элемента */ for (int j = i + 1; j < length; j++) { if (a[j] < a[min_i]) { min_i = j; } } /* меняем значения местами */ int temp = array[i]; array[i] = array[min_i]; array[min_i] = temp; } }

.cpp.pas.py

Анализ алгоритма

Теоретическая оценка

Вывод

Метод оказывается эффективным только на маленьких массивах (не более 10), на массивах больших размеров, в силу асимптотической сложности n^2, алгоритм оказывается крайне не эффективным.


Сортировка слиянием (Merge sort)

Упорядочиваем списки (или другие структуры данных, доступ к элементам которых можно получать только последовательно, например — потоки) в определённом порядке.

Описание алгоритма

Для решения задачи сортировки эти три этапа выглядят так: 1) Сортируемый массив разбивается на две части примерно одинакового размера; 2) Каждая из получившихся частей сортируется отдельно, например — тем же самым алгоритмом; 3) Два упорядоченных массива половинного размера соединяются в один. 1.1. — 2.1. Рекурсивное разбиение задачи на меньшие происходит до тех пор, пока размер массива не достигнет единицы (любой массив длины 1 можно считать упорядоченным). 3.1. Соединение двух упорядоченных массивов в один. Основную идею слияния двух отсортированных массивов можно объяснить на следующем примере. Пусть мы имеем два подмассива.

Пусть также, элементы подмассивов в каждом из этих подмассивов отсортированы по возрастанию. Тогда: 3.2. Слияние двух подмассивов в третий результирующий массив. На каждом шаге мы берём меньший из двух первых элементов подмассивов и записываем его в результирующий массив. Счетчики номеров элементов результирующего массива и подмассива из которого был взят элемент увеличиваем на 1.3. «Прицепление» остатка. Когда один из подмассивов закончился, мы добавляем все оставшиеся элементы второго подмассива в результирующий массив.

Реализация

void merge(int *a, int low, int mid, int high) { // Variables declaration. int *b = new int[high+1-low]; int h,i,j,k; h=low; i=0; j=mid+1; // Merges the two array’s into b[] until the first one is finish while((h<=mid)&&(j<=high)) { if(a[h]<=a[j]) { b[i]=a[h]; h++; } else { b[i]=a[j]; j++; } i++; } // Completes the array filling in it the missing values if(h>mid) { for(k=j;k<=high;k++) { b[i]=a[k]; i++; } } else { for(k=h;k<=mid;k++) { b[i]=a[k]; i++; } } // Prints into the original array for(k=0;k<=high-low;k++) { a[k+low]=b[k]; } delete[] b; } void merge_sort(int *a, int low, int high) {// Recursive sort … int mid; if(low<high) { mid=(low+high)/2; merge_sort(a, low,mid); merge_sort(a, mid+1,high); merge(a, low,mid,high); } }

.cpp.pas.py

Анализ алгоритма

Теоретическая оценка

Вывод

Метод оказывается крайне эффективным, однако требуется выделение дополнительной памяти.


Быстрая сортировка (Quicksort)

QuickSort является существенно улучшенным вариантом алгоритма сортировки с помощью прямого обмена (его варианты известны как «Пузырьковая сортировка» и «Шейкерная сортировка»), известного, в том числе, своей низкой эффективностью.

Принципиальное отличие состоит в том, что в первую очередь производятся перестановки на наибольшем возможном расстоянии и после каждого прохода элементы делятся на две независимые группы. Любопытный факт: улучшение самого неэффективного прямого метода сортировки дало в результате один из наиболее эффективных улучшенных методов.

Описание алгоритма

Быстрая сортировка использует стратегию «разделяй и властвуй». Шаги алгоритма таковы:

  1. Выбираем в массиве некоторый элемент, который будем называть опорным элементом. С точки зрения корректности алгоритма выбор опорного элемента безразличен. С точки зрения повышения эффективности алгоритма выбираться должна медиана, но без дополнительных сведений о сортируемых данных её обычно невозможно получить. Известные стратегии: выбирать постоянно один и тот же элемент, например, средний или последний по положению; выбирать элемент со случайно выбранным индексом.
  2. Операция разделения массива: реорганизуем массив таким образом, чтобы все элементы со значением меньшим или равным опорному элементу, оказались слева от него, а все элементы, превышающие по значению опорный — справа от него. Обычный алгоритм операции:
    1. Два индекса — l и r, приравниваются к минимальному и максимальному индексу разделяемого массива, соответственно.
    2. Вычисляется индекс опорного элемента m.
    3. Индекс l последовательно увеличивается до тех пор, пока l-й элемент не окажется больше либо равен опорному.
    4. Индекс r последовательно уменьшается до тех пор, пока r-й элемент не окажется меньше либо равен опорному.
    5. Если r = l — найдена середина массива — операция разделения закончена, оба индекса указывают на опорный элемент.
    6. Если l < r — найденную пару элементов нужно обменять местами и продолжить операцию разделения с тех значений l и r, которые были достигнуты. Следует учесть, что если какая-либо граница (l или r) дошла до опорного элемента, то при обмене значение m изменяется на r-й или l-й элемент соответственно, изменяется именно индекс опорного элемента и алгоритм продолжает свое выполнение.
  3. Рекурсивно упорядочиваем подмассивы, лежащие слева и справа от опорного элемента.
  4. Базой рекурсии являются наборы, состоящие из одного или двух элементов. Первый возвращается в исходном виде, во втором, при необходимости, сортировка сводится к перестановке двух элементов. Все такие отрезки уже упорядочены в процессе разделения.

Поскольку в каждой итерации (на каждом следующем уровне рекурсии) длина обрабатываемого отрезка массива уменьшается, по меньшей мере, на единицу, терминальная ветвь рекурсии будет достигнута обязательно и обработка гарантированно завершится.

Реализация

void quicksort(int* a, int first, int last) { int i = first, j = last, x = a[(first + last) / 2]; do { while (a[i] < x) i++; while (a[j] > x) j—; if(i <= j) { if (i < j) swap(a[i], a[j]); i++; j—; } } while (i <= j); if (i < last) quicksort(a, i, last); if (first < j) quicksort(a, first,j); }

.cpp.pas.py

Анализ алгоритма

Теоретическая оценка

Вывод

Метод показывает высокую эффективноть, при этом он не требует расходов на дополнительную память.

Однако, в худшем случае алгоритм оказывается крайне медленным (O(n2)).


Источники:

  • «The Art of Computer Programming, vol.3. Sorting and Searching,» 2-ed Donald E. Knuth
  • «Introduction to Algorithms» Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein
  • «An Introduction to the Analysis of Algorithms» Robert Sedgewick, Phillipe Flajolet.

↑ Расскажите друзьям о статье


Comments system Cackle

Сортировки массивов. Шейкерная сортировка

⇐ Предыдущая45678910111213Следующая ⇒

Задача сортировки

Задача сорт заключаются в упорядочении элементов массива.

 

Шейкерная сортировка широко используется в тех случаях, когда известно, что элементы почти упорядочены

Шейкер сортировка принимает во внимания тот факт, что от последней перестановки до конца (начала) массива находятся отсортированные элементы. Учитывая данный факт, просмотр осуществляется не до конца (начала) массива, а до конкретной позиции. Поэтому при использовании Шейкер сортировки необходимо запоминать индекс последней перестановки. На следующем шаге цикла начнём просмотр с последней перестановки. Просмотр массива осуществляется слева направо (устанавливается правая граница). Затем справа налево (устанавливается левая граница).

Сортировка прямым обменом (метод «пузырька»)

Просмотр массива осуществляется до тех пор, пока все элементы не встанут в порядке возрастания (убывания).

Предположим, мы упорядочиваем массив в порядке возрастания. После первого прохода "Пузырьком", самый большой элемент массива встанет на свое место. Выполним второй проход наоборот, от предпоследнего элемента до первого. После этого прохода встанет на свое место самый маленький элемент. Так и будем выполнять наши проходы массива: нечетные слева — направо и четные справа — налево. При этом на нечетных проходах будет занимать свое место самый большой элемент (из оставшихся), а при нечетных самый маленький (также из оставшихся).

Сравниваем 33 с 7. Меняем местами элементы и сохраняем позицию перестановки. Массив равен 7,33,15,11,0,4,25,-1.
Сравниваем 33 с 15. Меняем местами элементы и сохраняем позицию перестановки. Массив равен 7,15,33,11,0,4,25,-1.
Сравниваем 33 с 11. Меняем местами элементы и сохраняем позицию перестановки. Массив равен 7,15,11,33,0,4,25,-1.
Сравниваем 33 с 0. Меняем местами элементы и сохраняем позицию перестановки. Массив равен 7,15,11,0,33,4,25,-1 и т.д.
Сравниваем 33 с -1. Меняем местами элементы и сохраняем позицию перестановки. Массив равен 7,15,11,0,4,25,-1,33. Затем меняем направление просмотра и продолжаем процесс.
Сравниваем 25 с -1.

. Меняем местами элементы и сохраняем позицию перестановки. Массив равен 7,15,11,0,4,-1,25,33.
Сравниваем 4 с -1. . Меняем местами элементы и сохраняем позицию перестановки. Массив равен 7,15,11,0,-1,4,25,33 и т.д.
Сравниваем 7 с -1. . Меняем местами элементы и сохраняем позицию перестановки. Массив равен -1,7,15,11,0,4,25,33. В итоге получаем после первого шага Шейкер сортировки (рис. 1).

Запоминать, были или не были перестановки в процессе некоторого прохода.

Запоминать не только сам факт, что обмен имел место, но и положение (индекс) последнего обмена.

Чередовать направление последовательных просмотров.

Левая граница = Номер первого элемента

Правая граница = Номер последнего элемента

Пока Левая граница < Правой границы делать

Прямой проход "Пузырька" от Левой границы до Правой-1

Правая граница = Правая граница — 1

Обратный проход "Пузырька" от Правой границы до Левой+1

Левая граница = Левая граница + 1

 

k:= 25; {Индекс последнего изменения}

s:= 1; {Первый элемент массива}

e:= 25; {Последний элемент массива}

while e > s do

Begin

for i:= e downto s+1do if A [i] < A[i-1] then

Begin

tmp := A[i];

A[i] := A[i-1];

A[i-1] := tmp;

k := i; {запоминание индекса последней перестановки}

end;

s:=k;

for i:= s to e-1 do if A[i]>A[i+1] then

Begin

tmp := A[i];

A[i] := A[i+1];

A[i+1] := tmp;

k := i;

end;

e:=k;

end;

 

Сортировки массивов. Сортировка Шелла.

Задача сортировки

Задача сорт заключаются в упорядочении элементов массива.

Эта сортировка9) базируется на уже известном нам алгоритме простых вставок ПрВст. Смысл ее состоит в раздельной сортировке методом ПрВст нескольких частей, на которые разбивается исходный массив. Эти разбиения помогают сократить количество пересылок: для того, чтобы освободить "правильное" место для очередного элемента, приходится уже сдвигать меньшее количество элементов.

Алгоритм УлШелл

На каждом шаге (пусть переменная t хранит номер этого шага) нужно произвести следующие действия:

  1. вычленить все подпоследовательности, расстояние между элементами которых составляет kt;
  2. каждую из этих подпоследовательностей отсортировать методом ПрВст.

Нахождение убывающей последовательности расстояний kt, kt-1…, k1 составляет главную проблему этого алгоритма. Многочисленные исследования позволили выявить ее обязательные свойства:

  • k1 = 1;
  • для всех t kt > kt-1;
  • желательно также, чтобы все kt не были кратными друг другу (для того, чтобы не повторялась обработка ранее отсортированных элементов).

Дональд Кнут предлагает две "хорошие" последовательности расстояний:

1, 4, 13, 40, 121, _ (kt = 1+3*kt-1)

1, 3, 7, 15, 31, _ (kt = 1+2*kt-1 = 2t -1)

Первая из них подходит для сортировок достаточно длинных массивов, вторая же более удобна для коротких. Поэтому мы остановимся именно на ней (желающим запрограммировать первый вариант предоставляется возможность самостоятельно внести необходимые изменения в текст реализации алгоритма).

Как же определить начальное значение для t (а вместе с ним, естественно, и для kt)?

Можно, конечно, шаг за шагом проверять, возможно ли вычленить из сортируемого массива подпоследовательность (хотя бы длины 2) с расстояниями 1, 3, 7, 15 и т.д. между ее элементами. Однако такой способ довольно неэффективен. Мы поступим иначе, ведь у нас есть формула для вычисления kt = 2t -1.

Итак, длина нашего массива (N) должна попадать в такие границы:

kt <= N -1 < kt+1

или, что то же самое,

2t <= N < 2t+1

Прологарифмируем эти неравенства (по основанию 2):

t <= log N < t+1

Таким образом, стало ясно, что t можно вычислить по следующей формуле:

t = trunc(log N))

К сожалению, язык Pascal предоставляет возможность логарифмировать только по основанию е (натуральный логарифм). Поэтому нам придется вспомнить знакомое из курса средней школы правило "превращения" логарифмов:

logmx =logzx/logzm

В нашем случае m = 2, z = e. Таким образом, для начального t получаем:

t:= trunc(ln(N)/ln(2)).

Однако при таком t часть подпоследовательностей будет иметь длину 2, а часть — и вовсе 1. Сортировать такие подпоследовательности незачем, поэтому стоит сразу же отступить еще на 1 шаг:

t:= trunc(ln(N)/ln(2))-1

Расстояние между элементами в любой подпоследовательности вычисляется так:

k:= (1 shl t)-1; {k= 2t-1}

Количество подпоследовательностей будет равно в точности k. В самом деле, каждый из первых k элементов служит началом для очередной подпоследовательности. А дальше, начиная с (k+1)-го, все элементы уже являются членами некоторой, ранее появившейся подпоследовательности, значит, никакая новая подпоследовательность не сможет начаться в середине массива.

Сколько же элементов будет входить в каждую подпоследовательность? Ответ таков: если длину всей сортируемой последовательности (N) можно разделить на шаг k без остатка, тогда все подпоследовательности будут иметь одинаковую длину, а именно:

s:= N div k;

Если же N не делится на шаг k нацело, то первые р подпоследовательностей будут длиннее на 1. Количество таких "удлиненных" подпоследовательностей совпадает с длиной "хвоста" — остатка от деления N на шаг k:

P:= N mod k;


⇐ Предыдущая45678910111213Следующая ⇒


Дата добавления: 2015-10-21; просмотров: 358 | Нарушение авторских прав


Похожая информация:


Поиск на сайте:


Элементарные методы сортировки: обмен, вставка, выбор.

⇐ Предыдущая567891011121314Следующая ⇒

Существует три общих метода сортировки массивов:

  • Обмен
  • Выбор (выборка)
  • Вставка

Чтобы понять, как работают эти методы, представьте себе колоду игральных карт. Чтобы отсортировать карты методом обмена, разложите их на столе лицом вверх и меняйте местами карты, расположенные не по порядку, пока вся колода не будет упорядочена.

В методе выбораразложите карты на столе, выберите карту наименьшей значимости и положите ее в руку. Затем из оставшихся карт снова выберите карту наименьшей значимости и положите ее на ту, которая уже находится у вас в руке. Процесс повторяется до тех пор, пока в руке не окажутся все карты; по окончании процесса колода будет отсортирована.

Чтобы отсортировать колоду методом вставки, возьмите все карты в руку. Выкладывайте их по одной на стол, вставляя каждую следующую карту в соответствующую позицию. Когда все карты окажутся на столе, колода будет отсортирована.

Сортировка вставками

Сортировка вставками — простой алгоритм сортировки. Хотя этот алгоритм уступает в эффективности более сложным (таким как быстрая сортировка), у него есть ряд преимуществ:

· эффективен на небольших наборах данных, на наборах данных до десятков элементов может оказаться лучшим;

· эффективен на наборах данных, которые уже частично отсортированы;

· это устойчивый алгоритм сортировки (не меняет порядок элементов, которые уже отсортированы);

· может сортировать список по мере его получения;

Минусом -высокая сложность алгоритма: O(n²)

Вообще говоря, в худших случаях сортировка вставками настолько же плоха, как и пузырьковая сортировка и сортировка посредством выбора, а в среднем она лишь немного лучше.

Описание

На каждом шаге алгоритма мы выбираем один из элементов входных данных и вставляем его на нужную позицию в уже отсортированном списке, до тех пор, пока набор входных данных не будет исчерпан. Метод выбора очередного элемента из исходного массива произволен; может использоваться практически любой алгоритм выбора. Обычно (и с целью получения устойчивого алгоритма сортировки), элементы вставляются по порядку их появления во входном массиве.

Анализ Алгоритма

Время выполнения алгоритма зависит от входных данных: чем большее множество нужно отсортировать, тем большее время выполняется сортировка. Также на время выполнения влияет исходная упорядоченность массива. Так, лучшим случаем является отсортированный массив, а худшим — массив, отсортированный в порядке, обратном нужному. Временная сложность алгоритма при худшем варианте входных данных — θ(n²).

Реализация на java

public void addingSort() {

for (Node cur = first.next; cur != null; cur = cur.next) {

Node n = cur.prev;

Object val = cur.value;

for (; n != null; n = n.prev) {

if (((Comparable) n.value).compareTo(val) > 0) {

n.next.value = n.value;

} else {

break;

}

}

if (n != null) {

n.next.value = val;

} else {

first.value = val;

}

}

}

Сначала он сортирует два первых элемента. Затем алгоритм вставляет третий элемент в соответствующую порядку позицию по отношению к первым двум элементам. После этого он вставляет четвертый элемент в список из трех элементов. Этот процесс повторяется до тех пор, пока не будут вставлены все элементы. Например, при сортировке массива dcab каждый проход алгоритма будет выглядеть следующим образом:

 

Начало d c a b

Проход 1 c d a b

Проход 2 a c d b

Проход 3 a b c d

Сортировка выбором

Описание

При сортировке из массива выбирается элемент с наименьшим значением и обменивается с первым элементом. Затем из оставшихся n — 1 элементов снова выбирается элемент с наименьшим ключом и обменивается со вторым элементом, и т.д. Эти обмены продолжаются до двух последних элементов. Например, если применить метод выбора к массиву dcab, каждый проход будет выглядеть так:

Начало d c a bПроход 1 a c d bПроход 2 a b d cПроход 3 a b c d

Анализ

К сожалению, как и в пузырьковой сортировке, внешний цикл выполняется n — 1 раз, а внутренний — в среднем n/2 раз. Следовательно, сортировка посредством выбора требует 1/2(n2n)сравнений. Таким образом, это алгоритм порядка n2, из-за чего он считается слишком медленным для сортировки большого количества элементов. Несмотря на то, что количество сравнений в пузырьковой сортировке и сортировке посредством выбора одинаковое, в последней количество обменов в среднем случае намного меньше, чем в пузырьковой сортировке.

Реализация на java

public void SelectSort() {

Object c;

for (Node a = first; a != last; a = a.next) {

Node min = last;

for (Node b = a; b != last; b = b.next) {

if (((Comparable) b.val).compareTo(min.val) < 0) {

min = b;

}

}

c = a.val;

a.val = min.val;

min.val = c;

}

}

Сортировка Обменом

Самый известный алгоритм — пузырьковая сортировка. Его популярность объясняется интересным названием и простотой самого алгоритма. Тем не менее, в общем случае это один из самых худших алгоритмов сортировки.

Пузырьковая сортировка относится к классу обменных сортировок, т.е. к классу сортировок методом обмена. Ее алгоритм содержит повторяющиеся сравнения (т.е. многократные сравнения одних и тех же элементов) и, при необходимости, обмен соседних элементов. Элементы ведут себя подобно пузырькам воздуха в воде — каждый из них поднимается на свой уровень.

Чтобы наглядно показать, как работает пузырьковая сортировка, допустим, что исходный массив содержит элементы dcab.

Алгоритм пузырьковой сортировки одномерного массива на C++

Ниже показано состояние массива после каждого прохода:

Начало d c a b

Проход 1 a d c b

Проход 2 a b d c

Проход 3 a b c d

При анализе любого алгоритма сортировки полезно знать, сколько операций сравнения и обмена будет выполнено в лучшем, среднем и худшем случаях. Поскольку характеристики выполняемого кода зависят от таких факторов, как оптимизация, производимая компилятором, различия между процессорами и особенности реализации, мы не будем пытаться получить точные значения этих параметров. Вместо этого сконцентрируем свое внимание на общей эффективности каждого алгоритма.

В пузырьковой сортировке количество сравнений всегда одно и то же, поскольку два цикла for повторяются указанное количество раз независимо от того, был список изначально упорядочен или нет. Это значит, что алгоритм пузырьковой сортировки всегда выполняет

(n2n)/2

сравнений, где n — количество сортируемых элементов. Данная формула выведена на том основании, что внешний цикл выполняется n — 1 раз, а внутренний выполняется в среднем n/2 раз. Произведение этих величин и дает предыдущее выражение.

Обратите внимание на член n2 в формуле. Говорят, что пузырьковая сортировка является алгоритмом порядка n2, поскольку время ее выполнения пропорционально квадрату количества сортируемых элементов. Необходимо признать, что алгоритм порядка n2 не эффективен при большом количестве элементов, поскольку время выполнения растет экспоненциально в зависимости от количества сортируемых элементов.

В алгоритме пузырьковой сортировки количество обменов в лучшем случае равно нулю, если массив уже отсортирован. Однако в среднем и худшем случаях количество обменов также является величиной порядка n2.

 


⇐ Предыдущая567891011121314Следующая ⇒


Дата добавления: 2016-11-18; просмотров: 548 | Нарушение авторских прав


Похожая информация:


Поиск на сайте:


Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *