Преобразование HeapSort и ShellSort из C в Pascal - PullRequest
Новая
       30

Преобразование HeapSort и ShellSort из C в Pascal

1 голос
/ 18 марта 2020

У меня проблема с двумя видами сортировки - Heap и Shell. У меня есть некоторый код в C, и мне нужно попробовать использовать те же команды (например, когда я использую в C a 'for-l oop', я хочу использовать 'for-l oop' для Pascal также) в органах процедур. Я пытаюсь, но сортировки не работают, как в C. В C все отлично работает с массивами размером 40000.

Код для ShellSort в C, где параметр 'n' - это размер массива: 

    shellSort(int n){
      int shift,pom,j,i;
      shift = n/2;
      while(shifta>0){
        for (i = shift; i < n; i += 1){
            pom=arr[i];
            j=i;
            while((j>=shift) && (arr[j-shift]>pom)){
                arr[j] = arr[j - shift]; 
                j=j-shift;
            }
            arr[j]=pom;
        }
        shift= shift / 2;
      }
   }

Объявление в Pascal

  arr :array[0..22] of integer;       
  size:integer =23;

Код в Pascal с теми же параметрами: 

procedure ShellSort(n:integer); 
Var
 shift , pom : Integer;
Begin
  shift:=n div 2 ; 
  While shift>0 Do
    Begin
      For i:=shift to n Do
        Begin
          pom:=arr[i];
          j:=i;
          While (j>=shift) and (arr[j-shift]>pom) Do
            Begin
              arr[j]:=arr[j-shift];
              j:= j-shift
            End;
            arr[j]:=pom;
        End;
        shift:=shift div 2;
    End;
End;

Код для сортировки кучи в C: 

heapSort() {
    int N = size;
    int k;
    int pom;
    for (k = N / 2; k > 0; k--) {
        downHeap(k, N);
    }
    do {
        pom = arr[0];
        arr[0] = arr[N - 1];
        arr[N - 1] =  pom;
        N = N - 1;
        downHeap(1, N);
    } while (N > 1);

}

downHeap(int k, int N) {
    int T = arr[k - 1];
    while (k <= N / 2) {
        int j = k + k;

        if ((j < N) && (arr[j - 1] < arr[j])) {
            j++;
        }
        if (T >= arr[j - 1]) {
            break;
        } else {
            arr[k - 1] = arr[j - 1];
            k = j;
        }
    }
    arr[k - 1] = T;
}

Код для сортировки кучи в Pascal: 

procedure downHeap(k:integer;N:integer);
var
  T:integer;
begin
  T:=arr[k-1];
  while(k<= (N div 2)) do
    begin
      j:=k+k;
      if ((j<N) and (arr[j-1]<arr[j])) then
        begin
          j:=j+1;
        end;
      if (T>=arr[j-1]) then
        begin
          exit;
        end
      else
        begin
          arr[k-1]:=arr[j-1];
          k:=j;
        end;
    end;
    arr[k-1]:=T;
end;

procedure heapSort;
var
  n, pom:integer;
begin
  n:=size;
  for i:=n div 2 downto 1 do
    begin
      downHeap(i,n);
    end;
  repeat
    begin
      pom:=arr[0];
      arr[0]:=arr[n-1];
      arr[n-1]:=pom;
      n:=n-1;
      downHeap(1,n);
   end;
  until n>1;
end;

Вывод из Pascal: 

Unsorted array
10 9 8 7 6 5 4 3 3 2 1 0 15 15 15 15 14 18 99 1 19 95 95

BubbleSort
0 1 1 2 3 3 4 5 6 7 8 9 10 14 15 15 15 15 18 19 95 95 99

HeapSort
95 95 15 18 95 15 15 15 18 19 95 0 5 4 15 3 14 7 3 1 2 1 99

ShellSort
0 0 1 1 2 3 3 4 5 7 14 15 15 15 15 15 18 18 19 95 95 95 95

Expected
0 1 1 2 3 3 4 5 6 7 8 9 10 14 15 15 15 15 18 19 95 95 99

Я действительно подавлен.

1 Ответ

1 голос
/ 18 марта 2020

Передача комментариев в ответ.

В сортировке оболочки C l oop: 

for (i = shift; i < n; i += 1){

и Pascal l oop равно 

For i:=shift to n Do

Pascal l oop зацикливается слишком часто; оно должно быть: 

For i := shift to n-1 Do

при условии, что выражения допускаются в пределах l oop - если нет, вам нужна дополнительная переменная, примерно такая: 

var ub: integer;
ub := n - 1;

For i := shift to ub Do

C для l oop гораздо более общий и гибкий, чем Pascal для l oop.

В сортировке Heap C l oop: 

do { … } while (N > 1);

и вы перевели это на 

repeat … until n > 1;

Условие завершения неверно; until эквивалентно while not, поэтому вам необходимо: 

repeat … until n <= 1;

Я ни в коем случае не изучил весь код Pascal - и у меня нет компилятора Pascal для тестирования - так что могут быть и другие проблемы, которые еще предстоит решить, но эти два должны помочь вам. (Убедитесь, что вы проверили все вхождения for и repeat … until на наличие проблем, описанных здесь.)

...