Understanding Bubble Sort Algorithm - COEN 352 by Tawfiq Jawhar
Dive into the world of sorting algorithms with a focus on Bubble Sort. Explore how Bubble Sort works through animations, visual representations, and explanations of its time complexity, stability, and in-place nature. Discover the significance of one iteration in Bubble Sort and how it affects the arrangement of elements in an array. Get insights into optimizing Bubble Sort for best-case scenarios and understanding when the algorithm achieves its optimal time complexity.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Sorting Algorithms COEN 352 TAWFIQ JAWHAR
Bubble Sort Animation: https://youtu.be/nmhjrI-aW5o
What would the following array looks like after one iteration of bubble sort? Array = [12, 3, 5, 1, 20, 0]
What would the following array looks like after one iteration of bubble sort? Array = [12, 3, 5, 1, 20, 0] [3, 5, 1, 12, 0, 20] Biggest value will be at the end
What is the best time complexity of bubble sort and when does it happen?
What is the best time complexity of bubble sort and when does it happen? Best time complexity O(N) if we optimize it otherwise it s O(N2) because it will have to go till the end. In the optimized version: It happens when the array is already sorted. We can keep track of whether any element was swapped during the iteration and we can stop the iterations if there s no swaps. Which means we only go through the numbers once Note there's a difference between upper and lower bounds and worst and best cases. The growth rate applies to the change in cost as a change in input size occurs.
Is bubble sort stable? A sorting algorithm is said to be stable if two objects with equal keys appear in the same order in sorted output as they appear in the input array to be sorted. Bubble sort is stable If two elements are equal they will not be swapped and they will stay in the same order they were in before sorting. (unless you implemented otherwise)
Is bubble sort in place? in-place algorithm is an algorithm which transforms input using no auxiliary data structure. However a small amount of extra storage space is allowed for auxiliary variables.
Selection Sort Animation: https://youtu.be/xWBP4lzkoyM What is worst case? Best case? Can we optimize it like we did with bubble sort for best case? Less swaps than Bubble sort. Still bad.
Can we do better? Yes, yes we can! If we can divide the problem into smaller and simpler problems then use those solutions to reach a solution to the main problem Divide and conquer
Quick Sort Animation with implementation: https://youtu.be/SLauY6PpjW4 What controls whether this algorithm in the best case or worst case? What would you do to lower the chance of having a worst case quick sort?
Out of all the algorithms we have seen so far (including insertion sort), which one is the best??
Data Structure and Algorithms 101 IT DEPENDS. ALWAYS.
Banks often record transactions on an account in order of the times of the transactions, but many people like to receive their bank statements with checks listed in order by check number. People usually write checks in order by check number, and merchants usually cash them with reasonable dispatch. The problem of converting time-of-transaction ordering to check-number ordering is therefore the problem of sorting almost-sorted input. The number of checks to be sorted is less than 50. What sorting algorithm would you use? Question from: Introduction to Algorithms Hardcover by Thomas H. Cormen (Author), Charles E. Leiserson (Author), Ronald L. Rivest (Author), Clifford Stein (Author)
