SLR 25/ Algorithms Flashcards
Explain Bubble Sort
Repeatedly steps through a list, comparing each pair of adjacent items and swapping them if they are in the wrong order.
How might Bubble Sort be used
Rarely used, as it is so simple. Typically used to introduce the concept of a sorting algorithm to computer science students.
Explain Insertion Sort
Builds the final, sorted array or list one item at time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort or merge sort.
How might Insertion Sort be used
Useful for sorting short lists, larger lists that are almost sorted or small sub-lists.
Explain Binary Search
Only works if records are in sequence. It involves accessing the middle record in the file and determining if the target record has been found or, if not, if it is before or after the middle record in the sequence. This process is repeated on the part of the file where the target record is expected to be until it is found.
How might Binary Search be used
Used to maintain and search database indexes, quickly search a binary tree of data items, or construct and then search syntax trees for compilers. It can also be used for implementing routing in a router, data compression code and much more.
Explain Linear Search
Involves examining each entry in turn until the target is found or the end of the file is reached. Unless the file is in some useful order, a serial search will need to be used.
How might Linear Search be used
One of the most basic search algorithms. As such, it is rarely used beyond the basics of teaching. It can be useful for searching small lists. It does have one advantage over binary searches – the sorting of data items is not required before searching begins.
