Mphasis Searching and Sorting Quiz 1

Quick sort performs the worst if arranged in alphabetic/ ascending order. Quicksort is a well-known sorting algorithm that, on average, makes O(n log n) comparisons to sort n items. However, in the worst case, it makes O(n2) comparisons.

The time complexity or O(n) of Binary search is log n (base 2) as the "domain" halves after each comparison, so if you half a million 21 times you will reach 1 answer which will be the number you need.

Example:

for 4 numbers in a binary search we will need at most 3 i.e log 4(base 2) + 1 = 3.

for 8 numbers in a binary search we will need at most 4 i.e. log 8 +1 =4

for 15 numbers in a binary search we will need at most 4 i.e log 15 + 1 = 4.

First Pass:
( 5 1 4 2 8 ) –> ( 1 5 4 2 8 ), Here, algorithm compares the first two elements, and swaps since 5 > 1.
( 1 5 4 2 8 ) –> ( 1 4 5 2 8 ), Swap since 5 > 4
( 1 4 5 2 8 ) –> ( 1 4 2 5 8 ), Swap since 5 > 2
( 1 4 2 5 8 ) –> ( 1 4 2 5 8 ), Now, since these elements are already in order (8 > 5), algorithm does not swap them.

Second Pass:
( 1 4 2 5 8 ) –> ( 1 4 2 5 8 )
( 1 4 2 5 8 ) –> ( 1 2 4 5 8 ), Swap since 4 > 2
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
Now, the array is already sorted, but our algorithm does not know if it is completed. The algorithm needs one whole pass without any swap to know it is sorted.

Third Pass:
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )

arr[] = 64 25 12 22 11

// Find the minimum element in arr[0...4]
// and place it at beginning
11 25 12 22 64

// Find the minimum element in arr[1...4]
// and place it at beginning of arr[1...4]
11 12 25 22 64

// Find the minimum element in arr[2...4]
// and place it at beginning of arr[2...4]
11 12 22 25 64

The Breadth First Search explores every node once and puts that node in queue and then it takes out nodes from the queue and explores it's neighbors.

Bubble sort is slowest among the given sorting techniques.
More about compelxity - https://prepinsta.com/time-complexities-placements/

Bubble sort, also referred to as comparison sort, is a simple sorting algorithm that repeatedly goes through the list, compares adjacent elements and swaps them if they are in the wrong order. This is the most simplest algorithm and inefficient at the same time

In first iteration 4 and 3 will swap after that array become sorted so in next iteration no swap will occur hence, we will come out from the nested for loop.

Selection sort makes O(n) swaps which is minimum among all sorting algorithms mentioned above.