Алгоритм быстрой сортировки без типа данных - PullRequest
Новая
       3

Алгоритм быстрой сортировки без типа данных

1 голос
/ 30 октября 2019

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

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

Мой вопрос, таким образом:

Вопрос: можно ли написать «Quascort Pascal Unit»который мог бы быть использован для сортировки любого массива, будь то целые числа, строки или что-то еще?

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

1 Ответ

2 голосов
/ 30 октября 2019

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

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

  • сравнить и
  • поменять

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

Чтобы сделать это, объявляется «тип функции» orderRel, который принимает два целых числа (которые считаютсяиндексы элементов матрицы для сравнения) и «тип процедуры» copierProc (также принимает два индекса и предназначен для копирования одной записи матрицы в другую. См. код ниже).

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

Вот полная реализация модуля быстрой сортировки, и вы найдете полную программу тестирования ниже. Оба были протестированы в «Free Pascal Compiler версии 3.0.4 + dfsg-18ubuntu2 [2018/08/29] для x86_64». 

{$R+}

unit Quicksort;

interface

type
  orderRel = function(i, j: longint): boolean;                (* Order relation for sorting *)
  copierProc = procedure(i, j: longint);                      (* Used to copy matrix entry i to entry j *)

procedure qsort(n: longint; less: orderRel; cp: copierProc);  (* Quicksort takes two functions as arguments *)

implementation

procedure qsort(n: longint; less: orderRel; cp: copierProc);

  var left, rght: longint;

  procedure qsort1(a, b: longint);
  begin
  cp((a+b) div 2, n+1); (* Position n+1 of the matrix used as pivot *)
  left:= a; rght:= b;
  while left <= rght do begin
    while less(left, n+1) do inc(left);
    while less(n+1, rght) do dec(rght);
    if left <= rght then begin
      cp(left, n+2); cp(rght, left); cp(n+2, rght); (* Position n+2 used as auxiliar variable for swapping *)
      inc(left); dec(rght);
      end;
    end;
  if left < b then qsort1(left, b);
  if a < rght then qsort1(a, rght);
  end;

begin
qsort1(1,n);
end;

end.

Вот тестовая программа: 

program Test; (* For testing unit quicksort *)

uses quicksort;

const
  N = 9;

(* Matrices to be sorted.  One of integers, the other of strings *)

var
  int_arr:  array[1..N+2] of integer; (* Quicksort needs two extra working slots, hence N+2 *)
  st_arr:   array[1..N+2] of string;

(* Next two subroutines to be fed to Quicksort when sorting integer matrices *)

function int_comparisson (i, j: longint): boolean;
begin
int_comparisson:= int_arr[i] < int_arr[j];
end;

procedure int_copy(i, j: longint);
begin
int_arr[j]:= int_arr[i];
end;

(* Next two subroutines to be fed to Quicksort when sorting matrices of strings *)

function st_comparisson(i, j: longint): boolean;
begin
st_comparisson:= st_arr[i] < st_arr[j];
end;

procedure st_copy(i, j: longint);
begin
st_arr[j]:= st_arr[i];
end;

var
  i: integer;

begin

(* Initialize integer matrix *)
for i:= 1 to N do int_arr[i]:= random(100);

qsort(N, @int_comparisson, @int_copy); (* Quicksort takes two functions as arguments *)

for i:= 1 to N do write(int_arr[i]:5);
writeln;

(* Initialize matrix of strings *)
st_arr[1]:= 'the';
st_arr[2]:= 'quick';
st_arr[3]:= 'brown';
st_arr[4]:= 'fox';
st_arr[5]:= 'jumps';
st_arr[6]:= 'over';
st_arr[7]:= 'the';
st_arr[8]:= 'lazy';
st_arr[9]:= 'dog';

qsort(N, @st_comparisson, @st_copy);

for i:= 1 to N do write(st_arr[i], ' '); writeln;

end.

PS: Помимо сравнения и свопинга, быстрой сортировке также необходимо хранить сводку, которая, очевидно, должна иметь тот же тип, что и другие элементы матрицы. Вместо предоставления дополнительной переменной, которая будет играть роль стержня, что неизбежно потребует раскрытия типа матрицы, решение состоит в том, чтобы разрешить быстрой сортировке доступ к одной неиспользуемой записи матрицы, скажем, записи n + 1. Еще одна запись, а именно n + 2, затем используется в качестве вспомогательной переменной для подкачки.

...