In other languages

Help the wiki!

The Scratch Wiki is made by and for Scratchers. Do you want to contribute?

Learn more about joining as an editor!

See discussions in the Community Portal

Sorting Values

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.

Bubble Sort

Below is the bubble sort algorithm in Scratch which is one of many possible methods for sorting data:

when green flag clicked
set [pass v] to [0]
set [swaps v] to [0]
repeat until <<(pass) > [0]> and <(swaps) = [0]>>
  set [item v] to [0]
  change [pass v] by (1)
  set [swaps v] to [0]
  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

Below is the insertion sort algorithm in Scratch:

when green flag clicked
set [item v] to [2]
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) < [1]>>
    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

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. Note that quicksort uses recursion.

define Quicksort (_start) (_end)
if<((_end) - (_start)) < [2]>
if<<(_end) > (_start)> and <(item (_start) of [list v]) > (item (_end) of [list v])
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])>
change [a v] by (1)
else
if<(item (b) of [list v]) > (item (_end) of [list v])>
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])>
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 we compare every element in the list to the last element (for simplicity, we use the last one). This is called the 'pivot element'. We then divide the list into two sublists: one which has every element smaller than the pivot, and one with every element larger than the pivot.
  • We keep dividing these sublists into smaller and smaller sublists, until they are, at most, 2-long.
  • The list is now sorted.

Example Projects

See Also

  • This page was last modified on 15 July 2014, at 00:58.