Chapter 1 Algorithms : Sorting Algo Flashcards
How to do QUICK SORT
1) circle the pivot which is most left number in each sub list
2) if ascending descending , put all the numbers lower to the left and higher to the right of the sub list but the ORDER OF THIS MUST BE MAINTAINED EACH TIME
3) once this done, BOX THE PIVOT to let exmainer know its been used snd ordered
4) now continue for the new sublists made until ALL THE PIVOTS HAVE BEEN BOXED
how to count the number of COMPARISONS MADE each time for quick sort
What about sublists of 1 , just the pivot ?
Just count the number of un pivot and un boxed numbers each row , this is equal to number of comparisons
But just count them , pivot compared with 1,2 etc
SUBLISTS OF 1 HAVE NOTHING TO COMPARE TO SO THEY JUST GET BOXED UP WITH 0 COMPARISONS
What’s worse case scenarios for the quick sort and thus how to find complexity
Worse case = reverse / already in order
This gives the comparisons 4,3,2,1 which gives triangle numbers
However this must be adjusted one back , giving 1/2n (n-1)
Still QUADRATIC COMPLEXITY HOWEVER
What is n when doing the nth term for complexity, basic,sly how many passes must be made to ensure all ordered
N = number of items to be ordered snd number of passed
How to do bubble sort
Compare first two, which ever bigger pushed ti right, and then this continues happening with the next two items
By the end of the first pass, the BIGGEST NUMBER SHOULD HAVE BUBBLED TO THE TOP
The bubbled ti the top, MAKE SURE TO CAP IT AND IGNORE IT FOR THE NEXT ONE
End when NO MORE SWAPS HAVE BEEN MADE
- however that line still counts for comparisons!
How many comparisons made in bubble sort for each pass?
Thus what’s its complexity
Each pass the min number of comparisons made must be one less than the number of in the list
(So first pass with 8 elements = 7 comparisons must be made)
Thus it follows it goes 5,4,3 2 1 etc
Thus triangle numbers aagain = order of n2
I’d doing descending order, how to adjust bubble sort
Just make biggest for to left, in this case the SMALEEST WILL BUBBLE TO LEFT
Remember if there are n terms, for bubble and quick sort there will be n passes
However on the last pass maybe no swap !
How to the shuttle sort
First put a line between first rwo numbers
- then check if the number closest to line is bigger or smaller than one on left
- if match condition then swap. Keep doing this until NO MORE SWAPS occur = right position
Record this
Now for next pass, make line one unit BIGGER and repeat
End when the line can no longer move go next one up = sorted
Remember a comparison is still made if no swap happens!
So if jtsbigger it still has to check left tk see , don’t forget !
Shuttle sort complexity?
Check the Worde case = reverse ordered
Find its triangle numbers = n2
