Challenge: Bash the Quicksort

Trader11 · Dec 2, 2022

davidktw said:
Does it produce the same output as what my question requires, and how does it perform?

Looking at the code, I just have to give it one data set to make it work like a snail. Did the chat.ai bot tells you that too?

Can you ask your chat.ai bot about it? lol

Can’t say it is a good try, but a noted try?
I definitely am expecting more from you, not functioning just as a liaison officer for your chat.ai bot.
In any case, appreciate the participation.

I generated from mobile.

Haven't proof read

davidktw · Dec 2, 2022

Trader11 said:
I generated from mobile.

Haven't proof read

Maybe you should ?

davidktw · Dec 10, 2022

davidktw said:
Well I often hear leetcode challenges among some posts in this forum.
Perhaps it would be an interesting challenge to code a Quicksort implementation using Bash too ?

Other languages would be such a simple feat to implement Quicksort efficiently. Perhaps the challengers here can do just as good using Bash ?
The fun part has not arrived yet and there will be a reason why I have chosen Bash for this purpose.
Lets start simple first. Lets just implement a Quicksort in Bash first and see how far our HWZ Forum software engineers can achieve. (wink wink)

QUESTION
Implement a Quicksort algorithm using Bash where the implementation should use as much of Bash as possible. While there will be no restriction on how the implementation should be as long as it is written using Bash, challengers are free to use other utilities within the Linux ecosystem as long as the main sorting implementation is written purely in Bash. That means you should not using other programming languages or utilities that perform the actual sorting such as sort, or other programming tools like awk, perl, python etc.

INPUT

0 - N numeric values delimited by newline characters will be provided from standard IN stream.

Each numerical value can be in the integral range [-2^63,(2^63)-1]

Input is only limited to numerical values, string comparison is not required.

0 <= N <= 100000

OUTPUT

The sorted 0 - N numeric values, by ascending order (top down) will be printed to the standard OUT stream delimited by newline characters

Nothing should be printed if N == 0

SAMPLE

Code:

$ echo -ne '' | ./quicksort.sh $ echo '' | ./quicksort.sh $ echo '1' | ./quicksort.sh 1 $ seq 10 1 | ./quicksort.sh 1 2 3 4 5 6 7 8 9 10 $ (seq 10 1;seq 0 -10) | ./quicksort.sh -10 -9 -8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9 10

PERFORMANCE
Here we are also interested in performance. As every challenger system will differs, we will try to give a gauge to how good your implementation is
I will use sort as a measure which we can run on our system

Code:

$ time sort -n <quicksort.sample.test.data.10k.txt >/dev/null real 0m0.008s user 0m0.008s sys 0m0.001s

Hence the performance of your implementation will be pegged relative to the execution time of the linux sort tool using the exact command line arguments as shown above.

By running a sample set of test data of 10,000 lines of random numerical input data which you can download from
https://mega.nz/file/3DBEmBgR#ttIXpIkLFq-vtkPe4S_ZhKAOYyX0r2-mqH60Zwc2K6gand running the following command

Code:

$ time ./quicksort.sh <quicksort.sample.test.data.10k.txt >/dev/null real 0m5.924s user 0m5.915s sys 0m0.008s

That would means my implementation would be approximately 740.5x of the linux sort execution time. The lower this relative value is, the better your implementation is.

Here is another run against a sample set of 100,000 lines of random numerical input data which you can download from
https://mega.nz/file/mGhHxSST#Yqc3j_zVcwXsa597TnYqHSfEUXoWp9kLlz6BTPbZx-Y
When you use the 100k lines data set on the linux sort utility as such

Code:

$ time sort -n <quicksort.sample.test.data.100k.txt >/dev/null real 0m0.072s user 0m0.052s sys 0m0.020s

and upon your own Bash Quicksort implementation, you will get another relative performance.

Code:

$ time ./quicksort.sh <quicksort.sample.test.data.100k.txt >/dev/null real 5m35.569s user 5m35.444s sys 0m0.080s

Mine would be 4660.68x times of linux sort utility timing
As you can see Bash is not exactly performant and as the input size get larger, it is just going to get ridiculously slower.

