Sorting Algorithm Descriptions Flashcards
Bubble Sort - Works within one list
Consecutive items compared and swapped until biggest value has ‘bubbled’ to bottom/top - dependent on desired outcome
Every pass places another item into sorted part of list
Algorithm must ensure that comparing and swapping stops short of sorted part
Recognising bubble sort
Inner fixed loop compares each item of the list with next along
Selection Sort
Finds smallest value inside list1
Places it in first position in list2
Dummy value replaces value moved from 1st list
This value must be chosen to be larger than biggest list1 value
Insertion Sort
Assumes first item is already sorted
Takes second and compares it with first item to its left
If first is bigger then swap occurs
Sorted part has increased to 2
This is repeated for remaining list items
Inefficiency of insertion sort
Comparative sort. Builds sorted part one item at a time, Orders first two items Inserts 3rd item relative to first two 4th item relative to first 3 etc Average time = n X n-1 divided by 2
Quick and merge sort formula
Nlogn
Benefits of quick sort (and merge sort)
Divide and conquer method used reduces processor time required to process comparisons and swaps
Creates two half size problems
Combines solutions of small problem to original one
How corrective maintenance could be avoided?
Why is corrective maintenance required?
If error is discovered following app release
Carry out project life cycle correctly during development
- Design, Implementation, Testing etc
Linked list description
New node created to facilitate new data
Link of previous node in list updated to point to new node
New node link directed to next node in the list
How a 2D Array could be used to imlement a maze
2D string array used
Out of bounds represented by X
Full or used areas represented by 1
Empty or unused represented by 0
