Задача 4. Быстрая сортировка

Ввести натуральное число N, не превосходящее 10000. Получить N случай­ных натуральных чисел, не превосходящих 999. Упорядочить числа по неубыва­нию, используя алгоритм сортировки бинарными вставками.

{ Решение задачи 4 на языке PASCAL } {$X+}

USES Crt;

CONST Nmax=10000; Range=1000; TYPE TArray=ARRAY[1..Nmax] OF Word; PROCEDURE Print(n:Word; VAR A:TArray); VAR i : Word; BEGIN i:=1;

WHILE i<=n DO BEGIN

Write(A[i]:4);

IF i MOD 480=0 THEN BEGIN

Write('Ha5KMme клавишу'); ReadKey; WriteLn; END;

Inc(i);

END;

IF i MOD 480<>0 THEN BEGIN

Write(#10,#13,'Ha5KMme клавишу'); ReadKey; WriteLn; END;

END;

PROCEDURE BinarySort(n:Word; VAR a:TArray); VAR i,Nsort,as,bs,xs,Tmp : Word;

BEGIN Nsort:=1;

WHILE Nsort<n DO BEGIN Tmp:=a[Nsort+1];

IF Tmp>=a[Nsort] THEN BEGIN Inc(Nsort); Continue; END; IF Tmp<=a[1] THEN BEGIN

FOR i:=Nsort+1 DOWNTO 2 DO a[i]:=a[i-1];

a[1]:=Tmp; Inc(Nsort); Continue; END; as:=1; bs:=Nsort; xs:=(as+bs)DIV 2;

WHILE (xs<>as)AND(xs<>bs) DO BEGIN

IF Tmp=a[xs] THEN BEGIN bs:=xs+1; Break; IF Tmp<a[xs] THEN bs:=xs ELSE as:=xs; xs:=(as+bs)DIV 2;

END;

FOR i:=Nsort+1 DOWNTO bs+1 DO a[i]:=a[i-1]; a[bs]:=Tmp; Inc(Nsort);

END; END;

VAR A : TArray; n,i : Word;

BEGIN Write('Ввeдитe длину последовательности '); Read(n); Randomize; FOR i:=1 TO n DO A[i]:=Random(Range); Print(n,A);

WriteLn('Упopядoчeннaя последовательность :'); BinarySort(n,A); Print(n,A);

END.

/* Решение задачи 4 на языке C */

#include<stdio.h>

#include<conio.h>

#include<time.h>

#include<stdlib.h>

#define NMAX 10000

#define RANGE 1000

void Print(unsigned n,unsigned a[]){ unsigned i; i=1; while(i<=n){printf("%4u",a[i]);

if(!(i%480)){printf("Haжмитe клавишу"); getch(); printf("\n");}i++;} if(i%480){printf("\nHaжмитe клавишу"); getch(); printf("\n");}} void BinarySort(unsigned n,unsigned a[]){ unsigned i,Nsort=0,as,bs,xs,Tmp; while(++Nsort<n){Tmp=a[Nsort+1]; if(Tmp>=a[Nsort])continue;

if(Tmp<=a[1]){for(i=Nsort+1;i>=2;i--)a[i]=a[i-1];a[1]=Tmp;continue;} as=1; bs=Nsort; xs=(as+bs)/2;

while(xs!=as&&xs!=bs){if(Tmp==a[xs]){bs=xs+1;break;}

if(Tmp<a[xs])bs=xs;else as=xs; xs=(as+bs)/2;}

for(i=Nsort+1;i>bs;i--)a[i]=a[i-1]; a[bs]=Tmp;}} void main(void) { unsigned A[NMAX+1],n,i;

printf("\nВвeдитe длину последовательности "); scanf("%i",&n); randomize(); for(i=1;i<=n;i++)A[i]=random(RANGE); Print(n,A); printf("Упopядoчeннaя последовательность :\n"); BinarySort(n,A); Print(n,A);}

C   Решение Задачи 4 на языке FORTRAN SUBROUTINE $Print(n,A) INTEGER*2 A(n)

nn=n/460 DO 1 i1=1,nn

PRINT 999,(A(i),i=(i1-1)*460+1,i1*460) 1        PAUSE'Ha^MHTe ENTER'

IF(MOD(n,460).GT.0) THEN

PRINT 999,(A(i),i=nn*460+1,n) PAUSE'Ha^MHTe ENTER'

ENDIF

999 FORMAT(20I4)

END

SUBROUTINE BinarySort(n,a) INTEGER*2 a(n),as,bs,xs,Tmp Nsort=1

DO 99 WHILE(Nsort.LT.n) Tmp=a(Nsort+1) IF(Tmp-a(Nsort))1,99,99

1 IF(Tmp-a(1))2,2,3

2 DO 100 i=Nsort+1,2,-1

100 a(i)=a(i-1)

a(1)=Tmp

GOTO 99

3 as=1 bs=Nsort xs=(as+bs)/2

DO WHILE(xs.NE.as.AND.xs.NE.bs)

IF (Tmp.EQ.a(xs)) THEN bs=xs+1 EXIT

ENDIF

IF(Tmp.LT.a(xs)) THEN bs=xs

ELSE

as=xs

ENDIF

xs=(as+bs)/2

END DO

DO 101 i=Nsort+1,bs+1,-1

101 a(i)=a(i-1) a(bs)=Tmp

99 Nsort=Nsort+1

END

PARAMETER(Nmax=10000,Range=1000) INTEGER*2 A(Nmax)

PRINT *,'Введите длину последовательности ' READ*,n

CALL GetTim(ih,im,is,is100) CALL Seed(is*100) DO 1 i=1,n

CALL Random(x) 1 A(i)=x*Range CALL $Print(n,A)

PRINT*,'Упopядoчeннaя последовательность :' CALL BinarySort(n,A) CALL $Print(n,A)

END