admin / 06.10.2018

Класс TList. Delphi для профессионалов. Списки и коллекции

Delphi для профессионалов. Списки и коллекции

Класс TList

Основой класса TList является список указателей. Сам список представляет собой динамический массив указателей, к которому можно обратиться через индексированное свойство

property Items[Index: Integer]: Pointer;

Нумерация элементов начинается с нуля.

Прямой доступ к элементам массива возможен через свойство

type

PPointerList = ^TPointerList;

TPointerList = array[0..MaxListSize-1] of Pointer;

 property List: PPointerList;

которое имеет атрибут "только для чтения".

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

 Примечание

В списке могут содержаться указатели на разнородные структуры. Не обязательно хранить в списке только указатели на объекты или указатели на записи.

Реализованные в классе TList операции со списком обеспечивают потребности разработчика и совпадают с операциями списка строк.

Для добавления в конец списка нового указателя используется метод

function Add(Item: Pointer): Integer;

Прямое присваивание значения элементу, который еще не создан при помощи метода Add, вызовет ошибку времени выполнения.

Новый указатель можно добавить в нужное место списка. Для этого используется метод

procedure Insert(Index: Integer; Item: Pointer);

В параметре index указывается необходимый порядковый номер в списке.

Перенос существующего элемента на новое места осуществляется методом

procedure Move(Curlndex, Newlndex: Integer);

Параметр CurIndex определяет старое положение указателя. Параметр NewIndex задает новое его положение.

Также можно поменять местами два элемента, определяемые параметрами Indexl и Index2:

procedure Exchange(Indexl, Index2: Integer);

Для удаления указателей из списка используются два метода. Если известен индекс, применяется метод

procedure Delete(Index: Integer);

Если известен сам указатель, используется метод

function Remove(Item: Pointer): Integer;

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

function Expand: TList;

Для того чтобы метод сработал, необходимо, чтобы count = Capacity. Алгоритм работы метода представлен в табл. 7.1.

Таблица 7.1. Алгоритм увеличения памяти списка

Значение свойства Capacity

На сколько увеличится свойство Capacity

Метод

procedure Clear; dynamic;

используется для удаления всех элементов списка сразу. Для поиска указателя по его значению используется метод

function IndexOf(Item: Pointer): Integer;

Метод возвращает индекс найденного элемента в списке. При неудачном поиске возвращается — 1.

Для сортировки элементов списка применяется метод

type TListSortCompare = function (Iteml, Item2: Pointer): Integer;

 procedure Sort(Compare: TListSortCompare);

Так как состав структуры, на которую указывает элемент списка, невозможно заранее обобщить, разработка процедуры, осуществляющей сортировку, возлагается на программиста. Метод Sort лишь обеспечивает попарное сравнение указателей на основе созданного программистом алгоритма (пример сортировки см. выше в разд. "Класс TStringList").

Полностью все свойства и методы класса TList представлены в табл. 7.2.

Таблица 7.2. Свойства и методы класса TList

property Capacity: Integer;

Определяет число строк, для которых выделена память

Возвращает число строк в списке

property Items [Index: Integer]: Pointer;

type

TPointerList = array [0 . .MaxListSize-i ] of Pointer;

PPointerList = ATPointerList; property List: PPointerList;

Динамический массив указателей

function Add (Item: Pointer): Integer;

Добавляет к списку новый указатель

procedure Clear; dynamic;

