sorting algorithms

sorting algorithms

1. Bubble sorting

   • An example of a computer algorithm is bubble sort. This is a simple algorithm used for taking a list of jumbled up numbers and putting them into the correct order. The algorithm runs as follows: Look at the first number in the list. Compare the current number with the next number. Is the next number smaller than the current number? If so, swap the two numbers around. If not, do not swap. Move to the next number along in the list and make this the current number. Repeat from step 2 until the last number in the list has been reached. If any numbers were swapped, repeat again from step 1. If the end of the list is reached without any swaps being made, then the list is ordered and the algorithm can stop.
   • This algorithm could be used to sort the following list: 3, 2, 4, 1, 5 The first loop of the algorithm would produce: 3, 2, 4, 1, 5 (2<3 so the two values are swapped) 2, 3, 4, 1, 5 (3<4 so the two values are not swapped) 2, 3, 4, 1, 5 (1<4 so the two values are swapped) 2, 3, 1, 4, 5 (4<5 so the two values are not swapped) 2, 3, 1, 4, 5 (First pass completed) Values were swapped so the algorithm needs to run again. The second loop of the algorithm would start with the final list and run again as follows: 2, 3, 1, 4, 5 (2<3 so the values are not swapped) 2, 3, 1, 4, 5 (1<3 so the values are swapped) 2, 1, 3, 4, 5 (3<4 so the values are not swapped) 2, 1, 3, 4, 5 (4<5 so the values are not swapped) 2, 1, 3, 4, 5 (Second pass completed) 2, 1, 3, 4, 5 (1<2 so the values are swapped) 1, 2, 3, 4, 5 (2<3 so the values are not swapped) 1, 2, 3, 4, 5 (3<4 so the values are not swapped) 1, 2, 3, 4, 5 (4<5 so the values are not swapped) 1, 2, 3, 4, 5 (Third pass completed) Values were swapped

2. Binary Search

   • Binary search is an algorithm used to search quickly through an index. It can jump to the index and then jump through the list of numbers. It skips through the data to get closer to the required value by halving the amount of records with each jump.
   • Binary search is an algorithm used to search quickly through an index. It can jump to the index and then jump through the list of numbers. It skips through the data to get closer to the required value by halving the amount of records with each jump. For example, when searching through an alphabetical sequence for a record starting with 'r' it would first jump to the middle of the alphabet, 'm', and decide if 'r' is before or after 'm'. Then it would jump half way between 'm' and 'z', to 't', and so on: a, b, c, d, e, f, g, h, i, j, k, l, M, n, o, p, q, r, s, t, u, v, w, x, y, z n, o, p, q, r, s, T, u, v, w, x, y, z n, o, P, q, r, s q, R, s R In this example, the target value 'r' is reached in five steps. If the data was searched in sequential order from the start, looking at each letter, it would have taken 18 steps.

3. linear search

   • A linear checks each item of the list in turn to see if its the correct one. It stops when it either finds the item its looking for, or has checked every time
   • 1) look at the first item in the unordered list. 2) If this is the item you're looking for, then stop the search - you've found it. 3) if not, then look at the next item in the list. 4) Repeat steps 2 and 3 until you find the item that you're looking for or you've checked every item