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

 

Сортировка слиянием (Merge sort).

Упорядочиваем списки (или другие структуры данных, доступ к элементам которых можно получать только последовательно, например — потоки) в определённом порядке.

Для решения задачи сортировки эти три этапа выглядят так:

1) Сортируемый  массив разбивается на две  части примерно одинакового размера; 

2) Каждая  из получившихся частей сортируется  отдельно, например — тем же  самым алгоритмом;

3) Два упорядоченных  массива половинного размера  соединяются в один. 1.1. - 2.1. Рекурсивное  разбиение задачи на меньшие  происходит до тех пор, пока  размер массива не достигнет  единицы (любой массив длины 1 можно считать упорядоченным);

3.1. Соединение  двух упорядоченных массивов  в один. Основную идею слияния  двух отсортированных массивов  можно объяснить на следующем  примере. Пусть мы имеем два  подмассива. Пусть также, элементы  подмассивов в каждом из этих  подмассивов отсортированы по  возрастанию.

3.2. Слияние  двух подмассивов в третий  результирующий массив. На каждом  шаге мы берём меньший из  двух первых элементов подмассивов  и записываем его в результирующий  массив. Счетчики номеров элементов  результирующего массива и подмассива  из которого был взят элемент  увеличиваем на 1.3. "Прицепление" остатка. Когда один из подмассивов  закончился, мы добавляем все  оставшиеся элементы второго  подмассива в результирующий  массив.

Метод оказывается крайне эффективным, однако требуется выделение дополнительной памяти.

 

 

 

 

2. Програмная реализация методов сортировки

2.1 Сортировка пузырьком

 

Задача: составить программу для возможности сортировки чисел методом пузырька и представить листинг программы.

Листинг программы:

 

const

  m = 7; {количетво элементов в массиве}

var

  msort: array[1..m] of integer; { массив}

  i, j, k: integer; {i - это шаг ,j - это под-шаг}

begin

  writeln('Введите элементы массива');

  for i := 1 to m do

    read(msort[i]);

  for i := 1 to m - 1 do

  for j := 1 to m - i do

      if msort[j] > msort[j + 1] then begin

      k := msort[j];

      msort[j] := msort[j + 1];

      msort[j + 1] := k;

     end;

  write('Отсортированный массив: ');

  for i := 1 to m do

  write(msort[i]:4);

  writeln;

  end.

Пример сортировки представлен на рисунке 3.

Рис. 3 Сортировка пузырьком.

Количество элементов в массиве можно менять, в зависимости от предпочтений. Вначале нужно ввести элементы массива (столько цифр, сколько было указано изначально), а затем программа сама отсортирует их в порядке возрастания. Время: O(n^2).

 

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

 

Задача: составить программу сортировки вставками при автоматическом рандомном выборе чисел и последующей его сортировке. Приведем листинг программы и пример использования (рисунок 4).

Листинг программы:

uses Arrays;

procedure SortByInsert(a: array of integer);

begin

  for var i:=1 to a.Length - 1 do

  begin

    var x := a[i];

    var j := i - 1;

    while (j >= 0) and (x < a[j]) do

    begin

      a[j + 1] := a[j];

      j -= 1;

    end;

    a[j + 1] := x;

  end;

end;

begin

  var a := CreateRandomIntegerArray(15);

  writeln('Исходный массив: ');

  a.Writeln;

    SortByInsert(a);

    writeln('Массив после сортировки: ');

  a.Writeln;

end.

 

Рис. 4 Сортировка вставками.

Количество элементов в массиве можно изменить на нужное, числа выбираются рандомно и автоматически сортируются методом вставок. Время: O(n^2).

3.  Быстрая сортировка

 

Задача: создать программу, позволяющую реализовать быструю сортировку, представить листинг программы и пример (рисунок 5).

Листинг программы:

uses crt;

const n=200;

var x:array[1..n] of integer;

    i:integer;

procedure sort(l,r:integer); {lлевый конец масива,r-правый конец}

var

  i,j,x1,y1,m: integer;