procedure Delete (Index: Integer:;

Удаляет указатель с индексом

Index

class procedure Error (const Ksg: string; Data: Integer); virtual;

Генерирует исключительную

Ситуацию EListError.

Сообщение об ошибке создается из форматирующей строки Msg и числового параметра Data

procedure Exchange (Indexl, Index2: Integer);

Меняет местами указатели с индексами Indexl и Index2

Увеличивает размер памяти, отведенной под список

Возвращает первый указатель из списка

function IndexOf (Item: Pointer): Integer;

Возвращает индекс указателя, заданного параметром Item

procedure Insert (Index: Integer; Item: Pointer) ;

Вставляет новый элемент Items позицию Index

Возвращает последний указатель в списке

procedure Move (Curlndex, Newlndex: Integer);

Перемещает элемент списка на новое место

Удаляет из списка все пустые (Nil) указатели

function Remove (Item: Pointer): Integer;

Удаляет из списка указатель

Item

type TListSortCompare = function (Iteml, Item2 : Pointer): Integer;

procedure Sort (Compare: TListSortCompare);

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

 

 

Знаете ли Вы, что диаграмма развертывания, Диаграмма применения, Диаграмма размещения Deployment diagram — это метод объектно-ориентированного проектирования, отображающий физические взаимосвязи между программными и аппаратными компонентами системы.

Основы Delphi
TList
Тип
Универсальный контейнер списков объектов Classes unit
Описание
Класс TList очень полезный универсальный контейнер списков. Он отличается от массивов, в которых он обеспечивает более богатые функциональные возможности.

В частности объекты TList могут быть отсортированы. Эта сортировка может быть с использованием любых выбранных критериев. Например, список может содержать набор объектов, которые имеют строку и численные поля. Вы можете отсортировать список по строке, по числу, по обоим, с возрастанием или убыванием, как Вы желаете. И пересортировать позже по другим критериям.

Показанный пример кода показывает такую сортировку.

Ключевые свойства и методы упомянуты ниже.

Свойство Capacity

Используется для установления размера (число указателей на объекты) списка. Предварительно установив в разумное значение, можно избежать множественных перераспределений памяти.

Свойство Count

Число элементов (указателей) в списке. Может быть прочитано или записано. Если размер уменьшен в результате изменения значения Count, то удаляются элементы в конце списка.

Свойство Items

Позволяет обращаться к элементам в списке. Например, myList.Items[2] ; возвращает 3-ий элемент в списке.

Delphi TList записей

Это свойство, заданное по умолчанию, вышеупомянутое может быть упрощено до myList[2];.

Свойство List

Возвращает элементы в массиве.

Метод Add

Добавляет элемент в конец списока.

Метод Assign

Заменяет список содержанием другого списка.

Метод Clear

Удаляет все элементы списка, устанавливая Count в 0.

Метод Delete

Удаляет элемент из списка по его позиции в списке.

Метод Remove

Удаляет элемент из списка по его объектному указателю.

Метод Exchange

Меняет позиции двух элементов

Метод Move

Перемещает элемент в новую позицию списка.

Метод Insert

Вставляет новый элемент в список в данную позицию.
Метод First

Получает первый элемент в списке.

Метод Last

Получает последний элемент в списке.

Метод Sort

Сортирует список в соответствии с вашими указанными критериями. Сортировка списка проводится внутри TList, но каждая пара элемента сравнивается, вызывая функцию, которую вы указали для этого метода.

Метод IndexOf

Выдает позицию указанного объекта в списке.

Примечания
Вы можете добавить Nil указатели в список. Delphi добавляет Nil указатели, когда Вы устанавливаете свойство Count выше чем текущий номер элемента в списке.
Похожие команды
TStringList  Содержит список переменной длины, состоящий из строк

Array  Тип данных содержащий индексируемую коллекцию данных

 
Пример кода : Создание, присвоение, сортировка, и переделывание списка
unit Unit1;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, StdCtrls;

type
  // Определение класса клиента
  TCustomer = class
    private
      // Поля данных этого нового класса
      CustomerName   : String;
      CustomerNumber : Integer;

    public
      // Свойства для чтения значений этих данных
      property Name : String
          read CustomerName;
      property Number : Integer
          read CustomerNumber;

      // Коструктрор
      constructor Create(const CustomerName   : String;
                         const CustomerNumber : Integer);
  end;

  // Определение класса формы
  TForm1 = class(TForm)
    procedure FormCreate(Sender: TObject);

  private
    // TList объект мы использует в этом коде
    myList : TList;

    // Метод для показа содержимого нашего объекта списка
    procedure ShowListContents;

  public

  end;

var
  Form1: TForm1;

implementation

{$R *.dfm}

// Конструктор Customer
// —————————————————————————
constructor TCustomer.Create(const CustomerName   : String;
                             const CustomerNumber : Integer);
begin
  // Сохранение переданных параметров
  self.CustomerName   := CustomerName;
  self.CustomerNumber := CustomerNumber;
end;

// Программа сортировки TList : сравните клиентов по имени
// —————————————————————————
// Возвращенное целое число имеет следующее значение :
//
//   > 0 : (положительное) Item1 является меньше чем Item2
//     0 : Item1 равно Item2
//  
function compareByName(Item1 : Pointer; Item2 : Pointer) : Integer;
var
  customer1, customer2 : TCustomer;
begin
  customer1 := TCustomer(Item1);
  customer2 := TCustomer(Item2);

  // Теперь сравнение строк
  if      customer1.Name > customer2.Name
  then Result := 1
  else if customer1.Name = customer2.Name
  then Result := 0
  else Result := -1;
end;

// Подпрограмма для показа содержимого нашего списка
// —————————————————————————
procedure TForm1.ShowListContents;
var
  i : Integer;
begin
  // И повторный показ списка
  for i := 0 to myList.Count-1 do
  begin
    ShowMessage(TCustomer(myList[i]).Name+’ is customer number ‘+
                IntToStr(TCustomer(myList[i]).Number));
  end;
end;

// Конструктор формы
// —————————————————————————
procedure TForm1.FormCreate(Sender: TObject);
var
  customer : TCustomer;

begin
  // Создание объекта TList для хранения набора объектов клиент
  myList := TList.Create;

  // Создание нескольких объектов клиентов и добавление их в наш объект список
  customer := TCustomer.Create(‘Neil Moffatt’, 123);
  myList.Add(customer);
  customer := TCustomer.Create(‘Bill Gates’, 64);
  myList.Add(customer);

  // Мы можем добавить объект, не присваивая в промежуточную переменную
  myList.Add(TCustomer.Create(‘Henry Cooper’, 999));
  myList.Add(TCustomer.Create(‘Alan Sugar’, 2));

  // Теперь показываем список
  ShowListContents;

  // Теперь мы сортируем список в последовательность имён и повторяем показ
  myList.Sort(compareByName);
  ShowListContents;

  // Теперь удаляем и вставляем некоторые объекты
  // Обратите внимание, что индексы начинаются с 0
  myList.Insert(2, TCustomer.Create(‘Added as item 3’, 33));
  myList.Delete(4);

  // И повторно показываем список
  ShowListContents;
end;

end.

Neil Moffatt является клиентом с номером 123
Bill Gates является клиентом с номером 64
Henry Cooper является клиентом с номером 999
Alan Sugar является клиентом с номером 2

Alan Sugar является клиентом с номером 2
Bill Gates является клиентом с номером 64
Henry Cooper является клиентом с номером 999
Neil Moffatt является клиентом с номером 123

Alan Sugar является клиентом с номером 2
Bill Gates является клиентом с номером 64
Added Добавленный как 3 элемент является клиентом с номером 33
Henry Cooper является клиентом с номером 999

 

.

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

  • У нас есть библиотека в которой много интересных примеров кода на различных языках программирования.

Обобщенные интерфейсы в Delphi

Большинство примеров использования дженериков в Delphi используют класс с дженерик-типом. Однако, работая над своим проектом, я решил, что мне нужен интерфейс с дженерик-типом.

В проекте используется встроенный механизм издатель-подписчик. Я захотел чтобы подписчик имел для каждого типа события отдельный метод Receive, а не отдельный метод с огромным case-выражением, выбирающим действие для каждого типа события. Также я не хотел определять интерфейс для каждого типа события. Мне был нужен дженерик интерфейс подписчика, который получает тип события, как параметр.

Однако, я понятия не имел, могу ли я определить дженерик интерфейс, не говоря уже о реализации. Даже если предположить, что я могу сделать это, сможет ли Delphi выбрать правильный метод Receive для вызова? Есть только один способ узнать…

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

Класс TList — списки

О других частях я расскажу в своих следующих сообщениях.

Сперва я описал несколько простых событий. Их содержание не так интересно:

TSomeEvent = class // other stuff end; TSomeOtherEvent = class // other stuff end;

Затем, я определил дженерик интерфейс

ISubscriber<T> = interface procedure Receive(Event : T); end;

Этот интерфейс должен быть реализован подписчиками для получения событий разного типа. Заметьте, тип событий записан как джененрик тип T.

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

TMySubscribingObject = class(TInterfacedObject, ISubscriber<TSomeEvent>, ISubscriber<TSomeOtherEvent>) protected procedure Receive(Event : TSomeEvent); overload; procedure Receive(Event : TSomeOtherEvent); overload; end;

Здесь нет описания интерфейсов ISomeEventSubscriber и ISomeOtherEventSubscriber, мы можем просто использовать ISubscriber<T> и передать тип на месте. Для этого нужно реализовать обязательно перегруженный метод Receive.

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

И это работает? С первой попытки — нет, не получилось. Независимо от того, какой тип события и через какой интерфейс я передавал, всегда выполнялся последний метод Receive.

dunit_generic_interfaces Жизненное правило №37: Если речь идет о выборе между запутывающимся Малькольм и разработчиками компилятора Delphi, вероятно, это ошибка Малькольма.

Да, моя ошибка. Барри Келли указал на ошибки моего подхода. Я описал дженерик интерфейс с GUID. Привычка. Это означает, что ISubscriber<TSomeEvent> и ISubscriber<TSomeOtherEvent>, и любые другие интерфейсы определенные с этого дженерика будут иметь одинаковые GUID. Вместе с использованием оператора "as" для получения ссылки из экземпляра TMySubscribingObject, это путало Delphi и заставляло всегда возвращать одну и туже ссылку на интерфейс.

Удалил GUID и "as" — все заработало замечательно.

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

Источник: http://habrahabr.ru

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

Program RadixSort;  
Var A,B : array[1..1000] of word;  
N,i : integer;  
t : longint;  
Procedure Sort; {сортировка подсчетом}  
Var C : array[0..9] of integer;  
j : integer;  
Begin  
For j:=0 to 9 do  
C[j]:=0;  
For j:=1 to N do  
C[(A[j] mod (t*10)) div t]:= C[(A[j] mod (t*10)) div t]+1;  
For j:=1 to 9 do  
C[j]:=C[j-1]+C[j];  
For j:=N downto 1 do  
begin  
B[C[(A[j] mod (t*10)) div t]]:=A[j];  
C[(A[j] mod (t*10)) div t] := C[(A[j] mod (t*10)) div t]-1;  
end;  
End;  
Begin  
{Определение размера массива A (N) и его заполнение}  
…  
{сортировка данных}  
t:=1;  
for i:=1 to 5 do  
begin  
Sort;  
A:=B;  
t:= t*10;  
end;  
{Вывод массива A}  
…  
End.

   Так как сортировка подсчетом вызывается константное число раз, то время работы всей сортировки есть O(n). Заметим, что таким способом можно сортировать не только числа, но и строки, если же использовать сортировку слиянием в качестве устойчивой, то можно сортировать объекты по нескольким полям.

   Теперь вы владеете достаточным арсеналом, чтобы сортировать все что угодно и как угодно. Помните, что выбор нужной вам сортировки зависит от того, какие данные вы будете сортировать и где вы их будете сортировать.
   P.S. Все программы рабочие — если, конечно, вам не лень будет заменить три точки на код ввода и вывода массивов :-).

