Understanding Sorting Algorithms in Data Structures & Algorithms
Explore common sorting algorithms like Insertion Sort, their implementation, efficiency, and comparison to make informed decisions. Practice Big-Oh notation and timing measurements for algorithm complexity analysis in a classroom setting.
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. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
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.
E N D
Presentation Transcript
CSCI 204: Data Structures & Algorithms Revised by Xiannong Meng based on textbook author s notes 1
Insertion Sort Another commonly studied algorithm. Arranges the items by iterating over the sequence one complete time. inserts each unsorted item into its proper place. 2
Insertion Sort Code def insertionSort( theSeq ): n = len( theSeq ) for i in range( 1, n ) : value = theSeq[i] pos = i while pos > 0 and value < theSeq[pos - 1] : theSeq[pos] = theSeq[pos - 1] pos -= 1 theSeq[pos] = value 3
Working With Sorted Lists The efficiency of some algorithms can be improved when working with sorted sequences. For non-static collections, it would be inefficient to re-sort a sequence for each add/remove. Better to maintain a sorted sequence. 6
Maintaining a Sorted List To maintain a sorted list, new items must be inserted into their proper position. Can not simply be appended at the end. Must locate the proper position and use insert(). 7
Compare Different Sorting Algorithms So far, we have studied three different sorting algorithms Bubble sort: in each round, bubble the smallest items to the top (or sink the largest item to the bottom) Selection sort: in each round, select the correct position for the current item Insertion sort: in each round, insert the current item in its correct location so the partial list is sorted
Complexity and Timing In the classroom activity, you will come up the big-Oh notation for each of the three algorithms You will also measure the timing of the three algorithms with data sets of different sizes
