Sort Algorithms

Question 1

Linear Search

Answer 1

From left to right -> 1 2 3 4 5 6
Search for a specific element
Goes over each element and compares it to the target element
Ω(1)

Question 2

Binary Search

Answer 2

Divine and conquer
Reduce the area by half each time
Repeats until array is 0
Calculate the mid point
Array must be sorted
uses a target start end middle
If number is > then target it goes to the left
1 2 3 4 5 6
      ^
starts here
Best case
O(log n)
Worst case
When the element is in the last part of array or doesn't exsist
Ω(1)

Question 3

Bubble Sort

Answer 3

Higher value element to the right
->10
Lower to the left
 1 so swap 1 2 add 1 to swap counter each time it goes over an element
123
2<3
So end swap counter resets
Worst case when it's in reverse order
O(n^2)
Ω(n)

Question 4

Selection Sort

Answer 4

Find the smallest unsorted element and add it to the end of the list
312
132
Worst case
going over each of the n elements n times since it takes only 1 n element at the time
O(n^2)
Ω(n^2)

Question 5

Insertion Sort

Answer 5

slides elements over out of the way
321
takes 3 compares it to 2
2 shift it over
31
places 2 before 3
231
worst case
The array is in reverse order
we have to shift n elements n position each time we make an insertion
O(n^2)
Ω(n)

Question 6

Merge Sort

Answer 6

Uses recursion
Sorts right and left half then merge them together
521364
take left half
521
^
set it aside since its already sorted single element is sorted
The right part
 2 1
  ^
sort left half
is 2
and does it again
then compares the one with the lowest value
2 and 1
and does it again with 2 no compared to nothing
(assuming >n -1)
then merge 12 together and compares it with 5
1 goes 1st
5 and 2 then get compared
125

Worst
we have to split n elements up and recombine them effectively doubling the sorted sub-arrays as we build them up
Best
The array is already sorted
O(n log n)
Ω(n log n)