Linear arrays

Linear arrays

There are four common algorithms we use on a linear array. Although the IB asks only for you to know these at the pseudocode level, I suggest you memorize these for the rest of your life.

You will remember we use arrays to hold values of the same type at contiguous memory locations. In particular, the use of arrays allows us to create "groups" or "clusters" of variables without needing to give a unique variable name to each, but still allowing us to individually index into the elements of the array.

Standard algorithms

• Sequential search
• Binary search
• Bubble sort
• Selection sort

Sequential search

In computer science, linear search or sequential search is a method for finding a target value within a list. It sequentially checks each element of the list for the target value until a match is found or until all the elements have been searched.

Binary Search

In computer science, binary search, also known as half-interval search, is a search algorithm that finds the position of a target value within a sorted array (emphasis mine). Binary search compares the target value to the middle element of the array; if they are unequal, the half in which the target cannot lie is eliminated and the search continues on the remaining half until it is successful. If the search ends with the remaining half being empty, the target is not in the array.

• Click here for a good visualization of binary search

Bubble sort

Bubble sort, sometimes referred to as sinking sort, is a simple sorting algorithm that repeatedly steps through the list to be sorted, compares each pair of adjacent items and swaps them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted.

• This is a good animation which not only shows bubble sorts, but also shows the code stepping through a sort

# Thank you to Alex for submitting this code!!! 

def bubbleSort(list):
    swapped = True
    index_of_last_element = len(list)-1
    while swapped:
        swapped = False 
        for i in range(0,index_of_last_element):    
            if list[i] > list[(i+1)]:
                firstNumber = list[i]
                secondNumber = list[(i+1)]
                list[i] = secondNumber
                list[(i+1)] = firstNumber
                swapped=True
        index_of_last_element -= 1
    return list

Selection Sort

In computer science, selection sort is a sorting algorithm, specifically an in-place comparison sort. The algorithm divides the input list into two parts: the sublist of items already sorted, which is built up from left to right at the front (left) of the list, and the sublist of items remaining to be sorted that occupy the rest of the list. Initially, the sorted sublist is empty and the unsorted sublist is the entire input list. The algorithm proceeds by finding the smallest (or largest, depending on sorting order) element in the unsorted sublist, exchanging (swapping) it with the leftmost unsorted element (putting it in sorted order), and moving the sublist boundaries one element to the right.
I'm grateful to wikipedia for the code below

Sorted sublist == ( )
Unsorted sublist == (11, 25, 12, 22, 64)
Least element in unsorted list == 11

Sorted sublist ==  (11)
Unsorted sublist == (25, 12, 22, 64)
Least element in unsorted list == 12

Sorted sublist == (11, 12)
Unsorted sublist == (25, 22, 64)
Least element in unsorted list == 22

Sorted sublist == (11, 12, 22)
Unsorted sublist == (25, 64)
Least element in unsorted list == 25

Sorted sublist == (11, 12, 22, 25)
Unsorted sublist == (64)
Least element in unsorted list == 64

Sorted sublist == (11, 12, 22, 25, 64)
Unsorted sublist == ( )

Do you understand this?

This site is truly excellent resource to help you visually better understand sorting

Standards

These standards are used from the IB Computer Science Subject Guide

• Describe the characteristics of standard algorithms on linear arrays.

Propose a solution, hypothesis or other possible answer.

Give a sequence of brief answers with no explanation.

Give a detailed account or picture of a situation, event, pattern or process.