IB COMPUTER SCIENCE | Computational Thinking for Topic 4

COMPUTATIONAL THINKING | SEARCH AND SORT

ALSO IN THIS TOPIC
THINKING PROCEDURALLY
THINKING LOGICALLY
THINKING AHEAD
THINKING CONCURRENTLY
THINKING ABSTRACTLY
FLOWCHARTS
YOU ARE HERE | SEARCH AND SORT ALGORITHMS
MORE COMING SOON

SECTION 1 | WHAT ARE 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.

SECTION 2 | BUBBLE SORT

ABOUT BUBBLE SORT
IN PYTHON
IN JAVA
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 = LEN(VALUES)
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

SECTION 3 | SELECTION SORT

ABOUT SELECTION SORT
IN PYTHON
IN JAVA
PSEUDOCODE
VIDEO

The selection sort works by finding the smallest item in the list and moving it to the first unsorted position in the list. The list starts to get sorted from the left and each pass over the entire list is smaller each time as the list gets sorted from left to right.

1: SET: Make the first item in the list the current smallest - index 0 of the list
2: SEARCH: Iterate through the list and if any item is smaller than the current smallest then make that the new current smallest.
3: SWAP: After the smallest item in the list is found swap the first unsorted number for the smallest - index 0 swaps with the smallest item on the first pass
4: INCREMENT: The first item in the list is already sorted so index 0 can now be ignored - index 1 becomes the new smallest.
5: REPEAT: Continue to loop until the list is sorted. Loop length of the list - 1 times.

Unlike the bubble sort, if no swap was needed on any particular pass the selection sort still needs to continue to iterate until the length of the list - 1 iterations are complete.

This code could be streamlined as can be seen below.

In this pseudocode, the SELECTION_SORT function implements the Selection Sort algorithm. The for loop iterates over the unsorted section of the input array. The MIN_INDEX variable stores the index of the minimum element in the unsorted section of the array, and the for loop inside the SELECTION_SORT function finds the index of the minimum element in the unsorted section of the array. The VALUES array stores the input array to be sorted, and the Len function returns the length of an array. The TEMP variable is used to swap the minimum element with the first element in the unsorted section of the array.

SECTION 4 | WHAT ARE SEARCHING ALGORITHMS

The efficiency of algorithms is often measured in time complexity of O(n). Time complexity of O(n) refers to the amount of time it takes for a computer program to complete its task, as the size of the input data (n) increases. In other words, it's a way of measuring how efficient the program is in terms of how quickly it completes its task as the input size grows.

"O" means "order of", and "n" refers to the size of the input data. So, O(n) means that the time it takes for the program to complete its task increases linearly with the size of the input data. In simpler terms, if the input data size doubles, the time it takes to complete the task will approximately double as well.

In the case of a linear search, the time complexity of O(n) means that, as the number of elements in the list increases, the time it takes to find a match also increases linearly.

SECTION 5 | SEQUENTIAL SEARCH

ABOUT LINEAR SEARCH
IN PYTHON
IN JAVA
PSEUDOCODE
VIDEO

A linear search, also known as sequential search, is a method of searching an element in an array or list of elements by iterating through each element one by one until a match is found or all elements have been searched.

It has a time complexity of O(n), where n is the number of elements in the list. This means that the performance of the search is directly proportional to the size of the list, and for large lists, a linear search can become slow.

Evaluation of linear search:

Pros:

Simple to implement
Works for unsorted and sorted lists

Cons:

Slower for larger lists compared to other search algorithms like binary search
Not efficient for searching large data sets

In conclusion, linear search is a basic search algorithm that can be useful in certain situations, such as when the list of elements is small, or when the list is unsorted. However, for larger data sets or sorted lists, other search algorithms like binary search are more efficient.

