Сортировка массива по возрастанию (метод пузырька)
Последовательно просматриваем числа a0 , ..., an-1 находим наименьшее i такое, что ai > ai+1 .
Поменять ai и ai+1 местами, возобновить просмотр с элемента ai+1 и т.д.
Тем самым наибольшее число передвиниться на последнее место.
Следующие просмотры начинать опять сначала, уменьшая на единицу количество просматриваемых элементов.
Массив будет упорядочен после просмотра, в котором участвовали только первый и второй элементы.
Пример реализации - void bubblesort(int arr[], int n);
Сортировка массива по возрастанию выбором
Это наиболее естественный алгоритм упорядочивания.
Допустим, что элементы a0 , ..., ai-1 уже упорядочены, тогда среди оставшихся ai , ..., an-1
находим минимальный элемент и меняем его местами с i-тым элементом.
И так далее, пока массив не будет полностью упорядочен.
Сортировка выбором.
A[1..N] - сортируемый массив из n элементов.
for ( i=1; i 44
i=2 06 12| 55 42 94 18 44 67 12 <-> 55
i=3 06 12 18| 42 94 55 44 67 18 <-> 55
i=4 06 12 18 42| 94 55 44 67 42 <-> 42
i=5 06 12 18 42 44| 55 94 67 44 <-> 94
i=6 06 12 18 42 44 55| 94 67 55 <-> 55
i=7 06 12 18 42 44 55 67| 94 67 <-> 94
Вертикальной чертой отмечена граница уже отсортированной части
массива.
Сортировка выбором - простейший алгоритм, на практике не
используемый ввиду низкого быстродействия. Вместо этого
применяют ее улучшение - пирамидальную сортировку (Heapsort),
описанную в другом вопросе, а также (иногда) 'древесную сортировку'
Реализация - void selectionsort(int arr[], int n);
Сортировка массива по возрастанию (метод простых вставок)
Последовательно просматриваем a1 , ..., an-1 и каждый новый элемент ai вставляем на подходящее место
в уже упорядоченную совокупность a0 , ..., ai-1 .
Это место определяется последовательным сравнением ai с упорядоченными элементами a0 , ..., ai-1 .
Алгоритм
Все элементы условно разделяются на готовую
последовательность a1 ... ai-1 и входную ai ... an. Hа
каждом шаге, начиная с i=2 и увеличивая i на 1, берем i-й
элемент входной последовательности и вставляем его на
нужное место в готовую.
Пример:
Hачальные ключи 44 \ 55 12 42 94 18 06 67
i = 2 44 55 \ 12 42 94 18 06 67
i = 3 12 44 55 \ 42 94 18 06 67
i = 4 12 42 44 55 \ 94 18 06 67
i = 5 12 42 44 55 94 \ 18 06 67
i = 6 12 18 42 44 55 94 \ 06 67
i = 7 06 12 18 42 44 55 94 \ 67
i = 8 06 12 18 42 44 55 67 94 \
При поиске подходящего места удобно 'просеивать' x,
сравнивая его с очередным элементом ai и либо вставляя его,
либо пересылая ai направо и продвигаясь налево.
Просеивание может кончиться при двух условиях:
1. Hайден ai с ключом, меньшим x.
2. Достигнут конец готовой последовательности.
Метод хорош устойчивостью сортировки, удобством для
реализации в списках и, самое главное, естественностью
поведения. То есть уже частично отсортированный массив
будут досортирован им гораздо быстрее чем многими
'продвинутыми' методами.
Анализ
Число сравнений
минимальное: n - 1
среднее: ( n^2 + n - 2 ) / 4
максимальное: ( n^2 + n ) * / 2 - 1
Количество пересылок
минимальное: 2 * ( n - 1 )
среднее: ( n^2 + 9 * n - 10 ) / 4
максимальное: ( n^2 + 3 * n - 4 ) / 2
Примечания.
1. Если мы работаем с массивом, а не списком, то искать место вставки
очередного ai в готовую последовательность можно бинарным поиском,
ведь a1..a_i-1 уже отсортированы!
При этом количество сравнений снизится до O(nlogn),
но сортировка станет вести себя крайне неестественно (уже
отсортированный массив обрабатывается дольше всего), а,
самое главное, количество пересылок по-прежнему останется O(n^2).
2. При работе с массивами можно использовать и другое улучшение
InsertSort'a - ShellSort (описана в другом вопросе).
Пример на Си - Tomas Niemann.
--------------------------------------------------------------------
typedef int item; /* Тип сортируемых элементов */
typedef int tblIndex; /* Тип ключей, по которым сортируем */
#define compGT(a,b) (a > b) /* Функция сравнения */
void insertSort(T *a, tblIndex lb, tblIndex ub) {
item t;
tblIndex i, j;
/***********************
* сортируем a[lb..ub] *
***********************/
for (i = lb + 1; i <= ub; i++) {
t = a[i];
/* Сдвигаем элементы вниз, пока */
/* не найдем место вставки. */
for (j = i-1; j >= lb && compGT(a[j], t); j--)
a[j+1] = a[j];
/* вставка */
a[j+1] = t;
}
}
Реализация - void insertionsort(int arr[], int n);
Сортировка массива по возрастанию (метод бинарных вставок)
Этот алгоритм представляет из себя оптимизированную версию предыдущего, отличие заключается в том,
что при поиске место, на которое надо вставить элемент ai в уже упорядоченную совокупность
a0 , ..., ai-1 , определяется алгоритмом деления пополам
(отсюда и название алгоритма "бинарные вставки" здесь понимаем как "вставка делением пополам").
Реализация - void binaryinsertionsort(int arr[], int n);
Сортировка массива методом Шелла
Описание и исходник ShellSort (сортировка Шелла)
Этот алгоритм - модификация сортировки простыми вставками.
Идея, например, в случае 16 чисел n1 ... n16 такова:
Вначале сортируем простыми вставками каждые 8 групп из 2-х элементов
(n1, n9), (n2, n10), ... , (n8, n16).
Потом сортируем каждую из четырех групп по 4 элемента (n1, n5, n9, n13),
..., (n4, n8, n12, n16). Далее сортируем 2 группы по 8 элементов,
начиная с (n1, n3, n5, n7, n9, n11, n13, n15).
А в конце сортируем вставками все 16 элементов.
Очевидно, лишь последняя сортировка необходима,
чтобы расположить все элементы по своим местам.
Так зачем нужны остальные ?
Hа самом деле они продвигают элементы максимально близко
к соответствующим позициям, так что в последней стадии число
перемещений будет весьма невелико. Они и так почти рассортированы.
Были проведены многочисленные исследования по вопросу,
какова должна быть последовательность расстояний между сортируемыми
элементами в зависимости от прохода (инкремент).
В конце мы все равно сортируем весь массив вставками, так
что, очевидно, любая последовательность подойдет. Hабор
..., 8, 4, 2, 1 - неплохой выбор, особенно,
когда N - степень двойки. Hо гораздо лучше будет взять
( 3k - 1 )/2, ..., 40, 13, 4, 1
Ее можно вычислить рекуррентно:
i_1 = 1, i_k+1 = 3i_k + 1, k = 1, 2, ...
При этой последовательности количество операций даже
в наихудшем случае - порядка N^3/2.
Для случайной последовательности при N < 60000
количество операций, приблизительно, N^1.25,
однако уже при N > 50 QuickSort быстрее.
Исходник на Си.
void shell(unsigned long n, float a[])
{
unsigned long i, j, inc;
float v;
inc=1; // начальный инкремент
do {
inc *=3;
inc++;
} while (inc <= n);
do { // Цикл частичных сортировок
inc /=3;
// Внутренний цикл простых вставок
for (i=inc+1; i<=n; i++) {
v=a[i];
j=i;
while ( a[j-inc] > v) {
a[j] = a[j-inc];
j -= inc;
if ( j <= inc ) break;
}
a[j]=v;
}
} while ( inc > 1 );
}
Реализация - void shellsort(int arr[], int n);
Сортировка массива по возрастанию (метод Уильяма Флойда, бинарных деревьев)
Алгоритм основан на представлении массива в виде бинарного дерева, обладающего особыми свойствами.
В памяти компьютера все элементы массива расположены последовательно,
структура же дерева определяется следующим образом:
будем считать, что i-ый элемент массива ("предок") имеет два элемента потомка с номерами 2i+1 и 2i+2.
Дерево имеет нормальную форму, если любой элемент предок больше своих потомков.
Для понимания алгоритма рассмотрите приведенную блок-схему.
Из свойств алгоритма стоит заметить, что он дает стабильно хорошую скорость упорядочивания (порядка n*log(n)),
вне зависимости от того с каким массивом работает,
и поэтому используется в случаях когда необходимо гарантировано упорядочить массив за короткое время.
Двоичным(бинарным) деревом назовем упорядоченную структуру данных,
в которой каждому элементу - предшественнику или корню (под)дерева -
поставлены в соответствие по крайней мере два других элемента (преемника).
Причем для каждого предшественника выполнено следующее правило:
левый преемник всегда меньше, а правый преемник всегда больше или равен
предшественнику.
Вместо 'предшественник' и 'преемник' также употребляют термины
'родитель' и 'сын'. Все элементы дерева также называют 'узлами'.
При добавлении в дерево нового элемента его последовательно сравнивают
с нижестоящими узлами, таким образом вставляя на место.
Если элемент >= корня - он идет в правое поддерево, сравниваем его уже
с правым сыном, иначе - он идет в левое поддерево, сравниваем с левым,
и так далее, пока есть сыновья, с которыми можно сравнить.
Вот процесс построения дерева из последовательности 44 55 12 42 94 18 06 67:
44 44 44 44 44
\ / \ / \ / \
55 12 55 12 55 12 55
\ \ \
42 42 94
(**) 44 44 (*) 44
/ \ / \ / \
12 55 12 55 12 55
\ \ / \ \ / \ \
42 94 06 42 94 06 42 94
/ / / /
18 18 18 67
Дерево может быть и более-менее ровным, как на (*), может и иметь всего
две основные ветви (**), а если входная последовательность уже отсортирована,
то дерево выродится в линейный список.
Если мы будем рекурсивно обходить дерево по правилу
"левый сын - родитель - правый сын", то, записывая все
встречающиеся элементы в массив, мы получим упорядоченное
в порядке возрастания множество. Hа этом и основана идея сортировки деревом.
Более подробно правило обхода можно сформулировать как
обойти левое поддерево - вывести корень - обойти правое поддерево,
где рекурсивная процедура 'обойти' вызывает себя еще раз, если сталкивается
с узлом-родителем и выдает очередной элемент, если у узла нет сыновей.
/*********** сортировка с помощью двоичного дерева *************/
#include
#include
typedef struct tree
{
int a; // данные
struct tree *left; // левый сын
struct tree *right; // правый сын
} TREE;
TREE *add_to_tree(TREE *root, int new_value)
{
if (root==NULL) // если нет сыновей - создаем новый элемент
{
root = (TREE*)malloc(sizeof(TREE));
root->a = new_value;
root->left = root->right = 0;
return root;
}
if (root->a < new_value) // добавлем ветвь
root->right = add_to_tree(root->right, new_value);
else
root->left = add_to_tree(root->left, new_value);
return root;
}
void tree_to_array(TREE *root, int a[]) // процедура заполнения массива
{
static max2=0; // счетчик элементов нового массива
if (root==NULL) return; // условие окончания - нет сыновей
tree_to_array(root->left, a); // обход левого поддерева
a[max2++] = root->a;
tree_to_array(root->right, a); // обход правого поддерева
free(root);
}
void sort_tree(int a[], int elem_total) // собственно сортировка
{
TREE *root;
int i;
root = NULL;
for (i=0; i Другое описание метода 'древесной сортровки' можно найти, например,
> у H. Вирта в книге 'Алгоритмы + Структуры Данных = Программы'.
Основное различие - строится не представление данных в виде дерева,
а 'дерево выбора'. С помощью n/2 сравнений можно определить
наименьший элемент из каждой пары, при помощи следующих n/4 -
наименьший из каждой пары таких наименьших ключей и т.д
При этом за n-1 сравнений мы можем построить дерево выбора, как
показано для чисел 44 55 12 42 94 18 06 67:
06 Это HЕ двоичное дерево в смысле,
/ \ определенном выше.
/ \ И это HЕ пирамида, используемая в HeapSort
/ \
/ \
/ \
/ \
12 06 Hа втором шаге мы спускаемся по
/ \ / \ пути, указанному наименьшим ключом
/ \ / \ и исключаем его, последовательно
/ \ / \ заменяя либо на 'дыру' (или ключ
44 12 18 06 'бесконечность'(БЕСК), либо на элемент,
/ \ / \ / \ / \ находящийся на противоположной
44 55 12 42 94 18 06 67 ветви промежуточного узла:
взяли ключ 06 сверху опять выбрали наименьший с учетом, что любой
БЕСК 12 ключ < БЕСК.
/ \ / \
/ \ / \
/ \ / \
/ \ / \
/ \ / \
/ \ / \
12 БЕСК 12 18
/ \ / \ / \ / \
/ \ / \ / \ / \
/ \ / \ / \ / \
44 12 18 БЕСК 44 12 18 67
/ \ / \ / \ / \ / \ / \ / \ / \
44 55 12 42 94 18 БЕСК 67 44 55 12 42 94 18 БЕСК 67
Очевидно, требуется n операций на создание первоначального дерева,
а затем n шагов, каждый по log n сравнений для выбора нового наименьшего.
2
Такой вариант TreeSort довольно сильно отличается от изложенного выше.
Этот алгоритм еще называют 'выбор с замещением' и его можно неплохо
применять в тех же случаях, что и выше.
При этом он может быть даже выгоднее предыдущего метода,
хотя бы потому, что не нужно запоминать позицию, на которой мы остановились
при обходе дерева, т.е можно взять верхний элемент -> восстановить дерево ->
проделать некоторые операции -> взять следующий элемент и т.п.
Обходить же дерево удобно сразу целиком, либо какую-то его большую часть.
Кроме того, самой структура дерева выбора также может быть полезна.
Однако, нужно учесть, что памяти для дерева выбора нужно на
2n-1 элементов (элемент = ключ + указатели), в отличие от n элементов для
простого дерева.
Пример использования выбора с замещением можно увидеть в
многофазной сортировке (см соответствующий вопрос). Элементы обоих
'древесных' сортировок также используются в смежных
Пример реализации - void heapsort(int arr[], int n);
Сортировка массива по возрастанию (метод фон Неймана, слияний)
Алгоритм фон Неймана упорядочивания массива (алгоритм сортировки слияниями)
основан на многократных слияниях уже упорядоченных групп элементов массива.
Вначале весь массив рассматривается как совокупность упорядоченных групп по одному элементу в каждой.
Слиянием соседних групп получаем упорядоченные группы, каждая из которых содержит два элемента
(кроме, возможно, последней группы которой не нашлось парной).
Далее, упорядоченные группы укрупняются тем же способом и т.д.
Алгоритм дает хорошие показатели по скорости работы, даже в сравнении с сортировкой методом бинарных деревьев.
Единственный недостаток - необходимость использовать дополнительный массив того же размера.
Реализация - void neumansort(int arr[], int n);
Поиск k-го по величине элемента массива
Алгоритм ищет в массиве M, состоящем из n элементов, k-ый по величине элемент.
Эту задачу можно решить упорядочив массив и взяв элемент M[k],
но упорядочивание имеет скорость не лучше O(n*log(n)),
данный же алгоритм, и это можно достаточно строго доказать, имеет скорость работы O(n).
Каждый шаг работы алгоритма состоит из двух этапов и приводит к сокращению числа рассматриваемых элементов n.
Первый этап. Поиск некоторого "среднего" элемента в массиве M, который осуществляется следующим образом:
разобьем массив М на части по 5 элементов в каждой и упорядочим подмассивы по неубыванию.
Из средних элементов подмассивов (элементов с номером 3) составим новый массив,
с которым проделаем то же самое, будем осуществлять этот алгоритм пока не останется один элемент,
который мы помещаем в переменную med и переходим ко второму этапу.
Второй этап. Просматривая элементы массива M, перегруппируем их так, чтобы вначале шли элементы меньшие
или равные med, а затем большие med. Допустим первая часть массива содержит j элементов
(соответственно вторая n-j). Если k < j, то искомый элемент содержиться в первой половине массива,
тогда полагаем n = j и возвращаемся к первому этапу. Если k > j,
то искомый элемент находится во второй части массива, тогда переносим n-j последних элементов
в начало массива, полагаем n = n-j, k = k-j и возращаемся к первому этапу.
Продолжаем до того момента пока n не станет меньше 5, когда это произойдет просто упорядочим оставшиеся элементы
(их меньше 5) и элемент с номером k, будет искомым.
Пример реализации - double kthelement(int marr[], int n, int k);
QuickSort (быстрая сортировка)
====================================================================
Описание и исходник QuickSort (быстрая сортировка)
====================================================================
Основной алгоритм
Выберем случайным образом какой-то элемент х и
просмотрим массив, двигаясь слева направо, пока не
найдем аi больший x, а затем справа налево, пока не
найдем аi меньший х. Поменяем их местами и продолжим
процесс просмотра с обменом, пока просмотры не
встретятся где-то в середине массива.
В результате массив разделится на две части:
левую - с ключами, меньшими х и правую - с ключами,
большими х.
Этот шаг называется разделением. Х - центром.
К получившимся частям рекурсивно применяем ту же
процедуру. В результате получается очень эффективная сортировка.
Среднее быстродействие O(nlogn), но возможен случай таких
входных данных, на которых алгоритм будет работать за O(n^2)
операций. Hа случайных входных данных вероятность
такого чрезвычайно мала, кроме того, с этим можно бороться
при помощи некоторой модификации метода, описанной ниже.
Устойчивости нет. Поведение неестественно.
Пример рекурсивной QuickSort
-------------------------------------------------
typedef int item; /* Тип сортируемых элементов */
typedef int tblIndex; /* Тип ключей, по которым сортируем */
#define CompGT(a,b) (a > b)
tblIndex partition(T *a, tblIndex lb, tblIndex ub) {
item t, pivot;
tblIndex i, j, p;
/**********************************
* разделение массива a[lb..ub] *
**********************************/
/* Выбираем центр - pivot */
p = lb + ((ub - lb)>>1);
pivot = a[p];
a[p] = a[lb];
/* сортируем lb+1..ub относительно центра */
i = lb+1;
j = ub;
while (1) {
while (i < j && compGT(pivot, a[i])) i++;
while (j >= i && compGT(a[j], pivot)) j--;
if (i >= j) break;
t = a[i];
a[i] = a[j];
a[j] = t;
j--; i++;
}
/* центр в a[j] */
a[lb] = a[j];
a[j] = pivot;
return j;
}
void quickSort(T *a, tblIndex lb, tblIndex ub) {
tblIndex m;
/**************************
* сортируем a[lb..ub] *
**************************/
while (lb < ub) {
/* сортировка вставками для малых массивов */
if (ub - lb <= 12) {
insertSort(a, lb, ub);
return;
}
/* разделение пополам */
m = partition (a, lb, ub);
/* Уменьшаем требования к памяти: */
/* меньший сегмент сортируем первым */
if (m - lb <= ub - m) {
quickSort(a, lb, m - 1);
lb = m + 1;
} else {
quickSort(a, m + 1, ub);
ub = m - 1;
}
}
}
Улучшения
Hа практике для увеличения быстроты,
можно произвести несколько улучшений:
1. Произвести случайную перестановку всех чисел
массива перед сортировкой. Алгоритм с этим улушением
называется Randomized Quicksort и работает в среднем за O(nlogn)
времени при любых неприятных закономерностях в потоке входных
данных.
В зависимости от приложения можно использовать
этот вариант, либо каждый раз выбирать в качестве центрального
для функции partition средний из первого, последнего и среднего
элементов.
Если же вероятность таких неблагоприятных входных
данных крайне мала(массив случаен), то этот пункт можно
вовсе опустить.
2. Для коротких массивов вызывается сортировка
вставками. Из-за рекурсии и других "накладных
расходов" Quicksort оказывается не столь уж
быстрой для коротких массивов. Поэтому, если в массиве
меньше 12 элементов, вызывается сортировка вставками.
Пороговое значение не критично - оно сильно зависит от
качества генерируемого кода.
3. Если последний оператор функции является
вызовом этой функции, говорят о хвостовой рекурсии. Ее
имеет смысл заменять на итерации - в этом случае лучше
используется стек.
4. После разбиения сначала сортируется меньший
раздел. Это также приводит к лучшему использованию
стека, поскольку короткие разделы сортируются быстрее
и им нужен более короткий стек. Требования к памяти
уменьшаются с n до log n.
Пример, входящий в стандартную реализацию Си
использует многие из этих улучшений.
Стандартная реализация итерационной QuickSort
------------------------------------------------
#include < limits.h>
#define MAXSTACK (sizeof(size_t) * CHAR_BIT)
static void exchange(void *a, void *b, size_t size) {
size_t i;
/******************
* обменять a,b *
******************/
for (i = sizeof(int); i <= size; i += sizeof(int)) {
int t = *((int *)a);
*(((int *)a)++) = *((int *)b);
*(((int *)b)++) = t;
}
for (i = i - sizeof(int) + 1; i <= size; i++) {
char t = *((char *)a);
*(((char *)a)++) = *((char *)b);
*(((char *)b)++) = t;
}
}
void qsort(void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *)) {
void *lbStack[MAXSTACK], *ubStack[MAXSTACK];
int sp;
unsigned int offset;
lbStack[0] = (char *)base;
ubStack[0] = (char *)base + (nmemb-1)*size;
for (sp = 0; sp >= 0; sp--) {
char *lb, *ub, *m;
char *P, *i, *j;
lb = lbStack[sp];
ub = ubStack[sp];
while (lb < ub) {
/* выбираем центр и меняемся с 1м элементом */
offset = (ub - lb) >> 1;
P = lb + offset - offset % size;
exchange (lb, P, size);
/* разделение в два сегмента */
i = lb + size;
j = ub;
while (1) {
while (i < j && compar(lb, i) > 0) i += size;
while (j >= i && compar(j, lb) > 0) j -= size;
if (i >= j) break;
exchange (i, j, size);
j -= size;
i += size;
}
/* центр в A[j] */
exchange (lb, j, size);
m = j;
/* Меньший сегмент продолжаем обрабатывать, больший - в стек */
if (m - lb <= ub - m) {
if (m + size < ub) {
lbStack[sp] = m + size;
ubStack[sp++] = ub;
}
ub = m - size;
} else {
if (m - size > lb) {
lbStack[sp] = lb;
ubStack[sp++] = m - size;
}
lb = m + size;
}
}
}
}
#include < stdio.h>
#include < stdlib.h>
int arr[]={6,5,7,33,44,9,2,1,8,10};
void bubblesort(int arr[], int n);
void selectionsort(int arr[], int n);
void insertionsort(int arr[], int n);
void binaryinsertionsort(int arr[], int n);
void shellsort(int arr[], int n);
void heapsort(int arr[], int n);
void neumansort(int arr[], int n);
double kthelement(int marr[], int n, int k);
int main()
{
int i=0;
bubblesort(&arr,10);
selectionsort(&arr,10);
insertionsort(&arr,10);
binaryinsertionsort(&arr,10);
shellsort(&arr,10);
heapsort(&arr,10);
neumansort(&arr,10);
int sdf =kthelement(&arr,10,6);
for(i=0;i<10;i++)
{
printf ("%d\n",arr[i]);
}
printf ("\n%d\n",sdf);
return 0 ;
}
void bubblesort(int arr[], int n)
{
int i;
int j;
double tmp;
for(i = 0; i <= n-1; i++)
{
for(j = 0; j <= n-2-i; j++)
{
if( arr[j]>arr[j+1] )
{
tmp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = tmp;
}
}
}
}
void selectionsort(int arr[], int n)
{
int i;
int j;
int k;
double m;
for(i = 1; i <= n; i++)
{
m = arr[i-1];
k = i;
for(j = i; j <= n; j++)
{
if( m>arr[j-1] )
{
m = arr[j-1];
k = j;
}
}
arr[k-1] = arr[i-1];
arr[i-1] = m;
}
}
void insertionsort(int arr[], int n)
{
int i;
int j;
int k;
double tmp;
n = n-1;
i = 1;
do
{
j = 0;
do
{
if( arr[i]<=arr[j] )
{
k = i;
tmp = arr[i];
do
{
arr[k] = arr[k-1];
k = k-1;
}
while(k>j);
arr[j] = tmp;
j = i;
}
else
{
j = j+1;
}
}
while(jarr[i-1] )
{
e = c;
}
else
{
b = c;
}
c = (b+e)/2;
}
if( arr[b-1]arr[e-1] )
{
b = e+1;
}
else
{
b = e;
}
}
k = i;
tmp = arr[i-1];
while(k>b)
{
arr[k-1] = arr[k-1-1];
k = k-1;
}
arr[b-1] = tmp;
i = i+1;
}
while(i<=n);
}
void shellsort(int arr[], int n)
{
int c;
int e;
int g;
int i;
int j;
double tmp;
n = n-1;
g = (n+1)/2;
do
{
i = g;
do
{
j = i-g;
c = 1;
do
{
if( arr[j]<=arr[j+g] )
{
c = 0;
}
else
{
tmp = arr[j];
arr[j] = arr[j+g];
arr[j+g] = tmp;
}
j = j-1;
}
while(j>=0&&(c==1));
i = i+1;
}
while(i<=n);
g = g/2;
}
while(g>0);
}
void heapsort(int arr[], int n)
{
int i;
int j;
int k;
int t;
double tmp;
if( n==1 )
{
return;
}
i = 2;
do
{
t = i;
while(t!=1)
{
k = t/2;
if( arr[k-1]>=arr[t-1] )
{
t = 1;
}
else
{
tmp = arr[k-1];
arr[k-1] = arr[t-1];
arr[t-1] = tmp;
t = k;
}
}
i = i+1;
}
while(i<=n);
i = n-1;
do
{
tmp = arr[i];
arr[i] = arr[0];
arr[0] = tmp;
t = 1;
while(t!=0)
{
k = 2*t;
if( k>i )
{
t = 0;
}
else
{
if( karr[k-1] )
{
k = k+1;
}
}
if( arr[t-1]>=arr[k-1] )
{
t = 0;
}
else
{
tmp = arr[k-1];
arr[k-1] = arr[t-1];
arr[t-1] = tmp;
t = k;
}
}
}
i = i-1;
}
while(i>=1);
}
void neumansort(int arr[], int n)
{
int c;
int i;
int i1;
int i2;
int n1;
int n2;
int j;
int k;
double tmp;
int barr[n];
int mergelen;
//barr.setbounds(0, n-1);
mergelen = 1;
c = 1;
while(mergelenn )
{
n2 = n;
}
while(i1<=n1||i2<=n2)
{
if( i1>n1 )
{
while(i2<=n2)
{
i = i+1;
barr[i-1] = arr[i2-1];
i2 = i2+1;
}
}
else
{
if( i2>n2 )
{
while(i1<=n1)
{
i = i+1;
barr[i-1] = arr[i1-1];
i1 = i1+1;
}
}
else
{
if( arr[i1-1]>arr[i2-1] )
{
i = i+1;
barr[i-1] = arr[i2-1];
i2 = i2+1;
}
else
{
i = i+1;
barr[i-1] = arr[i1-1];
i1 = i1+1;
}
}
}
}
}
i = i+1;
while(i<=n)
{
barr[i-1] = arr[i-1];
i = i+1;
}
}
else
{
i = 0;
while(i+mergelen<=n)
{
i1 = i+1;
i2 = i+mergelen+1;
n1 = i+mergelen;
n2 = i+2*mergelen;
if( n2>n )
{
n2 = n;
}
while(i1<=n1||i2<=n2)
{
if( i1>n1 )
{
while(i2<=n2)
{
i = i+1;
arr[i-1] = barr[i2-1];
i2 = i2+1;
}
}
else
{
if( i2>n2 )
{
while(i1<=n1)
{
i = i+1;
arr[i-1] = barr[i1-1];
i1 = i1+1;
}
}
else
{
if( barr[i1-1]>barr[i2-1] )
{
i = i+1;
arr[i-1] = barr[i2-1];
i2 = i2+1;
}
else
{
i = i+1;
arr[i-1] = barr[i1-1];
i1 = i1+1;
}
}
}
}
}
i = i+1;
while(i<=n)
{
arr[i-1] = barr[i-1];
i = i+1;
}
}
mergelen = 2*mergelen;
if(c==1) c=0;else c=1;
}
if( (c==0) )
{
i = 1;
do
{
arr[i-1] = barr[i-1];
i = i+1;
}
while(i<=n);
}
}
double kthelement(int marr[], int n, int k)
{
double result;
int i;
int j;
int l;
int nm;
int mm;
int km;
double med;
double tmp;
double tmp2;
int larr[10];
int mergelen;
k = k+1;
while(n>5)
{
i = 1;
do
{
larr[i-1] = marr[i-1];
i = i+1;
}
while(i<=n);
nm = n;
while(nm>5)
{
mm = nm/5;
i = 1;
do
{
km = (i-1)*5;
j = 1;
do
{
l = 1;
do
{
if( larr[km+l-1]>larr[km+l-1] )
{
tmp = larr[km+l-1];
larr[km+l-1] = larr[km+l];
larr[km+l] = tmp;
}
l = l+1;
}
while(l<=5-j);
j = j+1;
}
while(j<=5);
larr[i-1] = larr[km+2];
i = i+1;
}
while(i<=mm);
km = mm*5;
nm = nm-km;
if( nm>0 )
{
mm = mm+1;
if( nm>1 )
{
j = 1;
do
{
l = 1;
do
{
if( larr[km+l-1]>larr[km+l] )
{
tmp = larr[km+l-1];
larr[km+l-1] = larr[km+l];
larr[km+l] = tmp;
}
l = l+1;
}
while(l<=nm-j);
j = j+1;
}
while(j<=nm);
}
larr[mm-1] = larr[km];
}
nm = mm;
}
if( nm!=1 )
{
j = 1;
do
{
l = 1;
do
{
if( larr[l-1]>larr[l] )
{
tmp = larr[l-1];
larr[l-1] = larr[l];
larr[l] = tmp;
}
l = l+1;
}
while(l<=nm-j);
j = j+1;
}
while(j<=nm);
if( nm>=3 )
{
med = larr[1];
}
else
{
med = larr[0];
}
}
else
{
med = larr[0];
}
i = 1;
j = n;
while(i!=j)
{
if( marr[i-1]>med )
{
while(marr[j-1]>med&&i!=j)
{
j = j-1;
}
if( i!=j )
{
tmp2 = marr[i-1];
marr[i-1] = marr[j-1];
marr[j-1] = tmp2;
i = i+1;
}
}
else
{
i = i+1;
}
}
if( k>=j )
{
i = j;
do
{
marr[i-j] = marr[i-1];
i = i+1;
}
while(i<=n);
n = n-j+1;
k = k-j+1;
}
else
{
n = j-1;
}
}
if( n!=1 )
{
i = 1;
do
{
j = 1;
do
{
if( marr[j-1]>marr[j] )
{
tmp2 = marr[j-1];
marr[j-1] = marr[j];
marr[j] = tmp2;
}
j = j+1;
}
while(j<=n-i);
i = i+1;
}
while(i<=n);
result = marr[k-1];
}
else
{
result = marr[0];
}
return result;
}
Оставьте свой комментарий !
Автор
Комментарий к данной статье
Igor'
Очень практично!!!!! 2006-04-05 11:56:23
Яковлев Се�
Типа да :-)
Вообще информации про сортировку навалом в инете
Я постарался собрать в кучу доступные мне материалы
Подозреваю , что это малая толика от того , что можно собрать
2006-04-05 12:40:47
Луизик
хоть немного нашла информации. Спасибки))) 2006-05-31 21:05:53
James
Гран мерси)
2007-06-27 23:42:01
Ирина
Пасибааааааааа:))))) 2009-11-09 21:22:21
"alert("XSS"
"alert("XSS");" 2011-08-28 23:27:21
Игорь
Поиск k-го по величине элемента массива индеец какой то писал там 4 строчки кода используя дополнительную функцыю поиска среднего елемента 2012-02-16 21:36:06
LINUX