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.[2]
Standard algorithms[edit]
- Sequential search
- Binary search
- Bubble sort
- Selection sort
Sequential search[edit]
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.[3]
Binary Search[edit]
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.[4]
Bubble sort[edit]
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. [5]
Do you understand this?[edit]
Standards[edit]
These standards are used from the IB Computer Science Subject Guide[6]
- Describe the characteristics of standard algorithms on linear arrays.
References[edit]
- ↑ http://www.flaticon.com/
- ↑ http://cs50.wiki/Arrays+and+strings
- ↑ https://en.wikipedia.org/wiki/Linear_search
- ↑ https://en.wikipedia.org/wiki/Binary_search_algorithm
- ↑ https://en.wikipedia.org/wiki/Bubble_sort
- ↑ IB Diploma Programme Computer science guide (first examinations 2014). Cardiff, Wales, United Kingdom: International Baccalaureate Organization. January 2012.