In case you are wondering how can Bash be so slow ?
These are the timings for the same algorithm written in Perl and ran against the same 2 test cases above.
The timings versus the linux sort utility are relatively 8.0x and 6.3x respectively

Code:

$ time <quicksort.sample.test.data.10k.txt ./quicksort.pl >/dev/null real 0m0.064s user 0m0.060s sys 0m0.005s $ time <quicksort.sample.test.data.100k.txt ./quicksort.pl >/dev/null real 0m0.454s user 0m0.446s sys 0m0.008s

Perl is already slower than C, but given Perl is a JIT compiled programming language, it is much faster than Bash, which is an interpreted language, in comparison.

However what we are pursing here is creativity when working with constrained scenario and Bash have its quirks, hence it’s up to you to squeeze as much out of it as possible.

We have not hit the limits yet, lets how the basic quicksort implementation progress (^.^)

Have fun coding and hopefully we still have software engineers that remember how to implement Quicksort instead of just knowing how to use.
Invitation to @peterchan75 @ng min teck @Trader11 @diminishin @project_00 and others!

Small hint: Remember how the input may vastly affect the performance of Quicksort ? What makes the worse case complexity of Quicksort ? Take note in your implementation.

It would seems getting SWE nowadays to attempt Quicksort is a new kind of difficulty. Getting them to do it using a shell script is another level of difficulty.

Here would be the one I did using Bash

Bash:

#!/usr/bin/env bash

function qs {
  local -n arr=$1
  local left=$2
  local right=$3
  local temp
  local pivot
  if ((left < right)); then
    ((
    pivot = RANDOM * RANDOM % (right - left + 1) + left,
    temp = arr[pivot],
    arr[pivot]=arr[right],
    arr[right]=temp,
    pivot=right,
    right--
    ))
    while ((left <= right))
    do
      if ((arr[left] < arr[pivot])); then
        ((left++))
      else
        ((
        temp = arr[left],
        arr[left]=arr[right],
        arr[right]=temp,
        right--
        ))
      fi
    done
    ((
    temp = arr[left],
    arr[left]=arr[pivot],
    arr[pivot]=temp,
    right--
    ))
    qs "${!arr}" $2 $(($left - 1))
    qs "${!arr}" $(($left + 1)) $pivot
  fi
}

