2.1.3 - Searching and Sorting Algorithms

Linear search and Binary Search

It can be either

It has to be ordered

• The length of the list is found • The program searches through the values in order from the start using a counter • It stops once the required value has been found or the list ends LESS EFFECTIVE THAN BINARY

• Finds the midpoint of the ordered list • If the midpoint isn’t the required value then it checks if the required value is lower or higher than the midpoint • If value is higher, it disregards all smaller numbers and if the value is lower, it disregards all larger numbers • This repeats until the value is found MORE EFFECTIVE THAN LINEAR

• Bubble sort - temp + swaps • merge sort - sublists • insertion sort - inserts into correct place

• Easy to understand • However, very slow and inefficient

• Very quick comparisons - better for use on large data sets than other sorting methods • Difficult to understand and needs lots of memory *

• Quicker than a bubble sort • Good for inserting extra data into already sorted lists • Not efficient when used on large data sets

• Both less efficient that a merge sort • Both produce a sorted list • Both work from left to right’ • Both swap values • Both have nested loops

• An insertion sort moves the value into its correct postition • A bubble sort repeatdely swaps values until it is in the correct position

• The list is split into sublist and this repeats until each element has its own sublist (sublist with a length of 1) • Each pair of adjacent sublists is compared and combined to form an ordered sublist with length 2 • This process is repeated until there is only one list left and the list will be ordered

• Start at the fron of the list and compare the two elements • If they are in the righ order, don’t swap but if they aren’t swap • Repeat for next 2 elements and repeat until one full pass has been made • Repeatedly perform passes until a pass has been done and no swaps have been made

• Bubble - look for temp + nested loop • Insertion - nested loop + i and i-1 • Merge - lots of sublists

• Don’t know how many swaps are needed • Will keep swapping until in correct position