This tutorial explains how to sort a list either alphabetically or numerically. The methods of sorting used in this tutorial are known as bubble sort, insertion sort, and quicksort.

## Slow Algorithms

### 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.

```when green flag clicked
set [pass v] to 
set [swaps v] to 
repeat until <<(pass) > > and <(swaps) = >>
set [item v] to 
change [pass v] by (1)
set [swaps v] to 
repeat ((length of [data v]) - (1))
change [item v] by (1)
if <(item ((item) + (1)) of [data v]) < (item (item) of [data v])> then
set [value v] to (item ((item) + (1)) of [data v])
replace item ((item) + (1)) of [data v] with (item (item) of [data v])
replace item (item) of [data v] with (value)
change [swaps v] by (1)
end
end
end
```

This script sorts the values from least to greatest.

#### How it Works

• This script sorts the data in the list "data"
• It does this by constantly comparing to values that are side-by-side on the list
• If a value needs to be moved, it is saved in the variable 'value' and then moved to the correct location
• It repeats this until no changes are made to the list

### 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.

```when green flag clicked
set [item v] to 
repeat until <(length of [data v]) < (item)>
set [insert location v] to ((item) - (1))
repeat until <<(item (insert location) of [data v]) < (item (item) of [data v])> or <(insert location) < >>
change [insert location v] by (-1)
end
insert (item (item) of [data v]) at ((insert location) + (1)) of [data v]
delete ((item) + (1)) of [data v]
change [item v] by (1)
end
```

This script sorts the values from least to greatest.

#### How it Works

• This script sorts the data in the list "Text"
• The list has 2 parts
• The first part is already sorted and the second part waiting to be sorted
• When the program gets to an unsorted value in a list the program moves the value into its proper location in the first part of the list
• When the program gets the end of the list all of the values have been sorted from least to greatest

## Fast Algorithms

### Quicksort

Below is a quicksort algorithm implemented in Scratch. While in the worse-case, quicksort operates at speeds similar to the Bubble or Insertion sorts, such cases are rare. Quicksort is typically much more efficient. Quicksort works by selecting an arbitrary value (the "pivot") and then placing all elements less than that pivot before it and all elements greater after it. Then it repeats this process on all elements before the pivot, then on all elements behind the pivot. Note that quicksort uses recursion.

```define Quicksort (_start) (_end)
if<((_end) - (_start)) < > then
if<<(_end) > (_start)> and <(item (_start) of [list v]) > (item (_end) of [list v])>> then
set [store v] to (item (_start) of [list v])
replace item (_start) of [list v] with (item (_end) of [list v])
replace item (_end) of [list v] with (store)
end
stop [this script v]
end
set [a v] to (_start)
set [b v] to ((_end) - (1))
repeat until <not <(a) < (b)>>
if<(item (a) of [list v]) < (item (_end) of [list v])> then
change [a v] by (1)
else
if<(item (b) of [list v]) > (item (_end) of [list v])> then
change [b v] by (-1)
else
set [store v] to (item (a) of [list v])
replace item (a) of [list v] with (item (b) of [list v])
replace item (b) of [list v] with (store)
end
end
end
if<(item (a) of [list v]) < (item (_end) of [list v])> then
change [a v] by (1)
end
set [store v] to (item (a) of [list v])
replace item (a) of [list v] with (item (_end) of [list v])
replace item (_end) of [list v] with (store)
Quicksort (_start) ((a) - (1))
Quicksort ((a) + (1)) (_end)

when green flag clicked
Quicksort (1) (length of [list v])
```

#### How it Works

• This script sorts the data in the list "list".
• The general idea is that each element is compared in the list to the last element (for simplicity, the last one is used). This is called the 'pivot element'. The list is then divided into two sublists: one which has every element smaller than the pivot, and one with every element larger than the pivot.
• These sublists keep dividing into smaller and smaller sublists, until they are, at most, 2-long.
• The list is now sorted.

### Merge Sort

Merge sort splits a list into two parts, and first sorts the items of each part separately. Then, merge sort repeats comparing the first item in each part, and moving the lower one to the end of the final list, until the parts run out of items. When this happens, the list is in order. Like quicksort, merge sort uses recursion.

The following script sorts items `(start :: custom-arg)` to `(end :: custom-arg)` of "list" with merge sort, calling itself to sort each half of the range before merging them. The variables `(x)` and `(x2)` represent the start of what remains to be merged of each half.

```define merge sort (start) to (end)
if <(start) = (end)> then
stop [this script v] // any single item is always in order
end
merge sort (start) to ((round (((start) + (end)) / (2))) - (1))
merge sort (round (((start) + (end)) / (2))) to (end)
set [x v] to (start)
set [x2 v] to (round (((start) + (end)) / (2)))
repeat until <<(x) = (end)> or <(x2) > (end)>>
if <(item (x2) of [list v]) < (item (x) of [list v])> then
insert (item (x2) of [list v]) at (x) of [list v]
change [x2 v] by (1)
delete (x2) of [list v]
change [x v] by (1)
else
change [x v] by (1)
end
end
```

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.

```define atomic // run without screen refresh
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

set [i v] to 
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  (item (i) of [list v])
end
end
set [j v] to (length of (length of [list v]))
repeat (j)
set [i v] to 
delete [all] of [0 v] //get the input "all" in the number-only space by copy-pasting
delete [all] of [1 v]
delete [all] of [2 v]
delete [all] of [3 v]
delete [all] of [4 v]
delete [all] of [5 v]
delete [all] of [6 v]
delete [all] of [7 v]
delete [all] of [8 v]
delete [all] of [9 v]
repeat (length of [list v])
set [k v] to 
atomic
end
set [k v] to 
set [i v] to 
repeat (10)
set [m v] to 
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
```

## Example Projects

Cookies help us deliver our services. By using our services, you agree to our use of cookies.