Блог

Главная - Вопросы по программированию - Как выполнить быструю сортировку в Ada

Как выполнить быструю сортировку в Ada

#algorithm #sorting #ada #quicksort

#алгоритм #сортировка #ada #Быстрая сортировка

Вопрос:

Как мне выполнить быструю сортировку в Ada? Мне бы также понравилась функция для ее тестирования. Я использую GPS в качестве среды IDE

Комментарии:

1. Практически так же, как вы сделали бы это на любом другом языке (хотя синтаксис массива немного удобнее).

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

3. rosettacode.org это хороший сайт для сравнения языков. это для домашней работы?

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

Ответ №1:

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

РЕДАКТИРОВАТЬ: большинство реализаций общей сортировки массива будут использовать быструю сортировку, поэтому проверьте, что вы используете, и вам, возможно, не придется внедрять свой собственный.

Ответ №2:

Вы можете получить код для быстрой сортировки по адресу http://rosettacode.org/wiki/Sorting_algorithms/Quicksort#Ada

Комментарии:

1. Если вы просто возитесь с языком и хотите посмотреть, как в нем будет выполняться быстрая сортировка (возможно, по сравнению с другими языками), Rosettacode — это то, что вам нужно.

Ответ №3:

Пример быстрой сортировки в Ada можно найти здесь . Обратите внимание, что вам понадобятся все три файла.

Комментарии:

1. Спасибо. Я попытался удалить его в IDE. я получил следующие ошибки, вы знаете, почему? Недопустимая последовательность байтов во входных данных преобразования «Element_Array» не определена «Element_Type» не определен «Index_Type» не определен

2. Не уверен, я никогда ничего не делал с Ada — я просто решил посмотреть пример, и вот что я нашел: rosettacode.org/wiki/Sorting_algorithms/Quicksort#Ada

3. -1: неполное копирование-вставка из другого источника. предоставления ссылки должно было быть достаточно. вы пропустили файл ads.

4. 1) здесь не место обсуждать ошибки, 2) без ошибок вам никто не сможет помочь, 3) вернитесь к rosettacode и прочитайте всю часть Ada. он состоит из трех файлов. GPS зависит от настроек проекта, попробуйте сначала (в командной строке).

Ответ №4:

Код

Скомпилирован на Windows 10 с GNAT GPL 2015. Преобразовано из псевдокода быстрой сортировки rosettacode.

 with Ada.Text_IO;
with Ada.Float_Text_IO;
with Ada.Strings;
with Ada.Strings.Fixed;

procedure Main is

   generic
      type Element is private;
   procedure Generic_Swap (A, B : in out Element);
   procedure Generic_Swap (A, B : in out Element) is
      Temp : constant Element := A;
   begin
      A := B;
      B := Temp;
   end;

   generic
      type Index is (<>);
      type Element is private;
      type Vector is array (Index range <>) of Element;
      with function "<" (Left, Right : Element) return Boolean is <>;
      with function ">" (Left, Right : Element) return Boolean is <>;
   procedure Generic_Quicksort (Item : in out Vector);
   procedure Generic_Quicksort (Item : in out Vector) is
      procedure Swap is new Generic_Swap (Element);
      pragma Suppress (Overflow_Check);
      pragma Suppress (Range_Check);
      Pivot : Element;
      Left : Index;
      Right : Index;
   begin
      if Item'Length > 1 then
         Pivot := Item (Item'Last); -- Choose the pivot element.
         Left := Item'First;
         Right := Item'Last;
         while Left <= Right loop
            while Item (Left) < Pivot loop
               Left := Index'Succ (Left);
            end loop;
            while Item (Right) > Pivot loop
               Right := Index'Pred (Right);
            end loop;
            if Left <= Right then
               Swap (Item (Left), Item (Right));
               Left := Index'Succ (Left);
               Right := Index'Pred (Right);
            end if;
         end loop;
         Generic_Quicksort (Item (Item'First .. Right));
         Generic_Quicksort (Item (Left .. Item'Last));
      end if;
   end;

   type Planet is (Mercury, Venus, Earth, Mars, Jupiter, Saturn, Uranus, Neptune, Pluto);
   type Planet_Season_Array is array (Planet range <>) of Float;
   procedure Sort is new Generic_Quicksort (Planet, Float, Planet_Season_Array);
   procedure Put (Item : Planet_Season_Array) is
      use Ada.Text_IO;
      use Ada.Float_Text_IO;
      use Ada.Strings.Fixed;
   begin
      for I in Item'Range loop
         Put (Tail (I'Img, Planet'Width));
         Put (Item (I), 2, 2, 0);
         New_Line;
      end loop;
      New_Line;
   end;

   Item : Planet_Season_Array (Planet) := (0.8, 0.1, 0.4, 0.9, 0.0, 0.7, 0.5, 0.3, 0.7);

begin
   Put (Item);
   Sort (Item);
   Put (Item);
end;

Вывод

 MERCURY 0.80
  VENUS 0.10
  EARTH 0.40
   MARS 0.90
JUPITER 0.00
 SATURN 0.70
 URANUS 0.50
NEPTUNE 0.30
  PLUTO 0.70

MERCURY 0.00
  VENUS 0.10
  EARTH 0.30
   MARS 0.40
JUPITER 0.50
 SATURN 0.70
 URANUS 0.70
NEPTUNE 0.80
  PLUTO 0.90