Сортировка массива вставками паскаль

Сортировка массива вставками паскаль

Алгоритмы сортировки массивов

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

Для переменных символьного типа понятия "возрастание" и "убывание" относятся к значениям машинного кода, используемого для представления символов в памяти компьютера. Так как все буквенные символы располагаются в таблице кодов по алфавиту, то сортировка слов текста всегда приводит к их упорядочению в алфавитной последовательности.

Существует много алгоритмов, обеспечивающих решение задачи сортировки. Наиболее известными являются следующие:
— метод сортировки обменами ("пузырьковая" сортировка);
— метод сортировки вставками;
— метод сортировки выбором элемента;

Алгоритмы и программы сортировки

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

Procedure Puzirek;
Var i, j: Integer;
y:Integer;
Begin
For i := 2 to n do
For j := n downto i do
If X[j-1] > X[j] then begin y:=X[j-1];
X[j-1]:=X[j];
X[j]:=y
end;
End;

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

Procedure Vstavka;
Var Z, Y, i, j: Integer;
Begin
For i := 2 to n do
For j := 1 to i-1 do
If X[j] > X[i] then
begin
Z := X[i];
For Y := i downto j+1 do X[Y] := X[Y-1];
X[j] := Z
end
End;

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

Читайте также:  Сглаживание гамма коррекция это

Procedure Vibor;
Var r, i, j: Integer;
Begin
For i := 1 to n-1 do
begin
r := i;
For j := i+1 to n do If a[r] > a[j] then r := j;
Y:=a[r]; a[r]:=a[i]; a[i]:=Y;
end
End;

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

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

  • количество присваиваний;
  • количество сравнений.

Все методы сортировки можно разделить на две большие группы:

  • прямые методы сортировки;
  • улучшенные методы сортировки.

Прямые методы сортировки по принципу, лежащему в основе метода, в свою очередь разделяются на три подгруппы:

  1. сортировка вставкой (включением);
  2. сортировка выбором (выделением);
  3. сортировка обменом (так называемая "пузырьковая" сортировка).

Улучшенные методы сортировки основываются на тех же принципах, что и прямые, но используют некоторые оригинальные идеи для ускорения процесса

Рассмотрим сортировку методом вставки.

Принцип метода заключается в следующем:

Массив разделяется на две части: отсортированную и не отсортированную. элементы из не отсортированной части поочередно выбираются и вставляются в отсортированную часть так, чтобы не нарушить в ней упорядоченность элементов. В начале работы алгоритма в качестве отсортированной части массива принимают только первый элемент, а в качестве не отсортированной — все остальные элементы.

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

    взятие очередного i-го не отсортированного элемента и сохранение его в дополнительной переменной;

поиск позиции j в отсортированной части массива, в которой присутствие взятого элемента не нарушит упорядоченности элементов;