лгоритмы  Сортировки. Часть 1

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

Однако, следует отметить что изучение алгоритмов совсем не лёгкая задача, здесь требуется внимательное рассмотрение каждой строчки. Конечно если Вы воспользуетесь кнопками Ctrl+C и Ctrl+V Ваша программа не станет хуже работать, но на мой взгляд, нет ничего хуже когда программист сам до конца не понимает, как работает его программа.

Итак, начнём.

Сортировка выбором

И начнём мы с  сортировки выбором. Хотя этот алгоритм и не является самым быстрым, но я решил начать с него потому что, на мой взгляд он наиболее прост для понимания. Суть алгоритма состоит в том, что бы в исходном массиве найти наименьший элемент, а затем поменять местами первый элемент в списке с найденным. После того, находиться наименьший их оставшихся и меняется со вторым элементом. И так до тех пор пока весь список не будет отсортирован.
Таким образом понадобиться N+(N-1)+(N-2)+…+1 или N*N проходов чтобы отсортировать список.

Листинг 1. Сортировка выбором
procedure SellectionSort( var a: array of integer; min,  
max: Integer);  
var
i, j, best_value, best_j: longint;  
begin
for i:=min to max do begin
best_value:=a[i];  
best_j:=i;  
for j:=i+1 to max do begin
if a[j]<best_value then begin
best_value:=a[j];  
best_j:=j;  
end;
end;
a[best_j]:=a[i];  
a[i]:=best_value;  
end;
end;

