C7 - Common/Standard algorithms

Bubble sort

Bubble sort has a worst-case and average complexity of O(n2), where n is the number of items sorted. Bubble sort performance over an already sorted list is O(n).

The position of elements in bubble sort plays an important role in determining performance. Large elements at the beginning do not pose a problem as they are easily swapped. The small elements toward the end move to the beginning slowly. As such, these elements are called rabbits and turtles.

The bubble sort algorithm can be optimized by placing larger elements in the final position. After every pass, all elements after the last swap are sorted and do not need to be checked again, thereby skipping the tracking of swapped variables.

Exercise

Create and comment a 'Bubble Sort' algorithm to improve the effectiveness of code using appropriate data structures

Show an example of code you have produced that uses a 'bubble sort' algorithm with it clearly commented in python.

Quick sort

Exercise

Create and comment a quick sort algorithm to improve the effectiveness of code using appropriate data structures

Show an example of code you have produced that uses a 'Quick Sort' algorithm with it clearly commented in python.

Insertion sort

Exercise

Create and comment an Insertion sort algorithm to improve the effectiveness of code using appropriate data structures

Show an example of code you have produced that uses an 'Insertion Sort' algorithm with it clearly commented in python.

Linear Search

Exercise

Create and comment a linear search algorithm to improve the effectiveness of code using appropriate data structures

Show an example of code you have produced that uses a 'Linear Search' algorithm with it clearly commented in python.

Binary Search

Exercise

Create and comment a Binary Search algorithm to improve the effectiveness of code using appropriate data structures

Show an example of code you have produced that uses a 'Binary Search' algorithm with it clearly commented in python.

Count Occurrence

Exercise

Create and comment a Count Occurrences algorithm to improve the effectiveness of code using appropriate data structures

Show an example of code you have produced that uses a 'Count Occurrences ' algorithm with it clearly commented in python.

Input validation

Exercise

It is common to have to validate the input of items that are to be stored in an array.

Create the algoritm below in python and explain what you think it does.

FOR counter FROM 0 TO 4 Do
  RECEIVE score [counter] FROM (INTEGER) KEYBOARD
  WHILE score [counter] ˂0 OR score [counter] ˃ 50 DO
    SEND (“The score you entered was not valid; please enter a score between 
    0 and 50”) TO DISPLAY
    RECEIVE score [counter] FROM (INTEGER) KEYBOARD
  END WHILE
END FOR

LIFO

An array is a random access data structure, where each element can be accessed directly and in constant time. A Queue is a linked list with sequential access where each element can be accesed only in particular order. The Last in First Out data structure is a structure that returns data sequentially from the end of the list.

Exercise

Create a LIFO data structure that asks for an input(a name) with each letter being entered seperately and then returns the name in reverse. e.g. if "G" "e" "o" "r" "g" "e" is entered then egroeg is returned

FIFO

The queue is an abstract data type that obeys a First In First Out (FIFO) rule. It is used where elements are processed in the order in which they arrive.

Exercise

Create a psudeo print queue which takes in print jobs(A string) queues them up and then outputs them in the order that they we sent when the queue is cleared