Задача с сортировкой (Delphi). Дано n точек на плоскости. Указать (n-1)-звенную несамопересекающуюся незамкнутую ломаную

[BHMJ(G)]

n**2 это квадрат (n^2). По моему алгоритму в сравнении с каждой данной точкой участвуют все точки, которые не были обработаны ранее, т.е. для первой точки это будет n-1 сравнений, для второй n-2 и т.д., что в итоге даёт (n^2)/2 операций. Вы можете предложить алгоритм со временем порядка n*log(n)? И да, я говорю об алгоритме поиска точек, составляющих спираль, а не о конечной сортировке точек перед отрисовкой.

[Леон2110]

Читая сообщения вспомнил про условие, в конце задачи написано: Обеспечить число действий порядка n*log n. Что это должно значить?

И кстати вот код сортировки полностью, может кому пригодится:

unit Unit1;

interface

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

type
  TForm1 = class(TForm)
    Memo2: TMemo;
    Button4: TButton;
    btn2: TButton;
    procedure Button4Click(Sender: TObject);
    procedure btn2Click(Sender: TObject);
  private
    { Private declarations }
  public
    { Public declarations }
  end;

var
  Form1: TForm1;
  i:integer;

 a: array[0..14] of TPoint;


 implementation

{$R *.dfm}

//процедура сортировки
procedure BubbleSort( var a: array of TPoint; min, max: Integer);
var
i, j: integer;
tmp: TPoint;
begin
//заполняем массив случайными числами от 0 до 195 с шагом 5
 randomize;
for i:=0 to 14 do
begin
a[i].x:=random(40)*5;
a[i].y:=random(40)*5;
end;
//сортировка массива
for i:=min to max do
for j:=min to max do
if (A[i].x < A[j].x) or ( (A[i].x = A[j].x) and (A[i].y < A[j].y) ) then begin
tmp:=A[i];
A[i]:=A[j];
A[j]:=tmp;
end;
end;


//кнопка запускающая процедуру сортировки и вывод в мемо2
procedure TForm1.Button4Click(Sender: TObject);
begin
BubbleSort(a,low(a),high(a));
for i:=low(a) to high(a) do
begin
  Memo2.Lines.Add (IntToStr(A[i].x)+ ','+ IntToStr(A[i].y));
end;
end;

//соединяем точки прямыми и рисуем красные кружки в местах точек
procedure TForm1.btn2Click(Sender: TObject);
begin
 With Form1.Canvas do
begin
  Polyline(a);
  Pen.Color := clRed;
  for i := low(a) to high(a) do
    Ellipse(a[i].x - 2, a[i].y - 2, a[i].x + 2, a[i].y + 2);
end;
end;

end.

[BDA]

Думаю, преподаватель хочет более эффективный алгоритм сортировки:

(Из Знай сложности алгоритмов)

[rrrFer]

Вы можете предложить алгоритм со временем порядка n*log(n)?

Да, а че тут предлагать?
Сортировка - n*log(n)
Выпуклая оболочка - n*log(n) - из за того, что предварительно нужна сортировка, но если точки отсортированы точки оболочки собираются за n (в худшем случае, если все точки принадлежат оболочке).

Твоя задача - чуть модифицировать выпуклую оболочку. Оболочка - это один слой твоей спирали.

выходит n*log(n) + n = n*log(n)

Даже не догадываюсь куда ты тут n^2 засадил.