METHOD sequentialSearch(arr: ARRAY OF INTEGER, target: INTEGER) RETURNS INTEGER
FOR i FROM 0 TO arr.LENGTH - 1
IF arr[i] = target THEN
RETURN i // Return the index of the target
END IF
END FOR
RETURN -1 // Return -1 if the target is not found
END METHOD

// Example usage:
arr <- [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
target <- 5

index <- sequentialSearch(arr, target)
IF index <> -1 THEN
OUTPUT "Element ", target, " is found at index ", index, "."
ELSE
OUTPUT "Element ", target, " is not found in the list."
END I

SECTION 6 | BINARY SEARCH

ABOUT BINARY SEARCH
IN PYTHON
IN JAVA
PSEUDOCODE
VIDEO

A binary search is a search algorithm used to find an element in a sorted list of elements. Unlike linear search, binary search uses a divide-and-conquer approach to search the list by repeatedly dividing the list in half until the target element is found or it is determined that the element is not in the list.

It has a time complexity of O(log n), where n is the number of elements in the list. This means that the performance of the search is logarithmic with respect to the size of the list, and as the list grows larger, the time it takes to find an element remains relatively constant.

Evaluation of binary search:

Pros:

Faster than linear search for large lists
Works only with sorted lists
Efficient use of memory

Cons:

More complex to implement compared to linear search
Not suitable for unsorted lists

In conclusion, binary search is a more efficient search algorithm than linear search for large, sorted lists. However, it requires that the list be sorted, and it can be more difficult to implement compared to linear search.

COMING SOON

METHOD binarySearch(arr: ARRAY OF INTEGER, target: INTEGER) RETURNS INTEGER
low <- 0
high <- arr.LENGTH - 1

WHILE low <= high
mid <- (low + high) DIV 2
IF arr[mid] = target THEN
RETURN mid // Return the index of the target
ELSE IF arr[mid] < target THEN
low <- mid + 1
ELSE
high <- mid - 1
END IF
END WHILE

RETURN -1 // Return -1 if the target is not found
END METHOD

// Example usage:
arr <- [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
target <- 5

index <- binarySearch(arr, target)
IF index <> -1 THEN
OUTPUT "Element ", target, " is found at index ", index, "."
ELSE
OUTPUT "Element ", target, " is not found in the list."
END IF

SECTION 7 | O(n) AND O(log n)

O(n) and O(log n) are measures of the time complexity of an algorithm. They describe how the time it takes for the algorithm to complete its task increases as the size of the input data increases.

"O" means "order of", and "n" refers to the size of the input data.

O(n) refers to algorithms that take longer to complete as the size of the input data grows linearly. This means that if the size of the input data doubles, the time it takes to complete the task approximately doubles as well.

O(log n) refers to algorithms that take longer to complete as the size of the input data grows logarithmically. This means that as the size of the input data increases, the time it takes to complete the task increases more slowly, at a logarithmic rate.

In simpler terms, O(n) means that the time it takes to complete the task grows at the same rate as the size of the input data, while O(log n) means that the time it takes to complete the task grows more slowly as the size of the input data grows.

SEQUENTIAL SEARCH

What is a linear/sequential search algorithm and how does it differ from other search algorithms?
How does the linear search algorithm work and what is its time complexity?
In what situations would a linear search be the best choice for searching through a dataset?
Can you provide an example of a linear search algorithm in action, using either pseudocode or a programming language?
Write structured English bullet-point instructions on conducting a binary search on a given array.
What are some potential limitations and drawbacks of using a linear search algorithm, and how can these be addressed?

What is a binary search algorithm and how does it differ from a linear search?
How does the performance of a binary search algorithm compare to a linear search in terms of time complexity?
What are the conditions that need to be met in order for a binary search to work correctly?
What are some real-world applications of binary search and why is it preferred over other search algorithms in these scenarios?
In a programming language such as Python or Javascript or in Pseudocode produce a binary search on the array given. Explain how your program implements the search.

numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

NAVIGATION

COMING SOON

Tutorials Point Great explanations and samples of various data structures