Методы сортировки массива


	1 занятие Сортировка массива. Способы сортировки массива. 2 занятие Сортировка вставкой. Сортировка выбором. 3 занятие Сортировка методом простого обмена. Рекурсивная сортировка. 4 занятие Сортировка методом слияний. 5 занятие Самостоятельное решение задач.

О проекте


	— Сертификат — Рецензии и отзывы

Преподавателям


	— Пояснительная записка — Учебно-тематический план — Программа курса — Содержание курса — Требования к уровню подготовки обучающихся

Тема: Сортировка вставкой. Сортировка выбором.

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

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

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

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

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

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

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

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

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

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

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

Таким образом, алгоритм будет состоять из (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]<Min
          then
            begin
              Min:=a[j];
              MinI:=j;
            end;
      a[MinI]:=a[i];
      a[i]:=Min;
    end;
End;

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

Вернуться назад

Проект «Pascaler» — лучший на ХI Всероссийской конференции молодых исследователей с международным участием «Шаг в будущее», Россия, Москва, 12 – 16 апреля 2004г.