Алгоритмы сортировки массива (BAS)

'/////////////////////////////////////////////////////////////////////
'
' Алгоритмы сортировки массива
'
' File    : PROFSORT.BAS
' Source  : Quick Basic, v4.5
' OS      : MSDOS-6.22
'
' Igor Salnikov, Copyright(C), 1995
'
'/////////////////////////////////////////////////////////////////////

DEFINT A-Z
DIM Mas1(1 TO 10), Mas2(1 TO 10)
CLS
RANDOMIZE TIMER
FOR n = 1 TO 10
  Mas1(n) = Randint%(1, 20)
  Mas2(n) = Mas1(n)
NEXT

ViewArray 10, Mas1()
PRINT : PRINT : PRINT

InsertionSort 10, Mas1()
ViewArray 10, Mas1(): FOR n = 1 TO 10: Mas1(n) = Mas2(n): NEXT
PRINT : PRINT

BubbleSort 10, Mas1()
ViewArray 10, Mas1(): FOR n = 1 TO 10: Mas1(n) = Mas2(n): NEXT
PRINT : PRINT

HeapSort 10, Mas1()
ViewArray 10, Mas1(): FOR n = 1 TO 10: Mas1(n) = Mas2(n): NEXT
PRINT : PRINT

ExchangeSort 10, Mas1()
ViewArray 10, Mas1(): FOR n = 1 TO 10: Mas1(n) = Mas2(n): NEXT
PRINT : PRINT

ShellSort 10, Mas1()
ViewArray 10, Mas1(): FOR n = 1 TO 10: Mas1(n) = Mas2(n): NEXT
PRINT : PRINT

QuickSort 1, 10, Mas1()
ViewArray 10, Mas1(): FOR n = 1 TO 10: Mas1(n) = Mas2(n): NEXT
PRINT : PRINT

a$ = INPUT$(1)
END

SUB BubbleSort (MaxIndex, SortArray())

    ' Алгоритм пузырька (speed = 2)
    Limit = MaxIndex
    DO
      Switch = 0
      FOR Index = 1 TO (Limit - 1)
        IF SortArray(Index) > SortArray(Index + 1) THEN
          SWAP SortArray(Index), SortArray(Index + 1)
          Switch = Index
        END IF
      NEXT Index
      Limit = Switch
    LOOP WHILE Switch

END SUB

SUB ExchangeSort (MaxIndex, SortArray())
    ' Алгоритм обмена (speed = 4)
    FOR Index = 1 TO MaxIndex
      SmallestIndex = Index
      FOR J = Index + 1 TO MaxIndex
        IF SortArray(J) < SortArray(SmallestIndex) THEN SmallestIndex = J
      NEXT J
      IF SmallestIndex > Index THEN
        SWAP SortArray(Index), SortArray(SmallestIndex)
      END IF
    NEXT Index
END SUB

SUB HeapDown (MaxLevel, SortArray())
    I = 1
    DO
      Child = 2 * I
      IF Child > MaxLevel THEN EXIT DO
      IF Child + 1 <= MaxLevel THEN
         IF SortArray(Child + 1) > SortArray(Child) THEN
           Child = Child + 1
         END IF
      END IF
      IF SortArray(I) < SortArray(Child) THEN
         SWAP SortArray(I), SortArray(Child)
         I = Child
      ELSE
         EXIT DO
      END IF
    LOOP
END SUB

SUB HeapSort (MaxIndex, SortArray())
    ' Алгоритм кучи (speed = 3)
    FOR I = 2 TO MaxIndex
      HeapUp I, SortArray()
    NEXT I

    FOR I = MaxIndex TO 2 STEP -1
      SWAP SortArray(1), SortArray(I)
      HeapDown I - 1, SortArray()
    NEXT I
END SUB

SUB HeapUp (MaxLevel, SortArray())
     I = MaxLevel
     DO UNTIL I = 1
        Parent = I  2
        IF SortArray(I) > SortArray(Parent) THEN
           SWAP SortArray(I), SortArray(Parent)
           I = Parent
        ELSE
           EXIT DO
        END IF
     LOOP
END SUB

SUB InsertionSort (MaxIndex, SortArray())
    ' Алгоритм вставки  (speed = 1)
    FOR Index = 2 TO MaxIndex
      TmpValue = SortArray(Index)
      FOR J = Index TO 2 STEP -1
        IF SortArray(J - 1) > TmpValue THEN
           SortArray(J) = SortArray(J - 1)
        ELSE
           EXIT FOR
        END IF
      NEXT J
        SortArray(J) = TmpValue
    NEXT Index
END SUB

SUB QuickSort (Low, High, SortArray())
    ' Быстрый алгоритм (speed = 6)
    IF Low < High THEN
      IF High - Low = 1 THEN
        IF SortArray(Low) > SortArray(High) THEN
          SWAP SortArray(Low), SortArray(High)
        END IF
      ELSE
        RandIndex = Randint%(Low, High)
        SWAP SortArray(Low), SortArray(RandIndex)
        Part = SortArray(High)
        DO
          I = Low: J = High

          DO WHILE (I < J) AND (SortArray(I) <= Part)
            I = I + 1
          LOOP
          DO WHILE (J > I) AND (SortArray(J) >= Part)
            J = J - 1
          LOOP

          IF I < J THEN SWAP SortArray(I), SortArray(J)
        LOOP WHILE I < J

        SWAP SortArray(I), SortArray(High)
        IF (I - Low) < (High - I) THEN
           QuickSort Low, I - 1, SortArray()
           QuickSort I + 1, High, SortArray()
        ELSE
           QuickSort I + 1, High, SortArray()
           QuickSort Low, I - 1, SortArray()
        END IF
      END IF
    END IF
END SUB

SUB ShellSort (MaxIndex, SortArray())
    ' Алгоритм ракушки (speed = 5)
    Offset = MaxIndex  2
    DO WHILE Offset > 0
       Limit = MaxIndex - Offset
       DO
         Switch = 0
         FOR Index = 1 TO Limit
           IF SortArray(Index) > SortArray(Index + Offset) THEN
              SWAP SortArray(Index), SortArray(Index + Offset)
              Switch = Index
           END IF
         NEXT Index
         Limit = Switch - Offset
       LOOP WHILE Switch
       Offset = Offset  2
    LOOP
END SUB

FUNCTION Randint% (lower, Upper) STATIC
    Randint% = INT(RND * (Upper - lower + 1)) + lower
END FUNCTION

SUB ViewArray (MaxIndex, SortArray())
    FOR n = 1 TO 10
      PRINT USING " ## "; SortArray(n);
    NEXT
END SUB