Final answer:
To create a Selection Sort block in Snap!, create a new block and use a script that implements the selection sort algorithm. Similarly, create a Binary Search block using a script that implements the binary search algorithm. To create a list filled with 30 random integer numbers, initialize an empty list and use a loop to insert random numbers. Then, call the Selection Sort block to sort the list, followed by the Binary Search block to find a key in the sorted list.
Step-by-step explanation:
Selection Sort Block in Snap!
To create a block in Snap! that uses the selection sort algorithm to sort a given list, right-click on the Blocks palette and select New Block. Name the block as 'Selection Sort'. Inside the block, use the following script:
when I receive [Selection Sort v]
set [list v] to (join [list v] [])
repeat (length of [list v])
set [minIndex v] to (0)
set [minValue v] to (item (minIndex) of [list v])
repeat with [i v] from (1) to (length of [list v])
if <item (i) of [list v]> < (minValue) then
set [minIndex v] to (i)
set [minValue v] to (item (i) of [list v])
delete (join [minIndex] of [list v]) from [list v]
insert (minValue) at (1) of [sorted v]
broadcast [Sorted v]
end
This script uses a loop to sort the given list using the selection sort algorithm. It compares each item in the list with the minimum value found so far and updates the minimum value and its index accordingly. Finally, it broadcasts a message indicating that the list has been sorted.
Binary Search Block in Snap!
To create a block in Snap! that uses binary search to find a key in a list, follow the same steps as before and name the block as 'Binary Search'. Inside the block, use the following script:
when I receive [Binary Search v]
set [key v] to (0)
set [list v] to (join [list v] [])
set [low v] to (1)
set [high v] to (length of [list v])
repeat until (low) > (high)
set [mid v] to (((low) + (high))/2)
if <item (mid) of [list v]> = [key v] then
broadcast [Found v]
end
else
if <item (mid) of [list v]> < [key v] then
set [low v] to ((mid) + (1))
else
set [high v] to ((mid) - (1))
broadcast [Not Found v]
end
This script implements the binary search algorithm to find the key in the given list. It keeps track of a low and high index within the list and compares the middle item with the key. If the middle item matches the key, it broadcasts a message indicating that the key has been found. Otherwise, it adjusts the low or high index based on the comparison and repeats the process.
Creating a List with 30 Random Integer Numbers
To create a list filled with 30 random integer numbers in Snap!, use the following script:
set [list v] to []
repeat (30)
set [num v] to (pick random (-100) to (100))
insert (num) at (length of [list v]) of [list v]
This script initializes an empty list, then repeats 30 times. In each iteration, it generates a random integer number using the 'pick random' block and inserts it at the end of the list. The resulting list will have 30 random integer numbers between -100 and 100.
Sorting the List and Performing Binary Search
To sort the list created above and perform a binary search with the last two digits of your U of M student number as the key, you can use the following script:
broadcast [Selection Sort v]
broadcast [Binary Search v]
This script broadcasts the 'Selection Sort' message to sort the list, and then broadcasts the 'Binary Search' message to perform the binary search with the key. Finally, depending on the result of the search, you can add appropriate output blocks to show whether the key exists in the sorted list or not.