Переменными min и mах можно ограничить область списка в которой, будет  выполнена сортировка. Что бы отсортировать  весь массив необходимо записать следующее

Листинг 2. Код Delphi/Pascal
SellectionSort(a, 0, high(a));

Сортировка вставкой

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

Листинг 3. Сортировка вставкой
procedure InsertionSort( var a: array of integer; N: integer);  
var
B: array [0..10000] of integer;  
i, j: integer;  
begin
for i:=0 to N do begin
j:=i;  
while (j>1) and (B[j-1]>A[i]) do begin
B[j]:=B[j-1];  
j:=j-1;  
end;
B[j]:=A[i];  
end;
for i:=0 to N do
A[i]:=b[i];  
end;

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

Пузырьковая сортировка

Чаще  всего используется для сортировки частично упорядоченных списков, так как именно для них скорость выполнения максимальна и может равняться O(N), где N количество элементов массива, а O время одного прохода через цикл.

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

Класс TList

На рисунке изображен пример сортировки данным методом.

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

На рисунке элемент двигается к вершине, как пузырёк воздуха к поверхности воды. Этот эффект и дал название алгоритму пузырьковой сортировке.

Листинг 4. Пузырьковая сортировка
procedure BubbleSort( var a: array of integer; min, max: Integer);  
var
i, j, tmp: integer;  
begin
for i:=min to max do
for j:=min to max-i do
if A[j]>A[j+1] then
begin {Обмен элементов}
tmp:=A[j];  
A[j]:=A[j+1];  
A[j+1]:=tmp;  
end;
end;

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

