How to resolve the algorithm Sorting algorithms/Quicksort step by step in the Icon and Unicon programming language

Published on 12 May 2024 09:40 PM
#Icon and unicon

How to resolve the algorithm Sorting algorithms/Quicksort step by step in the Icon and Unicon 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 Icon and Unicon programming language

Source code in the icon programming language

procedure main()                     #: demonstrate various ways to sort a list and string 
   demosort(quicksort,[3, 14, 1, 5, 9, 2, 6, 3],"qwerty")
end

procedure quicksort(X,op,lower,upper)                      #: return sorted list
local pivot,x 

   if /lower := 1 then {                                   # top level call setup
      upper := *X   
      op := sortop(op,X)                                   # select how and what we sort
      }

   if upper - lower > 0 then {
      every x := quickpartition(X,op,lower,upper) do       # find a pivot and sort ...
          /pivot | X := x                                  # ... how to return 2 values w/o a structure
      X := quicksort(X,op,lower,pivot-1)                   # ... left            
      X := quicksort(X,op,pivot,upper)                     # ... right
      }

   return X                                             
end

procedure quickpartition(X,op,lower,upper)                 #: quicksort partitioner helper
local   pivot
static  pivotL
initial pivotL := list(3)

   pivotL[1] := X[lower]                                   # endpoints
   pivotL[2] := X[upper]                                   # ... and
   pivotL[3] := X[lower+?(upper-lower)]                    # ... random midpoint
   if op(pivotL[2],pivotL[1]) then pivotL[2] :=: pivotL[1] # mini-
   if op(pivotL[3],pivotL[2]) then pivotL[3] :=: pivotL[2] # ... sort
   pivot := pivotL[2]                                      # median is pivot

   lower -:= 1
   upper +:= 1
   while lower < upper do {                                # find values on wrong side of pivot ...
      while op(pivot,X[upper -:= 1])                       # ... rightmost 
      while op(X[lower +:=1],pivot)                        # ... leftmost
      if lower < upper then                                # not crossed yet
         X[lower] :=: X[upper]                             # ... swap 
      }

   suspend lower                                           # 1st return pivot point
   suspend X                                               # 2nd return modified X (in case immutable)
end

You may also check:How to resolve the algorithm Loops/While step by step in the Seed7 programming language
You may also check:How to resolve the algorithm Semiprime step by step in the Bracmat programming language
You may also check:How to resolve the algorithm Evolutionary algorithm step by step in the SETL programming language
You may also check:How to resolve the algorithm Tree traversal step by step in the Elena programming language
You may also check:How to resolve the algorithm Monte Carlo methods step by step in the Action! programming language