COMPUTER SCIENCE CAFÉ
  • WORKBOOKS
  • BLOCKY GAMES
  • GCSE
    • CAMBRIDGE GCSE
  • IB
  • A LEVEL
  • LEARN TO CODE
  • ROBOTICS ENGINEERING
  • MORE
    • CLASS PROJECTS
    • Classroom Discussions
    • Useful Links
    • SUBSCRIBE
    • ABOUT US
    • CONTACT US
    • PRIVACY POLICY
  • WORKBOOKS
  • BLOCKY GAMES
  • GCSE
    • CAMBRIDGE GCSE
  • IB
  • A LEVEL
  • LEARN TO CODE
  • ROBOTICS ENGINEERING
  • MORE
    • CLASS PROJECTS
    • Classroom Discussions
    • Useful Links
    • SUBSCRIBE
    • ABOUT US
    • CONTACT US
    • PRIVACY POLICY

COMPUTATIONAL THINKING | SEARCH AND SORT

ON THIS PAGE
SECTION 1 | WHAT ARE SORTING ALGORITHMS​
SECTION 2 | BUBBLE SORT​
SECTION 3 | SELECTION SORT​
SECTION 4 | WHAT ARE SEARCHING ALGORITHMS​
​SECTION 5 | SEQUENTIAL SEARCH
​SECTION 6 | BINARY SEARCH
​SECTION 7 | O(n) AND O(log n)
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

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

    
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.
Picture
SEQUENTIAL SEARCH
  1. What is a linear/sequential search algorithm and how does it differ from other search algorithms?
  2. How does the linear search algorithm work and what is its time complexity?
  3. In what situations would a linear search be the best choice for searching through a dataset?
  4. Can you provide an example of a linear search algorithm in action, using either pseudocode or a programming language?
  5. Write structured English bullet-point instructions on conducting a binary search on a given array.
  6. What are some potential limitations and drawbacks of using a linear search algorithm, and how can these be addressed?
  1. What is a binary search algorithm and how does it differ from a linear search?
  2. How does the performance of a binary search algorithm compare to a linear search in terms of time complexity?
  3. What are the conditions that need to be met in order for a binary search to work correctly?
  4. What are some real-world applications of binary search and why is it preferred over other search algorithms in these scenarios?
  5. 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]
Picture
NAVIGATION
COMING SOON
Tutorials Point    Great explanations and samples of various data structures
Picture
SUGGESTIONS
We would love to hear from you
SUBSCRIBE 
To enjoy more benefits
We hope you find this site useful. If you notice any errors or would like to contribute material then please contact us.