← All source

Pascal — quicksort.pas

fpc -O3 quicksort.pas

./quicksort

wsl.exe -d Ubuntu -- bash -c "cd '/mnt/c/Users/granite/Documents/DSU/Algorithms 482/3/HW3/pascal' && fpc -O3 quicksort.pas && ./quicksort"

{
  Randomized Quicksort timing harness -- CSC 482 HW3 (Language Comparison)

  Algorithm: CLRS RANDOMIZED-QUICKSORT / RANDOMIZED-PARTITION (Ch. 5).
  At every partition step the pivot index is chosen uniformly at random
  from the current subarray range, swapped into the last position, and
  then a standard Lomuto partition is run around it. In-place, no
  library sort routine is used.

  No external code used -- original implementation based on CLRS
  RANDOMIZED-QUICKSORT pseudocode.

  Timing: FPC 3.2.2's SysUtils unit does not provide TStopwatch on this
  Linux target (confirmed by a failed compile attempt), and GetTickCount64
  is only millisecond resolution, so this uses BaseUnix/Unix's
  fpgettimeofday (a thin wrapper around the POSIX gettimeofday() syscall),
  which gives microsecond resolution -- both units are standard FPC RTL,
  no external packages.

  Build:  fpc -O3 quicksort.pas
  Run:    ./quicksort
}
program quicksort;

{$mode objfpc}{$H+}

uses
  SysUtils, BaseUnix, Unix;

type
  TIntArray = array of Integer;

{ Swap two integers in the array by index. }
procedure Swap(var arr: TIntArray; i, j: Integer);
var
  tmp: Integer;
begin
  tmp := arr[i];
  arr[i] := arr[j];
  arr[j] := tmp;
end;

{
  Lomuto partition around arr[hi] as the pivot. Returns the final index
  of the pivot after partitioning.
}
function LomutoPartition(var arr: TIntArray; lo, hi: Integer): Integer;
var
  pivot, i, j: Integer;
begin
  pivot := arr[hi];
  i := lo - 1;
  for j := lo to hi - 1 do
  begin
    if arr[j] <= pivot then
    begin
      Inc(i);
      Swap(arr, i, j);
    end;
  end;
  Swap(arr, i + 1, hi);
  Result := i + 1;
end;

{
  RANDOMIZED-PARTITION: choose a pivot index uniformly at random from
  [lo, hi], swap it into the last position, then partition normally.
}
function RandomizedPartition(var arr: TIntArray; lo, hi: Integer): Integer;
var
  r: Integer;
begin
  { Random(N) returns a value uniformly in [0, N-1]. }
  r := lo + Random(hi - lo + 1);
  Swap(arr, r, hi);
  Result := LomutoPartition(arr, lo, hi);
end;

{ RANDOMIZED-QUICKSORT: recursive in-place randomized quicksort. }
procedure RandomizedQuicksort(var arr: TIntArray; lo, hi: Integer);
var
  p: Integer;
begin
  if lo < hi then
  begin
    p := RandomizedPartition(arr, lo, hi);
    RandomizedQuicksort(arr, lo, p - 1);
    RandomizedQuicksort(arr, p + 1, hi);
  end;
end;

{ Fill arr[0..n-1] with random ints in [0, 1000000). Not timed. }
procedure GenerateRandomArray(var arr: TIntArray; n: Integer);
var
  i: Integer;
begin
  SetLength(arr, n);
  for i := 0 to n - 1 do
    arr[i] := Random(1000000);
end;

var
  csv: TextFile;
  arr: TIntArray;
  n: Int64;
  iterations: Integer;
  tvStart, tvEnd: TTimeVal;
  elapsed: Double;
const
  MAX_ITERATIONS = 25;
  MAX_SECONDS = 4.0;
  MAX_N: Int64 = 200000000;

begin
  Randomize; { seed RNG from the clock, once, at startup }

  AssignFile(csv, '../results/pascal.csv');
  Rewrite(csv);
  Writeln(csv, 'n,time_seconds');
  Flush(csv);

  Writeln('n,time_seconds');

  n := 1000;
  iterations := 0;

  while True do
  begin
    GenerateRandomArray(arr, n);

    fpgettimeofday(@tvStart, nil);
    RandomizedQuicksort(arr, 0, n - 1);
    fpgettimeofday(@tvEnd, nil);
    elapsed := (tvEnd.tv_sec - tvStart.tv_sec)
             + (tvEnd.tv_usec - tvStart.tv_usec) / 1.0e6;

    SetLength(arr, 0);

    Inc(iterations);
    Writeln(Format('%d,%.6f', [n, elapsed]));
    Writeln(csv, Format('%d,%.6f', [n, elapsed]));
    Flush(csv);

    if elapsed > MAX_SECONDS then
    begin
      Writeln('Stopping: iteration exceeded ', MAX_SECONDS:0:1, 's');
      Break;
    end;
    if iterations >= MAX_ITERATIONS then
    begin
      Writeln('Stopping: reached ', MAX_ITERATIONS, ' iterations');
      Break;
    end;
    if n * 2 > MAX_N then
    begin
      Writeln('Stopping: next n would exceed ', MAX_N);
      Break;
    end;

    n := n * 2;
  end;

  CloseFile(csv);
end.

Read Pascal report