objective: Sort the lines.
Sorting Algorithms : Selection sort, Bubble sort, Insertion sort, Merge sort and Quick sort.
Input and output of each sorting algorithm is same but each algorithm has it's unique way to sort the lines.
Mergesort :- It will divide the array as small sub-array's and sort each sub-array then final sort between the sub-arrays.
Quicksort :- It will divide array based on pivot, sort left sub-array and then right sub-array (you can implement it as right first and left as second). But which element to be consider as pivot ? In general, we select first element of the array as pivot and proceed but that always not give the best case. (It's all depend upon the selection of pivot).
Insertion sort :- Sorting one by one element. After k rounds, first k elements of initial array sorted, remaining elements are unsorted. Please note that those remaining elements are also un-altered.
Selection Sort :- Sorting one by one element (either from first or last index), after k rounds, k elements of array sorted (but not the first k elements of the input array), remaining elements are unsorted. Please note that those remaining elements are changed the positions compared to the initial array. But hold on, it swap the first element of the initial array with the Minimum element and second element of the array with the second minimum of the array etc.
Bubble sort :- Sorting one by one element, after k rounds, k elements of the array sorted (but not the first k elements of the input array), remaining elements are unsorted. Please note that those remaining elements are changed the positions compared to the initial array. But hold on, it swap neighbour elements and take to the highest element to the last. (you can implement it as lowest element to the first)
A) If you observe the partway (after some round of the sorting algorithm) : lines are sorted in 3 to 4 different subsize of the orginal size. (I mean range 1-10 sorted, 11-20 sorted, 20-30 sorted. but overall array not sorted). Therefore it is Merge-sort.
B) If you observe the partway (after some round of the sorting algorithm) : first k lines are sorted and remaining lines positions are not changed. Therefore it is Insertion-sort.
C) If you observe the partway (after some round of the sorting algorithm) : Please note that, it's surely neither merge nor insertion sort
i) Whether it can be a Bubble sort ? - NO
Case 1 :- on every pass, let maximum element of the pass get sorted - Maximum element it self is not in the position.
Case 2 :- on every pass, let minimum element of the pass get sorted - after first pass, minimum element is in the position but focus on the maximum element, it should be second element from the right. But that's not the case here.
ii) Whether it can be a selection sort ? - Yes, it is. Please note that, first element of the initial array swapped with smallest element of the array. Second element of the initial array with second smallest element of the array etc.
iii) Whether it can be a Quick sort ? - If the smallest element choosen as pivot. That's possible on first look. But observe the remaining elements after selecting the smallest as pivot, some elements that are higher than the pivot are un-moved and some elements that are higher than the pivot are moved compared to the pivot.
