We make at most k comparisons for the kth pass and we make a total of n-1 comparisons, summing we can conclude Looking at the algorithm, with each pass an element is added to the sublist of ordered elements at the front of the list. The outer while loop is clearly iterating over a variable dependent on n, the inner loop is not as obvious. This time we don't have a for loop nested within a while loop, we instead have a while loop nested within another while loop. Here is an example of Insertion Sort in action: Repeat step 2 until the current element is greater than the previous element.If the current element is less than the previous element swap them.Compare the current element with the previous element.Starting from the second element of the list, The final simple sorting algorithm is insertion sort which works as follows: Here is an example of Selection Sort in action: Move to the next index and repeat from step 1.Swap it with the current index (front of the unsorted list).Therefore, denoting the worst case runtime as T(n), we can see thatĪnother simple sorting algorithm is selection sort which works as follows:
Using Big O notation, simply letting each pass use n-1 comparisons and we make a total of n passes. We can see that in the worst case (when the list starts in reverse order), on a given input of size n, there will need to be n-1 comparisons to sort the first element, n-2 comparisons to sort the next element and so on until the last unordered element which will need 1 comparison.
Looking at the algorithm, with each pass (steps 1 to 4) the largest unordered element will have been sorted to the end of the list.
#Selection sort vs bubble sort graph code#
We could predict the complexity of this code to be O(n^2) as we have one loop nested in another (the for loop nested in the while loop) with both of these iterating based off of a variable which is dependent on n.
0 kommentar(er)
