Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Реализация сортировки вставками. Алгоритм Шелла.
Если первоначальный файл отсортирован, то на каждом просмотре делается только одно сравнение, так что эта сортировка имеет порядок О(n). Если файл отсортирован первоначально в обратном порядке, то данная сортировка имеет общее число сравнений
(n -1) + (n -2) + … + 3 + 2 + 1 = (n -1)* n /2. Сортировка простыми вставками лучше, чем сортировка «методом пузырька». Чем ближе файл к отсортированному виду, тем более эффективной становится сортировка простыми вставками. Среднее число сравнений в сортировке простыми вставками, рассматривая все возможные перестановки во входном массиве, составляет О(n 2). Требования на пространство для этой сортировки состоят только из одной временной переменной, например, Y. Улучшение сортировки простыми вставками достигается использованием вставок в список. При таком подходе используется массив указателей link, по одному указателю на каждый элемент первоначального массива. Данный массив можно представить как некоторый линейный список, на который указывает некоторый внешний указатель first. Для того чтобы вставить k -й элемент, организуется прохождение данного связанного списка до тех пор, пока не будет найдена нужная позиция для X (k) или пока не будет достигнут конец списка. В этот момент X (k) может быть вставлен в этот список просто при помощи настройки указателей списка без какого-либо сдвига элементов в массиве. Это уменьшает время, требуемое для вставки, но не время, необходимое для поиска нужной позиции. Требование на пространство также возникает из-за дополнительного массива link. Среднее число сравнений по прежнему равно О(n 2).
Сортировка Шелла (сортировка с убывающим шагом)
В этом методе в первоначальном файле сортируются отдельные подфайлы. Значение k назовем шагом. Например, если k =5, то первым сортируется подфайл, состоящий из элементов X (1), X (6), X (11) … Пять подфайлов каждый содержащий одну пятую элементов первоначального файла, сортируются аналогичным образом:
Subfile1 Þ X(1), X(6), X(11) … Subfile2 Þ X(2), X(7), X(12) … Subfile3 Þ X(3), X(8), X(13) … Subfile4 Þ X(4), X(9), X(14) … Subfile 5 Þ X (5), X (10), X (15) … После того как первые k подфайлов будут отсортированы (обычно при помощи метода простых вставок), выбираем некоторое новое меньшее значение k и данный файл снова разделяется на новый набор подфайлов. Каждый из подфайлов сортируется, и данный процесс повторяется опять с еще меньшим значением k. В конце концов k принимает значение 1, и тогда сортируется подфайл, состоящий из всего файла [3].
Пример. Задана последовательность 25, 57, 48, 37, 12, 92, 86, 33. Отсортировать ее по возрастанию элементов, используя алгоритм Шелла.
Решение. Первоначальный файл 25 57 48 37 12 92 86 33 Просмотр 1, шаг 5 25 57 48 37 12 92 86 33
Просмотр 2, шаг 3 25 57 33 37 12 92 86 48
Просмотр 3, шаг 1 25 12 33 37 48 92 86 57
Отсортированный файл 12 25 33 37 48 57 86 92
Поскольку первый используемый в сортировке Шелла шаг является большим, отдельные подфайлы являются достаточно малыми и потому сортировка простыми вставками над этими подфайлами работает достаточно быстро. Сортировка каждого подфайла приводит к тому, что весь файл становится ближе к отсортированному виду. И последующие частичные сортировки не нарушают результатов предыдущих сортировок. Приведем программную реализацию алгоритма на языке С++.
#include "stdafx.h" #include <math.h> #include <iostream> using namespace std; #include <conio.h>
void shell (int *, int, int);
int main () { /* Инициализация */ int A[40]; int i,n;
cout<<"Enter n= "; cin>>n; cout<<"\n Enter array \n";
for(i=0;i<n;i++) cin>>A[i];
shell(A,n,5); //5 - начальный шаг
cout<<"Result:\n"; for(i=0;i<n;i++) cout<<" "<<A[i];
_getch(); return 0; }
void shell (int * A, int n, int k) { for (;k>=1;k--) // для каждого убывающего шага { for (int i=0;i<n;i++) // цикл по индексу массива { for (int j=i;j+k<n;j=j+k) // выполняем сортировку j+k чисел { for (int l=j+k;l<n;l=l+k) { if(A[j]>A[l]) { int X=A[j]; A[j]=A[l]; A[l]=X; } } } } cout<<"\n k="<<k; for(int v=0;v<n;v++) cout<<" "<<A[v];
cout<<"\n"; } }
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Последнее изменение этой страницы: 2021-12-15; просмотров: 32; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.23.127.197 (0.01 с.) |