сдвиг элементов массива от i-го до j-1-го вправо, чтобы освободить найденную позицию вставки;

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

    Рассмотрите процедуру, реализующую выше рассмотренный алгоритм:

    Procedure Vstavka(Var a : Array1);
    Var
    i, j,e,g:integer;
    Begin
    for i:=2 to c do
    begin
    e:=A[i];
    j:=1;
    while (e>a[j]) do
    Inc(j);
    for g:=i-1 downto j do
    a[g+1]:=a[g];
    a[j]:=e;
    end;
    End;
    Читайте также:  Антивирус для мобильных устройств

    Задание. Составьте программу сортировки одномерного массива рассмотренным методом.

    Находим (выбираем) в массиве элемент с минимальным значением на интервале от 1-го элемента до n-го (последнего) элемента и меняем его местами с первым элементом. На втором шаге находим элемент с минимальным значением на интервале от 2-го до n-го элемента и меняем его местами со вторым элементом. И так далее для всех элементов до n-1-го.

    Рассмотрите схему алгоритма прямого выбора.

    Рассмотрите процедуру, реализующую выше рассмотренный алгоритм:

    Procedure Vibor(Var a: Array1);
    Var
    i, j, Min, MinI : integer;
    Begin
    for i:=1 to c do
    begin
    Min:=a[i];
    MinI:=i;
    for j:=i+1 to c do
    if a[j]

    Задание. Составьте программу сортировки одномерного массива рассмотренным методом.

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

    • количество шагов алгоритма, необходимых для упорядочения;
    • количество сравнений элементов;
    • количество перестановок, выполняемых при сортировке.

    Мы рассмотрим только три простейшие схемы сортировки.

    Метод "пузырька"

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

    В результате наибольший элемент оказывается в самом верху массива.

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

    Заметим, что при втором и последующих проходах, нет необходимости рассматривать ранее "всплывшие" элементы, т.к. они заведомо больше оставшихся. Другими словами, во время j -го прохода не проверяются элементы, стоящие на позициях выше j .

    Теперь можно привести текст программы упорядочения массива M[1..N] :

    begin
    for j :=1 to N -1 do
    for i :=1 to N — j do
    if M[ i ] > M[ i +1] then
    swap (M[ i ],M[ i +1])
    end;

    Стандартная процедура swap будет использоваться и в остальных алгоритмах сортировки для перестановки элементов (их тип мы уточнять не будем) местами:

    procedure swap (var x,y: . );
    var t: . ;
    begin
    t := x;
    x := y;
    y := t
    end;

    Заметим, что если массив M — глобальный, то процедура могла бы содержать только аргументы (а не результаты). Кроме того, учитывая специфику ее применения в данном алгоритме, можно свести число парметров к одному (какому?), а не двум.

    Читайте также:  Tomtom com getstarted обновить карты бесплатно

    Применение метода "пузырька" можно проследить здесь.

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

    Второй метод называется метод вставок ., т.к. на j -ом этапе мы "вставляем" j -ый элемент M[j] в нужную позицию среди элементов M[1] , M[2] ,. . ., M[j-1] , которые уже упорядочены. После этой вставки первые j элементов массива M будут упорядочены.
    Сказанное можно записать следующим образом:

    Чтобы сделать процесс перемещения элемента M[j] , более простым, полезно воспользоваться барьером: ввести "фиктивный" элемент M[0] , чье значение будет заведомо меньше значения любого из "реальных"элементов массива (как это можно сделать?). Мы обозначим это значение через —оо.

    Если барьер не использовать, то перед вставкой M[j] , в позицию i-1 надо проверить, не будет ли i=1 . Если нет, тогда сравнить M[j] ( который в этот момент будет находиться в позиции i ) с элементом M[i-1].

    Описанный алгоритм имеет следующий вид:

    begin
    M[0] := -oo;
    for j :=2 to N do
    begin
    i := j ;
    while M[ i ] M[ i — 1] do
    begin
    swap (M[ i ],M[ i -1]);
    i := i -1
    end
    end
    end;

    Процедура swap нам уже встречалась.

    Сортировка посредством выбора

    Идея сортировки с помощью выбора не сложнее двух предыдущих. На j -ом этапе выбирается элемент наименьший среди M[j] , M[j+1] ,. . ., M[N] (см. процедуру FindMin ) и меняется местами с элементом M[j] . В результате после j -го этапа все элементы M[j] , M[j+1] ,. . ., M[N] будут упорядочены.

    Сказанное можно описать следующим образом:

    нц для j от 1 до N-1
    выбрать среди M[j] ,. . ., M[N] наименьший элемент и
    поменять его местами с
    M[j]
    кц

    begin
    for j :=1 to N -1 do
    begin
    FindMin ( j , i );
    swap (M[ j ],M[ i ])
    end
    end;

    В программе, как уже было сказано, используется процедура FindMin , вычисляющая индекс lowindex элемента, наименьшего среди элементов массива с индексами не меньше, чем startindex :

    procedure FindMin (start index : integer; var lowindex : integer );
    var lowelem: . ;
    u: integer;
    begin
    lowindex := start index ;
    lowelem := M[startindex];
    for u:= start index +1 to N do
    if M[u] lowelem then
    begin
    lowelem := M[u];
    lowindex := u
    end
    end;

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

    Ссылка на основную публикацию
    Создать новую электронную почту на яндексе бесплатно
    Всем привет! С вами снова я, Алексей. В этом посте я расскажу вам о том, как создать электронную почту на...
    Сколько человек сидит в одноклассниках
    Mail.Ru Group исследовала и сравнила аудитории самых популярных в России социальных сетей — «Одноклассники», «Мой Мир», «ВКонтакте», Facebook и Twitter....
    Сколько четырехзначных чисел можно составить из нечетных
    Условие Решение 1 Решение 2 Решение 3 Поиск в решебнике Популярные решебники Издатель: Н. Я. Виленкин, В. И. Жохов, А....
    Создать канал на ютубе регистрация бесплатно
    Добрый день, уважаемые читатели и гости моего блога! Если вы попали на эту статью, значит хотите узнать, как зарегистрироваться в...
    Adblock detector