Программирование на языке высокого уровня. Марапулец Ю.В. - 47 стр.

UptoLike

ВУЗ: 

КамчатГТУ | Петропавловск-Камчатский

Составители: 

Рубрика: 

void sort_insert1 (int A[], int n)
{
for ( int i=1; i < n; i++)
{
int buf=A[i]; // Действие 1: сохранить очередной элемент
for (int k=0; k<i; k++) // Действие 2: поиск места вставки
if(A[k]>buf) break; // перед первым элементом, большим buf
for(int j=i-1; j>=k; j--) // Действие 3: сдвиг на 1 элемент вправо
A[j+1]=A[j];
A[k]=buf; //Действие 4: вставка очередного элемента
} // на место первого, который больше его
}
Вставка погружением. Очередной элемент «погружается» путем ряда обменов с
предыдущим до требуемой позиции в уже упорядоченную часть массива, пока «не дос-
тигнет дна» либо пока не встретит элемент, меньше себя.
void sort_insert2(int A[], int n)
{
for ( int i=1; i<n; i++)
// Пока не достигли "дна" или элемента, меньше себя
for ( int k=i; k !=0 && A[k] < A[k-1]; k--)
{
int buf=A[k],
A[k]=A[k-1];
A[k-1]=buf;
}
}
Сортировка Шелла. Существенными в сортировках вставками являются затраты
на обмены или сдвиги элементов. Для их уменьшения желательно сначала производить
погружение с большим шагом, сразу определяя элемент «по месту», а затем делать точ-
ную «подгонку». Так реализовано в сортировке Шелла: исходный массив разбивается на
m частей, в каждую из которых попадают элементы с шагом m, начиная от 0, 1,..., m-1
соответственно, то есть
0 , m , 2m , 3m ,...
1 , m+1, 2m+1, 3m+1,...
2 , m+2, 2m+2, 3m+2,...
Каждая часть сортируется отдельно с использованием алгоритма вставок или об-
мена. Затем выбирается меньший шаг, и алгоритм повторяется. Шаг удобно выбрать
равным степеням 2, например, 64, 32, 16, 8, 4, 2, 1. Последняя сортировка выполняется с
шагом 1. Несмотря на увеличение числа циклов, суммарное число перестановок будет
меньшим. Принцип сортировки Шелла можно применить и во всех обменных сортиров-
ках. Следует отметить, что сортировка Шелла требует четырех вложенных циклов:
-
1-й по шагу сортировки (по уменьшающимся степеням 2 - m = 64, 32, 16 ...);
-
2-й по группам (по индексу первого элемента в диапазоне k = 0 ... m-1);
-
еще два цикла обычной сортировки погружением для элементов группы, начинаю-
щейся с k с шагом m.
Для двух последних циклов нужно взять базовый алгоритм, заменив шаг 1 на m и
поменяв границы сортировки.
47
void sort_insert1 (int A[], int n)
{
        for ( int i=1; i < n; i++)
        {
                 int buf=A[i];                // Действие 1: сохранить очередной элемент
                 for (int k=0; kbuf) break; // перед первым элементом, большим buf
                for(int j=i-1; j>=k; j--) // Действие 3: сдвиг на 1 элемент вправо
                          A[j+1]=A[j];
                A[k]=buf;               //Действие 4: вставка очередного элемента
        }                                 // на место первого, который больше его
}

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

void sort_insert2(int A[], int n)
{
        for ( int i=1; i

Страницы