Topics from the Cambridge IGCSE (9-1) Computer Science 0984 syllabus.
7.4 ALGORITHM DESIGN AND PROBLEM SOLVING
SECTION OBJECTIVES 7.4 Understand standard methods of solution. Limited to: - linear search - bubble sort - totalling - counting - finding maximum, minimum and average values
SEARCHING ALGORITHMS There are many methods to search for values with sets of data, here we focus on a simple linear search.
LINEAR SEARCH
IN PYTHON
PSEUDOCODE
VIDEO
<
>
A linear search is a simple algorithm that looks at each item in a list in order until it finds the item it is looking for or gets to the end of the list. Linear searches are simple, but they can be quite inefficient. To learn more about linear searches compared to binary searches click here.
Although a linear search might be slow an inefficient, one of the main uses for a linear search is on an un-sorted list.
In its simplest form a linear search could be like the one below. However, there are a few problems with the search below.
Firstly, it will continue to search the entire list even after it has found the item.
Secondly if it gets to the end of the list and the item is not found then no response is given, whilst this is not a technical problem, it is not user friendly.
my_list ← [2,4,45,3,56,6,75,3,5,8] end ← LEN(my_list) OUTPUT ("What number are you looking for? ") INPUT findme FOR index ← 1 TO end IF my_list[index] = findme THEN OUTPUT ("The number is in the list") END FOR NEXT index
SORTING ALGORITHMS Sorting algorithms are methods of sorting an array (list) of data in to numeric order. There are various sorting methods and each has its advantage and disadvantage. Some algorithms work great for short lists and some are much better suited to large lists. When you try these sorting algorithms it is interesting to add a timer so you can see a comparison of time taken for different data sets.
ABOUT BUBBLE SORT
IN PYTHON
PSEUDOCODE
VIDEO
<
>
The bubble sort is a simple sorting algorithm and you can think of it are a bubble repeatedly going through a list and sorting two items at a time until the entire list is sorted. The bubble will always have to pass the length of the list -1 times to ensure the entire list is sorted. Below is an illustration of a bubble sort, the list in the illustration has 6 numbers therefore 5 passes/loops are needed. You will also notice that during each pass the number of list items that the bubble will need to check is reduced by 1, this is because after the first pass the last number will always be sorted, the second pass the next to last will always be sorted and so on.
Whilst the bubble sort works fine with short lists it is not an efficient sort to use with long list. To make the sort slightly more efficient you could add a condition to end the sort if on any pass no swaps were made as this would mean the list was already sorted.
Adding a while loop to the bubble sort could make the sort very quick if the last part of the list is already sorted, this is because you can break the sort if no changes are needed, this works with the bubble sort because it passes through the list multiple times.
Extended version of the sort - showing how to break the loop if the list is already sorted. This is done by checking if any changes were needed on each complete pass of the list.
LISTLEN = 4 SWAP = TRUE loop while SWAP = TRUE SWAP = FALSE loop COUNTER from 0 to LISTLEN - 1 if VALUES[COUNTER] > VALUES[COUNTER + 1] then TEMPORARY = VALUES[COUNTER] VALUES[COUNTER] = VALUES[COUNTER + 1] VALUES[COUNTER + 1] = TEMPORARY SWAP = TRUE end if end loop end loop
CALCULATION ALGORITHMS You should be confident with making calculations from give data. Here we look at calculating data that is in lists, if you want to learn more about how to put data in lists and list manipulation then click here.
Remember the examiners want to know that you can develop algorithms yourself, so where possible avoid using built in methods that do the algorithm for you such as myList.max()
TOTALLING
COUNTING
MAXIMUM
MINIMUM
AVERAGE
<
>
IN PYTHON
IN PSEUDOCODE To total a list in Pseudocode: my_list ← [2,4,45,3,56,6,75,3,5,8] end ← LEN(my_list) FOR index ← 1 TO end total ← total + my_list[index] NEXT index OUTPUT total
IN PYTHON
IN PSEUDOCODE To count the number of items in a list in Pseudocode: my_list ← [2,4,45,3,56,6,75,3,5,8] end ← LEN(my_list) count = 0 OUTPUT ("What number are you looking for? ") INPUT findme FOR index ← 1 TO end IF my_list[index] = findme THEN count ← count + 1 NEXT index OUTPUT findme "is in the list"count"times"
IN PYTHON
IN PSEUDOCODE To find the maximum value in a list in Pseudocode: my_list ← [2,4,45,3,56,6,75,3,5,8] end ← LEN(my_list) maximum ← my_list[0] FOR index ← 1 TO end IF my_list[index] > maximum THEN maximum ← my_list[index] NEXT index OUTPUT maximum
IN PYTHON
IN PSEUDOCODE To find the minimum value in a list in Pseudocode: my_list ← [2,4,45,3,56,6,75,3,5,8] end ← LEN(my_list) minimum ← my_list[0] FOR index ← 1 TO end IF my_list[index] < minimum THEN minimum ← my_list[index] NEXT index OUTPUT minimum
IN PYTHON
IN PSEUDOCODE To find the average value in a list in Pseudocode: my_list ← [2,4,45,3,56,6,75,3,5,8] end ← LEN(my_list) FOR index ← 1 TO end total ← total + my_list[index] NEXT index average ← total / end OUTPUT average
