1. What is a bubble sort?
->Bubble sort is a simple sorting algorithm, it works by repeatedly stepping through the list to be sorted comparing each pair of adjacent items and swapping if they are in the wrong order. First pass bubbles out the largest element and places it in the last position and second pass places the second largest element in the second last position and so on.
Thus in the last pass smallest element is placed in the first position. The running time is the total number of comparisons that is n(n-1)/2 which implies O(n2) time complexity.
2. What is Insertion Sort?
-> Insertion sort is a simple comparison sorting algorithm, every iteration of insertion sort removes an element from the input data and insert it into the correct position in the already sorted list until no input element remains. The running time is the total number of comparisons that is n(n-1)/2 which implies O(n2) time complexity.
3. What is Selection Sort?
->Insertion sort is a simple comparison sorting algorithm, the algorithm works as follows:
1. Find the minimum value in the list.
2. Swap it with the minimum value in the first position.
3. Repeat the steps above for the remainder of the list (starting at the second position and advancing each time). The running time is the total number of comparisons that is n(n-1)/2 which implies O(n2) time complexity.
4. What is Merge Sort?
->Merge sort is an O(nlogn) comparison-based divide and conquer sorting algorithm, it works as follows:
1. If the list is of length 0 or 1, then it is already sorted.
2. Divide the unsorted list into two sub lists of about half the size.
3. Sort each sublist recursively by re-applying merge sort algorithm.
4. Merge the two sublists back into one sorted list. If the running time of merge sort for a list of length n is T(n) then the recurrence relation is T(n) = 2T(n/2) + n, thus after simplifying the recurrence relation T(n) = O(nlogn).
5. What is Quick Sort?
-> Quick sort sorts by employing a divide and conquer strategy to divide a list into two sub-lists. The steps are:
1. Pick an element, called a pivot, from the list.
2. Reorder the list so the elements which are less than the pivot come before the pivot and the elements greater than pivot come after it. After this partitioning the pivot is in its final position.
3. Recursively sort the sub-list of lesser elements and the sub-list of greater elements. The running time complexity for worst case is O(n2) and for best and average case it is same i.e., O(nlogn).