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) |
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) |
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(n^{2})
. 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(n^{2})
. 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:
- Takes the least significant digit of each key,
- Groups the keys based on that digit, but preserving the original order otherwise,
- 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