Revision as of 18:39, 8 January 2019 by Jvvg (talk | contribs) (more specific categories)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Document stub.png This article is a stub. It may be incomplete, unfinished, or have missing parts/sections. If the article can be expanded, please do so! There may be suggestions on its talk page. (September 2017)
DocumentInQuestion.png It has been suggested that this page's contents be merged with the page Sorting Values. You can discuss this on the page's talk page. (September 2017)
SandCastleIcon.png This page has links to websites or programs not trusted by Scratch or hosted by Wikipedia. Remember to stay safe while using the Internet, as we can't guarantee the safety of other websites.

A sorting algorithm is an algorithm used to sort lists (aka arrays), usually in ascending order. This article will explain how to implement some common sorting algorithms in Scratch.

Tutorials

These tutorials will assume that the name of the list being sorted is "list", the items of which are simply the numbers 1 to 50 in a random order.

The time complexity of these algorithms will be denoted in Big O notation - as in, if the time taken to sort a list with n elements is equal to the number of elements, its time complexity will be O(n).

All of these sorts will need the same custom block:

define swap (m) and (n)
set [a v] to (item (m) of [list v])
set [b v] to (item (n) of [list v])
replace item (m) of [list v] with (b)
replace item (n) of [list v] with (a)

Bubble Sort

Bubble sort is one of the simplest sorting algorithms. However, it is relatively slow - its time complexity is O(n2). Bubble sort works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted.

define bubble sort
set [i v] to [0]
repeat (length of [list v])
 change [i v] by (1)
 set [j v] to [0]
 repeat ((length of [list v]) - (i))
  change [j v] by (1)
  if <(item (j) of [list v]) > (item ((j) + (1)) of [list v])> then
   swap (j) and ((j) + (1)):: custom
  end
 end
end

Insertion Sort

Insertion sort is another simple sorting algorithm, and like bubble sort, its time complexity is O(n2). Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list. At each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain.

define insertion sort
set [i v] to [0]
repeat (length of [list v])
 change [i v] by (1)
 set [j v] to ((i) - (1))
 repeat until <not <(item (j) of [list v]) > (item ((j) + (1)) of [list v])>>
  swap (j) and ((j) + (1)):: custom
  change (j) by (-1)
 end
end

Heap Sort

Heap sort is a very complex but very efficient and fast algorithm - its time complexity is O(n log n). Heap sort involves two stages: the first stage arranges the elements into a heap structure, and the second stage takes the top element of the heap (i.e. the element with the largest value) and puts it at the start of the sorted list.

This algorithm requires three custom blocks instead of one, due to its complexity: "heapify", "siftDown", and the actual block itself, "heap sort".

define siftDown (st) to (en)
set [root v] to (st)
repeat until <((root) * (2)) > (en)>
 set [child v] to ((root) * (2))
 set [swap v] to (root)
 if <(item (swap) of [list v]) < (item (child) of [list v])> then
  set [swap v] to (child)
 end
 if <<not <((child) + (1)) > (en)>> and <(item (swap) of [list v]) < (item ((child) + (1)) of [list v])>> then
  set [swap v] to ((child) + (1))
 end
 if <(swap) = (root)> then
  stop [this script v] //note: this only stops the custom block, not the script running it.
 else
  swap (root) and (swap):: custom
  set [root v] to (swap)
 end
end

define heapify
set [j v] to ([ceiling v] of (((length of [list v]) - (1)) / (2)))
repeat until <(n) < [0]>
 siftDown (j) to (length of [list v])
 change [j v] by (-1)
end

define heap sort
set [i v] to (length of [list v])
heapify
repeat until <not <(i) > [1]>>
 swap (i) and (1):: custom
 change [i v] by (-1)
 siftDown (1) to (i)
end

Radix LSD Sort

A least significant digit (LSD) Radix sort is one of the quickest sorts - its time complexity is O(k*n) where k is the character length of the element with the largest value and n is the number of keys being sorted. A Radix LSD sort:

  1. Takes the least significant digit of each key,
  2. Groups the keys based on that digit, but preserving the original order otherwise,
  3. Repeats the grouping process with each more significant digit.

In this implementation, each group is put into a list of its own, from 0 to 9. To do this efficiently, however, this script makes use of "hacked" blocks to dynamically put each element in the correct "bucket".

//"atomic" is "run without screen refresh"
define atomic
change [i v] by (1)
repeat (10)
 if <(letter (j) of (item (i) of [list v])) = (k)> then
  add (item (i) of [list v]) to (k) // this is a hacked block
 end
 change [k v] by (1)
end

define radix lsd sort
set [i v] to [0]
repeat (length of [list v])
 change [i v] by (1)
 repeat until <(length of (item (i) of [list v])) = (length of (length of [list v]))> // assuming the list is numbers from 1 to n in random order, "length of list" is assumed to be n.
  replace item (i) of [list v] with (join [0] (item (i) of [list v])
 end
end
set [j v] to (length of (length of [list v]))
repeat (j)
 set [i v] to [0]
 delete (all v) of [0 v]
 delete (all v) of [1 v]
 delete (all v) of [2 v]
 delete (all v) of [3 v]
 delete (all v) of [4 v]
 delete (all v) of [5 v]
 delete (all v) of [6 v]
 delete (all v) of [7 v]
 delete (all v) of [8 v]
 delete (all v) of [9 v]
 repeat (length of [list v])
  set [k v] to [0]
  atomic
 end
 set [k v] to [0]
 set [i v] to [0]
 repeat (10)
  set [m v] to [0]
  repeat (length of (k):: list) // this is a hacked block
   change [i v] by (1)
   change [m v] by (1)
   replace item (i) of [list v] with (item (m) of (k)) // this is a hacked block
  end
  change [k v] by (1)
 end
 change [j v] by (-1)
end

See Also