How to resolve the algorithm Sorting algorithms/Quicksort step by step in the ERRE programming language

Published on 12 May 2024 09:40 PM
#Erre

How to resolve the algorithm Sorting algorithms/Quicksort step by step in the ERRE programming language

Table of Contents

Problem Statement

Sort an array (or list) elements using the   quicksort   algorithm. The elements must have a   strict weak order   and the index of the array can be of any discrete type. For languages where this is not possible, sort an array of integers.

Quicksort, also known as   partition-exchange sort,   uses these steps.

The best pivot creates partitions of equal length (or lengths differing by   1). The worst pivot creates an empty partition (for example, if the pivot is the first or last element of a sorted array). The run-time of Quicksort ranges from   O(n log n)   with the best pivots, to   O(n2)   with the worst pivots, where   n   is the number of elements in the array.

This is a simple quicksort algorithm, adapted from Wikipedia. A better quicksort algorithm works in place, by swapping elements within the array, to avoid the memory allocation of more arrays. Quicksort has a reputation as the fastest sort. Optimized variants of quicksort are common features of many languages and libraries. One often contrasts quicksort with   merge sort,   because both sorts have an average time of   O(n log n). Quicksort is at one end of the spectrum of divide-and-conquer algorithms, with merge sort at the opposite end.

With quicksort, every element in the first partition is less than or equal to every element in the second partition. Therefore, the merge phase of quicksort is so trivial that it needs no mention! This task has not specified whether to allocate new arrays, or sort in place. This task also has not specified how to choose the pivot element. (Common ways to are to choose the first element, the middle element, or the median of three elements.) Thus there is a variety among the following implementations.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Sorting algorithms/Quicksort step by step in the ERRE programming language

Source code in the erre programming language

PROGRAM QUICKSORT_DEMO

DIM ARRAY[21]

!$DYNAMIC
DIM QSTACK[0]

!$INCLUDE="PC.LIB"

PROCEDURE QSORT(ARRAY[],START,NUM)
  FIRST=START               ! initialize work variables
  LAST=START+NUM-1
  LOOP
    REPEAT
      TEMP=ARRAY[(LAST+FIRST) DIV 2]  ! seek midpoint
      I=FIRST
      J=LAST
      REPEAT     ! reverse both < and > below to sort descending
      WHILE ARRAY[I]
        I=I+1
        END WHILE
        WHILE ARRAY[J]>TEMP DO
          J=J-1
        END WHILE
        EXIT IF I>J
        IF I
        I=I+1
        J=J-1
      UNTIL NOT(I<=J)
      IF I
         QSTACK[SP]=I            ! Push I
         QSTACK[SP+1]=LAST       ! Push Last
         SP=SP+2
      END IF
      LAST=J
    UNTIL NOT(FIRST

    EXIT IF SP=0
    SP=SP-2
    FIRST=QSTACK[SP]            ! Pop First
    LAST=QSTACK[SP+1]           ! Pop Last
  END LOOP
END PROCEDURE

BEGIN
   RANDOMIZE(TIMER)              ! generate a new series each run

                                 ! create an array
   FOR X=1 TO 21 DO              ! fill with random numbers
       ARRAY[X]=RND(1)*500       ! between 0 and 500
   END FOR
   PRIMO=6                       ! sort starting here
   NUM=10                        ! sort this many elements
   CLS
   PRINT("Before Sorting:";TAB(31);"After sorting:")
   PRINT("===============";TAB(31);"==============")
   FOR X=1 TO 21 DO              ! show them before sorting
      IF X>=PRIMO AND X<=PRIMO+NUM-1 THEN
         PRINT("==>";)
      END IF
      PRINT(TAB(5);)
      WRITE("###.##";ARRAY[X])
   END FOR

! create a stack
!$DIM QSTACK[INT(NUM/5)+10]
   QSORT(ARRAY[],PRIMO,NUM)
!$ERASE QSTACK

   LOCATE(2,1)
   FOR X=1 TO 21 DO                ! print them after sorting
      LOCATE(2+X,30)
      IF X>=PRIMO AND X<=PRIMO+NUM-1 THEN
         PRINT("==>";)             ! point to sorted items
      END IF
      LOCATE(2+X,35)
      WRITE("###.##";ARRAY[X])
   END FOR
END PROGRAM

You may also check:How to resolve the algorithm Remove duplicate elements step by step in the ATS programming language
You may also check:How to resolve the algorithm Generate random chess position step by step in the C++ programming language
You may also check:How to resolve the algorithm Tau number step by step in the ALGOL 68 programming language
You may also check:How to resolve the algorithm Compound data type step by step in the Go programming language
You may also check:How to resolve the algorithm Averages/Mode step by step in the Ada programming language