Lol well this was all wrong xd but das okay

Background

A good algorithm

• Values are only compared where needed
• Quick speed / low execution counts
• Deterministic output
• Sort stability

Sorting algorithms

• Bubble sort (unoptimised)
• Bubble sort (optimised)
• Insertion sort
• Selection sort
• Shell sort (Powers of 4)
• Shell sort (Sedgewick)
• Pseudo-Bogo Sort

Complexity

Sorting Stability

A sorting implementation is considered stable if values maintain ordering when sorted by another key.

For example

Would return

Rather than some variant where the a -> b -> c ordering is not preserved

A stable sort would keep the ordering (for key 1) CAB,
whereas an unstable sort might produce ABC, ACB, BAC, BCA, or CBA

Design

The program execution time of sortA and sortB can be used to analyse the type of algorithm implemented. For example, a bubble sort in its best case (already sorted) scenario should occupy O(n) time

Methodology

Linear Time
Traversing a sorted array of 2n elements should take twice the time of a sorted array of n elements  
Bubble vs Insertion
Both Bubble Sort and Insertion Sort share the same best, average and worst case execution times. However one input case where Insertion Sort is faster than Bubble Sort is {1,3,3,3,3,3,…,3,2}. Where Insertion Sort will take O(n) time while Bubble Sort would take O(n^2) time.
We can craft an input with: python3 -c "print('\n'.join(map(str,[1,*([3]*(1000000-2)),2])))"
 
Checking for stability
We can craft an input to check for stablity

1 2 3 4 5 6 7

1 C 2 1 A 3 1 B 4 5

Checking for bogo-ness
For a sort of the same array of numbers taken n times, if the differences between timings are considerably different, or if the sort never finishes within a reasonable time - then it is highly liking that the sort is a bogo sort.

Lots of data … 'lazily'

I can’t be bothered to learn bash scripting so I’ll just use Python

This script generates a comma-separated list of n_items, time.
This could be used for finding patterns, or even for graphing/plotting purposes

Usage: ./data.py [items] [A/D/R]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

#!/bin/python3
import sys

import subprocess
from random import shuffle

# Returns the mean of a list of items (to 3 decimal places)
def average(items):
  sum = 0
  for item in items:
    sum += item
  return round(sum / len(items), 3)

for n in range(2, int(sys.argv[1]), 10000):
  print(n, file=sys.stderr, end=" ")
  if sys.argv[2] == "D": nums = range(n, -1, -1)   # Descending
  else: nums = range(n)                            # Ascending
  
  nums = list(nums)
  if sys.argv[2] == "R": shuffle(nums)             # Random
  string = "\n".join(map(str,nums)).encode()

  times = []
  for x in range(10):
    with subprocess.Popen(["/usr/bin/time", "-f%U", "./sortA"], stdin=subprocess.PIPE, stdout=subprocess.PIPE, stderr=subprocess.PIPE) as process:
      times.append(float(process.communicate(string)[1][1:-2]))

  avg = average(times)
  print(str(n) + ",", avg)
  print(avg, file=sys.stderr, end="")

Tools

gen

Although I didn’t use this because my data generation script generated the numbers for me already

./gen <n-values> (A|D|R) [seed]

./gen is a program that generates numbers either in ascending, descending or random order
(n-values is actually n+1 values but sure)

GNU time

Version: 1.7
/usr/bin/time --format="%U"

The time program measures the execution time of a program.
We are only interested in the “user execution time” of our programs, so we can add the flag --format="%U%"

Experimentation

All tests would be conducted 10 times, and the average of these timings would be taken to mitigate time inconsistencies caused by environmental factors (computer load, other users, things gone wrong)

The tests would also be run on the same UNSW CSE computer (wagner), under the same user account

Results

sortA

Further Timing

sortB

Further Timing

Analysis

sortA

The sort timing results suggested the implementation of a Bubble or Insertion Sort for sortA’s algorithm.

In the best case scenario where all inputs are already sorted (ascending inputs) -
sortA produced timings whose input of 1000000 numbers resulted in a timing of 0.262s, which was twice that of half as many inputs (500000) at 0.127s.
This suggests that the sort algorithm was either a Bubble Sort or Insertion Sort, as both of these algorithms exhibit a best case time of O(n).

To determine whether this algorithm was a Bubble or Insertion sort, the command was run: python3 -c "print('\n'.join(map(str,[1,*([3]*(1000000-2)),2])))" | time --format="%U" ./sortA > /dev/null
This returned a timing in the 0.2s region which is closer to O(n) time than O(n^2), hence it can be concluded that sortA is an Insertion Sort

The stability sort passed, as the program output the correct order CAB BUT DIS WRONG, shell sorts are not stable by nature

sortB

It is evident that sortB is neither an Insertion Sort nor a Bubble Sort, as a doubling of the number of items does not double proportionally. It is also not a selection sort, the timings do not increase exponentially

sortB’s sorting computation time graph displayed a non-linear trend, where the linear increase of the amount of items to sort increased either logarithmically or exponentially.

On assumption of a Shell Sort, upon dividing the timings by the number of items, a trend can be seen where the average and worst cases have values are the square of the best case timings. This is consistent with the Shell Sort’s complexity.

The stability sort passed, as the program output the correct order CAB

Conclusion

sortA is an Insertion Sort.
sortB is a Shell Sort.

EDIT: I dun guf.
sortA was a shell sort - unstable. –> not enough input
sortB was a bubble sort - it has an early exit boi (best case)