При этом виде сортировке массив разбивается на две части, а затем рекурсивно вызывает сама себя для их сортировки. Притом элементы первой части меньше любого элемента второй части.
Рассмотрим данный вид сортировке на примере:  
Если алгоритм вызывается для списка, который содержит нуль или один элемент, то подписок уже отсортирован и процедура заканчивается, в противном случае выбирается один элемент, относительно которого список разбивается на две части, в первый подписок идут элементы меньше выбранного, во второй больше. И затем, как уже было сказано, она рекурсивно вызывает сама себя для сортировки обои подсписков.

Листинг 5. Быстрая сортировка
procedure QuickSort( var a: array of integer; min, max: Integer);  
Var  
i,j,mid, tmp : integer;  
Begin  
if min<max then begin
mid:=A[min];  
i:=min-1;  
j:=max+1;  
while i<j do begin
repeat
i:=i+1;  
until A[i]>=mid;  
repeat
j:=j-1;  
until A[j]<=mid;  
if i<j then begin
tmp:=A[i];  
A[i]:=A[j];  
A[j]:=tmp;  
end;
end;
QuickSort(a, min,j);  
QuickSort(a, j+1,max);  
end;
end;

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

Сортировка методом Шелла.

Ещё один метод  сортировки — это сортировка методом  Шелла.Основная идея этого алгоритма  заключается в том, чтобы в  начале ycтpанить массовый беспорядок в массиве, сравнивая далеко стоящие  друг от друга элементы.

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

