With bubble sort, we are always comparing EVERY pair in the unsorted sublist with each pass, so that's n-m comparisons (twice as many as insertion sort on random data). With random data, you can expect to make m/2 comparisons and swaps, where m is the size of the sorted sublist. With insertion sort, we are only performing a linear search in the sorted sublist with each pass. However, insertion sort will perform fewer comparisons in general. Yes, after each pass, insertion sort and bubble sort intuitively seem the same - they both build a sorted sublist at the edge. I will try to give a more concise and informative answer than others. In insertion sort elements are bubbled into the sorted section, while in bubble sort the maximums are bubbled out of the unsorted section. Note that typical implementations terminate early if no swaps are made during one of the iterations of the outer loop (since that means the array is sorted). The 5 is bubbled out of the unsorted section In each iteration, sift through the unsorted section to find the maximum. In each iteration the next element is bubbled through the sorted section until it reaches the right spot: sorted | unsortedĪfter i iterations the last i elements are the biggest, and ordered. After i iterations the first i elements are ordered.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |