Форум программистов, компьютерный форум, киберфорум
Delphi для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/13: Рейтинг темы: голосов - 13, средняя оценка - 5.00
0 / 0 / 1
Регистрация: 10.12.2012
Сообщений: 26
1

Алгоритмы сортировки Delphi в массивах с оценкой времени

24.12.2013, 11:03. Показов 2546. Ответов 1
Метки нет (Все метки)

Добрый день!
Выполняю лабораторные работы по алгоритмам сортировки. Рассматривается 3 алгоритма: пузырьковая сортировка (bubble sort), сортировка вставками (insertion sort), быстрая сортировка (quick sort). Вся проблема в том, что указанные способы необходимо применить в предложенной преподавателем программе. Программа содержит несколько тестов для расчета времени выполнения алгоритма в заданном массиве. Вот с пузырьковой сортировкой я все понял. А как прицепить к этой программе две остальные, не пойму.
Вот код для быстрой сортировки:
Delphi
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
procedure QuickSort (var A: array of Integer; Left, Right: Integer);
var
  i, j: Integer;
  Middle, t: Integer;
begin
  repeat
    i:= Left;
    j:= Right;
    Middle:= A[(Left + Right) div 2];
    repeat
      while A[i] < Middle do
        Inc (i);
      while A[j] > Middle do
        Dec (j);
      if i <= j then
      begin
        t:= A[i];
        A[i]:= A[j];
        A[j]:= t;
        Inc (i);
        Dec (j);
      end;
    until i > j;
    if Left < j then
      QuickSort (A, Left, j);
    Left:= i;
  until i >= Right;
end;
Для сортировки вставками есть следующее словесно-формульное описание :
СОРТИРОВКА МАССИВА ВСТАВКАМИ.
Входные данные: A = a0, a1, a2, …, aN–1 – сортируемый массив;
Op(x, y) – бинарный предикат упорядочивания, если Op(ai, aj) = true, тогда считается что элементы ai и aj упорядочены верно;
Промежуточные данные: i, j – счетчики обработанных элементов
t – выбранный элемент
Выходные данные: A – массив, для которого Op(ai, aj) = true при любых i, j
1. Будем последовательно выбирать элементы массива A и искать позицию для вставки этого элемента. Считаем, что первый элемент уже находится в правильной позиции, если это не так, то последующая часть алгоритма его обработает, таким образом, начинаем перебор элементов массива со второго,
i = 1
2. Проверяем, все ли элементы упорядочены (i = N), если да, то завершаем работу
3. Выбираем i-тый элемент
t = ai
4. Ищем позицию для вставки элемента и создаем там «пустое пространст-во», для этого начиная с предыдущего по отношению к выбранному элементу (i – 1) сдвигаем все элементы вправо до тех пор пока либо не достигнем начала массива, либо не найдем позицию для вставки
j = i – 1
5. Если j > 0 и Op (aj, t) = false, то сдвигаем элемент aj вправо
aj+1 = aj
уменьшаем счетчик j,
j = j – 1
и повторяем шаг 5
6. Вставляем текущий элемент t в найденную позицию j
a j = t
7. Увеличиваем счетчик обработанных элементов i, и повторяем действия ал-горитма, начиная с шага 2

Написал следующий алгоритм, правда есть сомнения относительно его правильности:
Delphi
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Program InsertionSort (var A: array of Integer; Op: TBinaryPredicate);
var
  i, j: Integer;
  t: Integer;
Begin
for i:=1 to t do
begin
j:=i;
while (j>1) and (A[j-1]>A[i]) do
begin
A[j]:=A[j-1];
j:=j-1;
end;
A[j]:=A[i];
end;
Очень прошу помочь с реализацией этих двух алгоритмов сортировки в прикрепленной программе!
Вложения
Тип файла: zip Приложение к ЛР№4.zip (37.5 Кб, 8 просмотров)
__________________
Помощь в написании контрольных, курсовых и дипломных работ здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
24.12.2013, 11:03
Ответы с готовыми решениями:

Алгоритмы поиска и сортировки в массивах
Здравствуйте форумчане помогите решить вот такое задание:В массиве содержится не менее 10 записей...

Алгоритмы поиска и сортировки в одномерных массивах символов
Сколько раз у заданном предложении встречаются слова &quot;КСМ&quot; и &quot;СКС&quot; ?

Написать две функции сортировки массива целых чисел, реализующих заданные алгоритмы сортировки – один из класса квадрат
#include &lt;stdio.h&gt; #include &quot;stdafx.h&quot; #include &quot;iostream&quot; #include &lt;stdlib.h&gt; #include...

Алгоритмы сортировки массивов.Реализуйте алгоритмы сортировок данных массивов
Задания к лабораторной работе. Выполните приведенные ниже задания. 1. Даны два целочисленных...

1
0 / 0 / 1
Регистрация: 10.12.2012
Сообщений: 26
24.12.2013, 18:55  [ТС] 2
Ну в общем исправил я код для сортировки вставкой. Вроде даже работает. Правда как-то очень уж быстро по-моему. Вот код, надеюсь на этот раз верный
Delphi
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
procedure InsertionSort (var A: array of Integer; Op: TBinaryPredicate);
  var
  i, j: Integer;
  t: Integer;
begin
  i := 1 ;
  for i:=Low(A) to High(A) do
  begin
 t:=A[i];
 j:=i-1;
 while (j>=0) and (Op (A[j], t) = false) do
begin
  A[i]:=A[i+1];
  j:=j-1;
end;
  A[j]:=t;
 
end;
i:=i+1;
end;
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
24.12.2013, 18:55

Сортировки в одномерных массивах
Преобразовать одномерный массив, состоящий из n вещественных элементов , таким обозримом , чтобы...

Программа сортировки текстовых значений в массивах через InputBox
Всем добрый день (вечер/etc) Вновь имею проблемы с кодом. Если коротко: Необходимо в text1...

Алгоритмы сортировки
Используя сортировку слиянием, «быструю» сортировку, пирамидальную сортировку и сортировку...

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


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru