Standard Sorting Algorithms
No description yet. This curated deck is ready for daily study.
Card preview (6)
What happens in a bubble sort?
• We look at two pieces of data in turn. • We rearrange these two pieces of data (if needed) before moving onto the next two pieces of data. • Each time we go from the start of the data set to the end we call it a pass. • We cannot stop passing through the data set until we pass through it and move no pieces of data.
Example - rearrange the below data set so its in order from smallest to largest: 75, 10, 26, 97, 68
FIRST PASS: - Swap 75 and 10 (10, 75, 26, 97, 68) - Swap 75 and 26 (10, 26, 75, 97, 68) - Don’t swap 75 and 97 - Swap 97 and 68 (10, 26, 75, 68, 97) SECOND PASS: - Swap 75 and 68 (10, 26, 68, 75, 97) THIRD PASS (we moved data so needs to be done again) - - Change nothing. - Three passes
What happens in a merge sort?
• We break our data set up into pairs to start off with. • We re-arrange these pairs and then begin to merge these pairs together. • We repeat this process until we merge the whole data set back together and re-arrange that.
Example - Rearrange (75, 10, 26, 97, 68) using a merge sort.
• Break up the list into pairs (68 is ok on its own) • Swap 10 and 75 • Don’t swap 26 and 97 • Don’t swap 68 and nothing • Merge the two nearest pairs from the left together • 10, 26, 75, 97, 68 • Merge the big list and the 68 together • Rearrange • 10, 26, 68, 75, 97
What happens in an insertion sort?
• We create a temporary list. • We work our way through our data set and place each piece of data into the correct location in the temporary list.
Use an insertion sort to sort: 75, 10, 26, 97, 68
• 75 is the first term in the temporary list • 10 is smaller than 75, so it goes to first place in a new list (75 goes to 2) • 26 slots between 10 and 75 • 97 goes at the end • 68 goes in the middle. SHOW EACH INSERTION!