function _main {
  local -a arr_input
  if (($# == 0)); then
    readarray -t arr_input
  else
    arr_input=("$@")
  fi
  ((${#arr_input[@]} > 0))  && [ "z${arr_input[0]}" != "z" ] && \
    qs "arr_input" 0 $((${#arr_input[@]} - 1)) && printf '%d\n' ${arr_input[@]}
}
_main "$@"

The same technique written in Perl

Perl:

#!/usr/bin/env perl

use strict;
use warnings;

my @arr=();
while (<>) {
  chomp;
  push(@arr, $_);
}

sub qs {
  my($arr, $left, $right) = @_;
  if ($left < $right) {
    my $pivot = int(rand() * ($right - $left + 1)) + $left;
    my $temp = $arr[$pivot];
    $arr[$pivot] = $arr[$right];
    $arr[$right] = $temp;
    $pivot = $right;
    $right--;
    while ($left <= $right) {
      if ($arr[$left] < $arr[$pivot]) {
          $left++;
      } else {
        $temp = $arr[$left];
        $arr[$left] = $arr[$right];
        $arr[$right] = $temp;
        $right--;
      }
    }
    $temp = $arr[$left];
    $arr[$left] = $arr[$pivot];
    $arr[$pivot] = $temp;
    qs($arr, $_[1], $left - 1);
    qs($arr, $left + 1, $pivot);
  }
}

qs(\@arr, 0, $#arr);
print join("\n", @arr), "\n";

Same technique in Python

Python:

#!/usr/bin/env python3

import sys
from random import randrange

arr = []
for line in sys.stdin:
    arr.append(int(line))

def quicksort(arr, left=0, right=None):
    if right is None:
        right = len(arr) - 1
    if (left < right):
        oleft  = left
        oright = right
        r      = randrange(left, right + 1)
        pivot  = arr[r]
        arr[r] = arr[right]
        arr[right] = pivot
        right -= 1
        while (left <= right):
            if arr[left] < pivot:
                left += 1
            else:
                temp       = arr[left]
                arr[left]  = arr[right]
                arr[right] = temp
                right     -= 1
        arr[oright] = arr[left]
        arr[left]   = pivot
        quicksort(arr, oleft, left - 1)
        quicksort(arr, left + 1, oright)
    return arr

for i in quicksort(arr):
    print(i)

This is a less performant method in Python. It looks pretty fast when the input size is small, but if you observe the memory consumption, it will balloon up very quickly.

Python:

#!/usr/bin/env python3

import sys
from random import randrange

arr = []
for line in sys.stdin:
    arr.append(int(line))

def quicksort(arr):
    if len(arr) <= 1:
        return arr
    r      = randrange(len(arr))
    pivot  = arr[r]
    return quicksort([i for i in arr if i < pivot]) + [i for i in arr if i == pivot] + quicksort([i for i in arr if i > pivot])

for i in quicksort(arr):
    print(i)

Is it academic like what Peter said ? At this point of time, yes because it is still starting. After 766 views to this thread on 10-Dec, only 1x submission from AI was submitted. Lets hope the SWEs that read this thread are too busy or find it too easy for them to attempt.

However the fun hasn't really begin.
Happy coding.

davidktw · Dec 10, 2022

Part 2 and Part 3 to this Quicksort challenge is out.
Refer to Post #2 and Post #3 for details.

@Trader11 wanna try consult the AI for multiprocessing solution ?

davidktw · Dec 12, 2022

davidktw said:
Okay lets have the 2nd part to this challenge ?
Suppose you have attempted the part 1 of this challenge in the post above using recursive approach, now try implement the iterative approach.
All recursive solution must have a non-recursive counterpart.

Hint: One possible technique is you need to know how to use a particular data structure.

I think we can just skim over this 2nd part as it is rather trivial. Better to just focus on part 3 which is the interesting bit.
If you do run the code, you will quickly realise the iterative approach is not much better than the recursive approach because a good recursive implementation can be rather efficient if you know exactly what makes a recursion expensive. Method calls and keeping stack frames can be costly at times, but if you know your complexity analysis, you will know a good recursive quicksort implementation isn't costly in that manner. There are more costly operations besides recursion and the language implementation used matters. In this case, Bash is inefficient enough to make recursion the lesser of concern.

Bash:

#!/usr/bin/env bash

function qs {
  local -n arr=$1
  local left
  local oleft
  local right
  local temp
  local pivot

  local -a tasks

  # TASK FORMAT
  # LEFT RIGHT LEFT RIGHT ... LEFT RIGHT
  tasks=("$2 $3")

  while ((${#tasks[@]} > 0)); do

    read left right <<<"${tasks[0]}"
    ((oleft=left))
    tasks=("${tasks[@]:1}")

    if ((left < right)); then
      ((
      pivot = RANDOM * RANDOM % (right - left + 1) + left,
      temp = arr[pivot],
      arr[pivot]=arr[right],
      arr[right]=temp,
      pivot=right,
      right--
      ))
      while ((left <= right))
      do
        if ((arr[left] < arr[pivot])); then
          ((left++))
        else
          ((
          temp = arr[left],
          arr[left]=arr[right],
          arr[right]=temp,
          right--
          ))
        fi
      done
      ((
      temp = arr[left],
      arr[left]=arr[pivot],
      arr[pivot]=temp
      ))
      tasks=("$oleft $(($left - 1))" "$(($left + 1)) $pivot" "${tasks[@]}")
    fi

  done
}

function _main {
  local -a arr_input
  if [ $# -eq 0 ]; then
    readarray -t arr_input
  else
    arr_input=("$@")
  fi
  [ ${#arr_input[@]} -gt 0 ] && [ "z${arr_input[0]}" != "z" ] && \
    qs "arr_input" 0 $((${#arr_input[@]} - 1)) && printf '%d\n' ${arr_input[@]}
}
_main "$@"

Happy coding

Challenge: Bash the Quicksort

More options

Trader11

Banned

davidktw

Arch-Supremacy Member

davidktw

Arch-Supremacy Member

davidktw

Arch-Supremacy Member

davidktw

Arch-Supremacy Member