OpenCourser
Learn skills that shape your future
Visit OpenCourser.com
This course will help to understand seven most important comparison based sorting algorithms along with the details of how to estimate the complexities for any algorithm. Students will clearly understand how to estimate the best case, average case and worst case complexities for any algorithm along with details analysis of each of the sorting algorithm.
The seven sorting algorithms that you will learn in this course are as follows:
This course will help to understand seven most important comparison based sorting algorithms along with the details of how to estimate the complexities for any algorithm. Students will clearly understand how to estimate the best case, average case and worst case complexities for any algorithm along with details analysis of each of the sorting algorithm.
The seven sorting algorithms that you will learn in this course are as follows:
Bubble sort
Selection Sort
Insertion Sort
Shell Sort
Quick Sort
Merge Sort
Heap Sort
Students will learn details of heap data structures along with the heap operations like, insertion into heap, heap adjust, heap delete and heapify while learning the heap sort.
Although, sorting utilities can be found in the library of any modern day programming language, however, it is must for a programming student to understand them from scratch as this will help to form strong foundation on algorithm. Also, it is often found that, many questions are asked on sorting algorithms on Job interviews, hence, it will be really fruitful to have a strong hold on this topic.
In the course, I described the logic of each of the seven comparison based sorting algorithms using visual description that is really easy to understand, then I explained the algorithm, analysed them for their performance and finally implemented them using C and Java.
If you are interested of implementing them using in other language you can also do that following the lectures. It will be really easy to do.
Introduction to the course.
How we can decide about the efficiency or performance of algorithm, what are the yard sticks? How to compare two algorithms on their performance. Concept of RAM model.
This quiz is based on the first lecture of the section - 2.
Understand how we can approach mathematically to estimate for the efficiency of algorithm.
This quiz depends on the second lecture of section 2.
How to find the execution time for any algorithm, the definition of worst case complexity, Big-Oh notation.
You must view the 3rd lecture in section 2 to be able to answer these questions.
Learn how we can calculate the Big-Oh for an algorithm.
Please view the 5th lecture of section - 2 before attempting this quiz.
Calculate Big-Oh of some more algorithms.
Some more examples on calculating Big-Oh.
You must have completed lectures 5, 6 and 7 to attempt this quiz.
Understand best case complexity of an algorithm, the Big Omega notation.
Understand average case complexity and Big Theta notation.
Understand the logic of bubble sort clearly, step-by-step with visual description.
Understand how to analyse bubble sort for worst case behaviour.
Understand how we can improve the bubble sort algorithm for best case behaviour when input is a sorted list.
Starting the implementation of bubble sort using C. Understand all the function prototypes that we will need. You can download the entire code as attached.
Writing the function for bubble sort.
Testing the bubble sort with different randomly generated input list. I will note down the execution time on each of the execution and finally will use these data to plot the n vs f(n) curve.
Check how bubble sort program behaves if you supply a sorted array as input.
Implementing the bubble sort method in a class SortUtility along with some other helper methods which may be required for testing bubble sort. You can download the code attached with this lecture.
Executing the program with various input sizes and plotting the n vs f(n) graph. The code is attached with the previous lecture.
How bubble sort works with sorted input. Download the code attached.
Introduction to selection sort, understand clearly how the selection sort logic works, then understand the algorithm.
Analysis of selection sort for best case and worst case time complexity. Also, deciding about space complexity.
Implementation of selection sort using C programming. Testing the method using various input sizes and finally plotting the size of input vs execution time graph to inspect if the curve is indeed O(n^2).
Implementation of selection sort logic using Java, then testing the method using different input sizes and finally plotting the input size vs execution time graph to check if the curve is indeed O(n^2).
Introduction to insertion sort, then understand the logic of insertion sort, understand the algorithm.
The best case analysis of insertion sort, the best case behaviour happens when the input list is sorted. Understand how the best case time complexity of insertion sort is linear.
Analysis of insertion sort for the worst case, understand how the insertion sort is O(n^2)
Test your knowledge on Insertion Sort with this Quiz.
The C implementation and testing, code attached, I will run the program for various input sizes and will note down the execution time on each occasion and finally I will plot the input size vs execution time graph to check if indeed insertion sort is O(n^2).
Implementation of insertion sort using Java, code attached, executing the program for various input sizes and finally plotting the input size vs execution time graph to check if indeed insertion sort is O(n^2).
Introduction to Shell Sort, then understand the logic of Shell Sort with visual description.
See how we can implement Shell sort using C program, here I will implement shell sort using both default Shell gap and Sedgewick gap. You can download the code from the attached file.
Watch how we can implement Shell sort using Java (code is attached), I will implement Shell sort using both default Shell gap and also by using Sedgewick gap.
Brief introduction to quick sort.
Clearly understand the quick sort procedure with comprehensive visual description.
I will explain the partition logic using example array with visual description.
Understand the partition logic algorithm more clearly in this lecture as I will dry run the algorithm step-by-step with example input.
Understand how we can analyse quick sort for it's average behaviour.
Understand how to estimate the space complexity of quick sort.
See how we can implement and execute quick sort using C, also experience the how the graph - input size vs execution time looks like for different input sizes. You can download the code attached with this lecture.
See how we can implement and execute quick sort using Java. Also watch and experience the input size vs. execution time curve for different input sizes. You can download the code attached with this lecture.
Brief introduction to merge sort.
Understand the merge sort helper - the merge logic. How to merge two sorted halves of an array into one completely sorted array in-place using this merge logic, this will be used in merge sort.
Understand clearly step-by-step with the visual description that how merge sort works.
Details analysis of merge sort to find the worst case complexity and space complexity.
Watch and experience merge sort implementation and execution using C. You can download attached code.
Watch and implement merge sort implementation and execution in Java. You can download the code as attached.
Brief introduction to heap data structure and heap sort.
You must have basic understanding of binary tree to understand heap, so here in this lecture I have briefly explained binary tree data structure.
Understand almost complete binary tree, a special type of binary tree.
Understand heap data structure clearly.
Understand clearly how we can insert an element in heap with visual description.
Understand how we delete an element from heap.
Understand clearly how to adjust a particular index i of heap, when the left child of i is a heap and right child of i is also heap. This procedure is required to adjust the heap after delete operation and also from heapify operation to build a heap from any arbitrary array.
This method is really awesome, it builds a heap from any arbitrary array using the heap adjust operation.
Understand the heap sort.
Watch how we can implement heap sort using C, you can download the code attached with this lecture.
Understand how we can implement heap sort using Java. You can download the code attached with this lecture.
Save
Good preparation for technical interviews.
Implementations provided in Java and C.
Excellent for building algorithm basics.
Thorough coverage of Big O and performance.
Complex logic made easy with visuals.
OpenCourser helps millions of learners each year. People visit us to learn workspace skills, ace their exams, and nurture their curiosity.
Our extensive catalog contains over 50,000 courses and twice as many books. Browse by search, by topic, or even by career interests. We'll match you to the right resources quickly.
Find this site helpful? Tell a friend about us.
We're supported by our community of learners. When you purchase or subscribe to courses and programs or purchase books, we may earn a commission from our partners.
Your purchases help us maintain our catalog and keep our servers humming without ads.
Thank you for supporting OpenCourser.