begin

  i:=l;

  j:=r;

  m:=round ((l+r)/2);{средний элемент}

  x1:=x[m];

  repeat

    while x[i]<x1 do inc(i);{пока левый больше среднего, подвигаем левый край вправо}

    while x[j]>x1 do dec(j);{пока правый меньше среднего, подвигаем левый вправо}

    if i<=j then {если левый и правый срослись}

     begin

      y1:=x[i];

      x[i]:=x[j];{меняем левый и правый}

      x[j]:=y1;

      inc(i); {левый вправо}

      dec(j); {правый влево}

     end;

  until i>j;{конец одной перестановки}

  if l<j then sort(l,j);{рекурсивно сортируем}

  if i<r then sort(i,r);{или левую или правую части}

end;

 begin

clrscr;

randomize;

writeln('Исходный массив:');

for i:=1 to n do

  begin

   x[i]:=random(1000);

   write(x[i]:4);

  end;

writeln;

sort(1,n);

writeln('Массив после сортировки: ');

for i:=1 to n do

write(x[i]:4);

end.

Рис. 5 Быстрая сортировка.

Программа выбирает 200 чисел рандомным путем и сортирует методом быстрой сортировки. Количество чисел можно изменить на нужное. Время: O(n log(n)).

 

3. ПРИМЕНЕНИЕ  СОРТИРОВКИ

 

Алгоритм сортировки пузырьком считается учебным и практически не применяется вне учебной литературы, вместо него на практике применяются более эффективные алгоритмы сортировки.

Самое распространенное применение сортировка нашла в таблицах Exel. Где зачастую необходимо отсортировать данные: числа по возрастанию (убыванию), буквы в алфавитном порядке и т.д.

В промышленности сортировка применяется для проверки попадания мышкой в графическом редакторе, восстановления электрических связей по геометрическим данным, сборки padstack'ов из разрозненных деталей, поиска правил (constraints), действующих между двумя заданными объектами, проверка конструкторско-технологических ограничений.

Алгоритмы сортировки имеют большое практическое применение. Их можно встретить там, где речь идет об обработке и хранении больших объемов информации (базы данных о сотрудниках, их заработной плате и т.д.). Некоторые задачи обработки данных решаются проще, если данные заранее упорядочить.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Заключение

 

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

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

Рассмотренные в данной курсовой работе методы сортировки имеют как преимущества, так и недостатки. Выбор того или иного алгоритма сортировки зависит от конкретной задачи.

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

Исходя из того, что основным критерием эффективности алгоритма сортировки является скорость, можно сделать вывод, что метод быстрой сортировки является наиболее оптимальным.

 

 

 

 

Список литературы

1. Абрамов. С.А., Зима Е.В. Начала программирования на языке Паскаль. - М.: Наука, 1987.- 112с.
2. Васюкова Н.Д., Тюяева В.В. Практикум по основам программирования. Язык Паскаль: Учеб. пособ. для учащихся средн. спец. уч. завед. М.Высшая школа, 1991.- 160с.
3. Вирт Н. Алгоритмы + структуры данных = программы: Пер. с англ. - М.: Мир, 1985. - 406 с,
4. Грогоно П. Программирование на языке Паскаль : Пер. с англ. - М.: Мир, 1982. -382с.
5. Интерактивные демонстрации по программированию [электронный ресурс].URL:      http://informatika.kspu.ru/flashprog/theory2.php?PHPSESSID=19a30358893da4665d71d4e8e1492d44 (Дата обращения: 06.12.2014г.).
6. К.Йенсен, Н.Вирт. Руководство для пользователя и описание языка Паскаль. - М.: Финансы и статистика, 1982. - 150 с.
7. Перминов О.Н. Язык программирования Паскаль. - М.: Радио и связь, 1988. - 220 с.
8. Сортировка Вставками. [электронный ресурс]. URL:  http://cppstudio.com/post/462/ (Дата обращения: 06.12.2014г.).
9. Сортировка массива. [электронный ресурс]. URL: http://edunow.su/site/content/algorithms/sortirovka_massiva (Дата обращения: 06.12.2014г.).
10. Упорядочивание массива. [электронный ресурс]. URL: http://shiva16.narod.ru/Unit14.htm (Дата обращения: 12.12.2014г.).