Листинг 6. Сортировка методом Шелла
procedure TForm1.SortShell( var a: array of real; N: Integer);  
var
h:Variant;  
c:Boolean;  
g:Integer;  
i:Integer;  
j:Integer;  
tmp:Real;  
begin
h:=1;  
g:=0;  
repeat
h:=3*h+1  
until (h>=n);  
if (h>n) then begin
h:= h/3;  
g:=h;  
end;
n:=n-1;  
repeat
i:=g;  
repeat
j:=i-g;  
c:=True;  
repeat
if a[j]<=a[j+g] then begin
c:=False;  
end  
else begin
Tmp:=a[j];  
a[j]:=a[j+g];  
a[j+g]:=Tmp;  
end;
j:=j-1  
until not((j>=0)and(C));  
i:=i+1  
until not(i<=n);  
h:=g;  
h:=h/3;  
g:=h;  
until not(g>0);  
end;


Заключение.

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

Удачи!

P.S. Замечания, пожелания и дополнения к этой статье просим оставлять на форуме.

Цель: изучение алгоритма быстрой сортировки и ее модификаций.

На этом занятии  мы изучим алгоритм быстрой сортировки, который, пожалуй, используется более  часто, чем любой другой. Основа алгоритма  была разработана в 1960 году (C.A.R.Hoare) и с тех пор внимательно  изучалась многими людьми. Быстрая сортировка особенно популярна ввиду легкости ее реализации; это довольно хороший алгоритм общего назначения, который хорошо работает во многих ситуациях, и использует при этом меньше ресурсов, чем другие алгоритмы.

Основные достоинства этого алгоритма состоят в том, что он точечный (использует лишь небольшой дополнительный стек), в среднем требует только около N log N операций для того, чтобы отсортировать N элементов, и имеет экстремально короткий внутренний цикл. Недостатки алгоритма состоят в том, что он рекурсивен (реализация очень затруднена когда рекурсия недоступна), в худшем случае он требует N2 операций, кроме того он очень "хрупок": небольшая ошибка в реализации, которая легко может пройти незамеченной, мо жет привести к тому, что алгоритм будет работать очень плохо на некоторых файлах.

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

Улучшить алгоритм быстрой сортировки является большим искушением: более быстрый алгоритм сортировки — это своеобразная "мышеловка" для программистов. Почти с того момента, как Oia?a впервые опубликовал свой алгоритм, в литературе стали появляться "улучшен ные" версии этого алгоритма. Было опробовано и проанализировано множество идей, но все равно очень просто обмануться, поскольку алгоритм настолько хорошо сбалансирован, что результатом улучшения в одной его части может стать более сильное ухудшение в друг ой его части. Мы изучим в некоторых деталях три модификации этого алгоритма, которые дают ему существенное улучшение.

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

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

Найденные элементы меняются местами. После первого же прохода все элементы, которые меньше х, будут стоять слева от х, а все элементы, которые больше х, — справа от х. С двумя половинами массива поступают точно также. Продолжая деление этих половин до тех пор пока не останется в них по 1 элементу.

program Quitsort;

uses

  crt;

Const

  N=10;

Type

  Mas=array[1..n] of integer;

var

  a: mas;

  k: integer;

function Part(l, r: integer):integer;

var

  v, i, j, b: integer;

begin

  V:=a[r];

  I:=l-1;

  j:=r;

repeat

repeat

      dec(j)

until (a[j]<=v) or (j=i+1);

repeat

      inc(i)

until (a[i]>=v) or (i=j-1);

    b:=a[i];

    a[i]:=a[j];

    a[j]:=b;

until i>=j;

  a[j]:=a[i];

  a[i]:= a[r];

  a[r]:=b;

  part:=i;

end;

procedure QuickSort(l, t: integer);

var i: integer;

begin

if l<t then

begin

      i:=part(l, t);

      QuickSort(l,i-1);

      QuickSort(i+1,t);

end;

end;

begin

  clrscr;

  randomize;

for k:=1 to 10 do

begin

      a[k]:=random(100);

      write(a[k]:3);

end;

  QuickSort(1,n);

  writeln;

for k:=1 to n do

    write(a[k]:3);

  readln;

end.

Страницы:← предыдущая1234следующая →

FILED UNDER : IT

Submit a Comment

Must be required * marked fields.

:*
:*

Open

Close