Sorts

Quick Sort:
1) Select a pivot value. Doesn’t matter which number.
9,5,4,15,3,8,11
Let’s 9 is the pivot
The actual position where the pivot value belongs is called the split point
2) Divide the list into 2 partitions- either side of the split point
(Doesn’t matter what order the numbers are either side of the list) as longas all numbers less than pivot value are on the left, and the one that are greater must be on the right
3,5,4,8 9 15,11
3) So now the 2 numbers are first become pivots:
3 5,4,8 9 15 11
4) and we reorder this
3 5,4,8 9 11 15
5) Same again- more pivots
3 5 4,8 9 11 15
6) Re-order
3 4 5 8 9 11 15
Now ordered :)

Advantages:
Extremely fast- if the partition is always in the middle, there will be log n divisions in a list of length n, and each of the n items needs to be checked against the pivot value to find the split point. So time complexity is O(n log n)

Doesn’t need additional memory, like merge sort

Disadvantages:
If the split points aren’t near the middle, but close to start or end- division uneven.
If split point the first item in the sequenced list, division results in a list of 0 items and list of n-1 items. The list of n-1 items divides into 0 items and n-2 items- and so on (basically not splitting it. Example:
Let’s say this is the list:
9,5,4,15,3,8,11
and lets say we choose 3 as pivot point
9,5,4,15 3 8,11
3 9,5,4,8,11
Then we choose 4 as pivot point
3 4 9,5,8,11
Then we choose 5 as pivot point
3 4 5 9,8,11
Then we choose 8 as pivot point
3 4 5 8 9,11
Then we choose 9 as pivot point
3 4 5 8 9 11
This is slow- time complexity O(n*)

If list very large, and recursion continues too long, may cause a stack overflow and program will crash

How are pivots chosen:
so lets say 9 is split point
9 5,4,15,3,8,11
Goal of partition process is to move items that are on the wrong side of the pivot value whilst converging on split point. Locate 2 positions called leftmark and rightmark at beginning and end of remaining items in list
So 5 becomes leftmark
11 becomes rightmark
so now we have this
9 5(lm),4, 15, 3, 8, 11 (rm)
5 < 9 so move lm to right
4 < 9 so move right
15 > 9 so stop
so lm becomes 15
9 5,4, 15 (lm), 3, 8, 11 (rm)
11 > 9 so move rm left
8 < 9 so stop
9 5, 4, 15 (lm), 3, 8 (rm), 11
Now we switch 15 and 8 and continue moving lm and rm
9 5,4, 8(lm), 3, 15 (rm), 11
Continue moving lm and rm
8 <9 so move lm right
3<9 so move right
15>9 so stop
9,5,4,8,3,15 (lm, rm) 11

15 > 9 so move rm left
9,5,4,8,3 (lm), 15 (rm) 11
rm and lm have now crossed so we stop
position of rm is now split point. Pivot value exchanged with contents of split point
5,4,8, 9, 3,15, 11
so now
3,5,4,8 9 15,11
Look familiar??

Binary Search
Needs to be sorted

Linear Search
Can be unsorted
Starting at the first element / each item is checked... until value is found or end of list reached and not found

Insertion Sort