2017-08-30 17:44:31

Sorting Algorithms using Java & C: Make Your Basics Strong

164 students enrolled

Please confirm that you want to add **Sorting Algorithms using Java & C: Make Your Basics Strong** to your Wishlist.

Comprehensive course to understand, analyse and implement different comparison based sorting algorithms using Java & C

New

164 students enrolled

What Will I Learn?

- How to analyse an algorithm, understanding of worst case, best case and average case complexities, how to estimate them for any algorithm. Seven (7) most important comparison based sorting algorithms, Bubble Sort, Selection Sort, Insertion Sort, Shell Sort, Quick Sort, Merge Sort and Heap Sort. Students will get to know details of heap data structures along with heap operations along with heap sort. They will also get to know how to analyse these algorithms and how to find the worst and best case complexities for each of them.

Requirements

- Students must be familiar with basic understanding of C or Java. If you are familiar with any other language then also you can join the course, however, the implementations of the sorting algorithms in this course is done in both C and Java only.

Description

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.

Who is the target audience?

- "Sorting algorithms" are gateway to the world of understanding algorithms, any programming aspirant who wants to make the fundamentals more concrete. The fact is, in Job interviews of many questions are asked from this section.

Compare to Other Java Algorithms Courses

Curriculum For This Course

59 Lectures

06:35:45
+
–

Introduction
1 Lecture
03:40

Introduction to the course.

Preview
03:40

+
–

Efficiency of algorithm
8 Lectures
49:56

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.

Preview
05:32

This quiz is based on the first lecture of the section - 2.

Quiz on Efficiency of algorithm

5 questions

Understand how we can approach mathematically to estimate for the efficiency of algorithm.

Preview
03:21

This quiz depends on the second lecture of section 2.

Quiz on Mathematical Approach

1 question

How to find the execution time for any algorithm, the definition of worst case complexity, Big-Oh notation.

How to estimate for efficiency - Big-Oh notation.

05:39

You must view the 3rd lecture in section 2 to be able to answer these questions.

Quiz on How to estimate efficiency - Big Oh notation

2 questions

Learn how we can calculate the Big-Oh for an algorithm.

Calculating Big-Oh

07:06

Please view the 5th lecture of section - 2 before attempting this quiz.

Calculating Big - Oh

5 questions

Calculate Big-Oh of some more algorithms.

Calculating Big-Oh continue...

08:40

Some more examples on calculating Big-Oh.

Calculating Big-Oh more examples

06:36

You must have completed lectures 5, 6 and 7 to attempt this quiz.

More Quiz on Big Oh

4 questions

Understand best case complexity of an algorithm, the Big Omega notation.

Best case complexity

07:51

Quiz on Best case complexity.

3 questions

Understand average case complexity and Big Theta notation.

Average case complexity

05:11

+
–

Bubble Sort
10 Lectures
01:03:23

Understand the logic of bubble sort clearly, step-by-step with visual description.

Bubble sort logic.

13:54

Understand how to analyse bubble sort for worst case behaviour.

Analysis of bubble sort - Worst case complexity

04:23

Understand how we can improve the bubble sort algorithm for best case behaviour when input is a sorted list.

Improve bubble sort algorithm for best case

07:04

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.

Implementation of bubble sort using C - Part 1, Understand the helper functions

03:06

Writing the function for bubble sort.

Implementation of bubble sort using C - Part 2 Writing the function.

07:08

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.

Implementation of bubble sort using C - Part 3 Testing

06:57

Check how bubble sort program behaves if you supply a sorted array as input.

Implementation of bubble sort using C - Part 4, how it behaves on sorted input.

02:35

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.

Implementation of bubble sort using Java - Part 1

10:10

Executing the program with various input sizes and plotting the n vs f(n) graph. The code is attached with the previous lecture.

Implementation of bubble sort using Java - Part 2

05:55

How bubble sort works with sorted input. Download the code attached.

Implementation of bubble sort using Java - Part 3

02:11

Quiz on Bubble Sort

4 questions

Do the bubble sort by moving the smallest number to the top of the sub array.

Bubble Sort Assignment No - 1 using C or Java

1 question

Move the largest number at the bottom and smallest number at the top within the same iteration of the outer loop.

Assignment 2 - Implement 2 way Bubble Sort using Java or C

1 question

+
–

Selection Sort
4 Lectures
25:52

Introduction to selection sort, understand clearly how the selection sort logic works, then understand the algorithm.

Understand Selection Sort logic and develop the algorithm

09:50

Test your understanding of Selection Sort

Selection Sort Dry Run

2 questions

Analysis of selection sort for best case and worst case time complexity. Also, deciding about space complexity.

Analysis of selection sort

04:00

Quiz on selection sort

4 questions

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 using C

04:54

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).

Implementation of selection sort using Java

07:08

In this assignment instead of selecting the minimum number and placing that at the top of the sorted section, you will actually find the maximum number from the unsorted section and will need to place at the bottom of the sorted section.

Perform selection sort by selecting maximum number

2 questions

+
–

Insertion Sort
5 Lectures
26:14

Introduction to insertion sort, then understand the logic of insertion sort, understand the algorithm.

Introduction to insertion sort, understanding the logic using visual description

11:50

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.

Insertion sort on sorted array as input

02:17

Analysis of insertion sort for the worst case, understand how the insertion sort is O(n^2)

Worst case behaviour of insertion sort.

04:35

Test your knowledge on Insertion Sort with this Quiz.

Quiz on Insertion Sort

5 questions

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 C

03:40

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).

Implementation of insertion sort using Java

03:52

+
–

Shell Sort
4 Lectures
29:12

Introduction to Shell Sort, then understand the logic of Shell Sort with visual description.

Introduction to Shell Sort, understand the logic with visual description.

10:21

Algorithm of Shell Sort

04:14

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**.

Implementation of Shell Sort using C

07:34

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.

Implementation of Shell Sort using Java

07:03

+
–

Quick Sort
9 Lectures
01:05:54

Brief introduction to quick sort.

Quick Sort introduction.

01:54

Clearly understand the quick sort procedure with comprehensive visual description.

Quick sort procedure with visual description.

08:29

I will explain the partition logic using example array with visual description.

Partition logic. Understand clearly how partition logic works

07:14

Understand the partition logic algorithm more clearly in this lecture as I will dry run the algorithm step-by-step with example input.

Dry run of Partition logic algorithm.

10:27

Understand how we can analyse quick sort for it's average behaviour.

Analysis of quick sort - average case execution time.

12:07

Analysis of quick sort - worst case, when the input is sorted.

05:56

Understand how to estimate the space complexity of quick sort.

Analysis of quick sort - space complexity

03:01

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.**

Implementation of Quick sort using C

08:40

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.**

Implementation of Quick sort using Java

08:06

+
–

Merge Sort
6 Lectures
40:47

Brief introduction to merge sort.

Introduction to Merge Sort

01:22

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.

Merge logic - How to merge two sorted halves of same array into one sorted array

09:00

Understand clearly step-by-step with the visual description that how merge sort works.

Merge sort procedure

06:40

Details analysis of merge sort to find the worst case complexity and space complexity.

Analysis of merge sort.

10:18

Watch and experience merge sort implementation and execution using C. **You can download attached code**.

Implementation of merge sort using C

06:12

Watch and implement merge sort implementation and execution in Java. **You can download the code as attached**.

Implementation of merge sort using Java

07:15

+
–

Heap data structure and Heap sort
12 Lectures
01:30:47

Brief introduction to heap data structure and heap sort.

Introduction to heap sort.

02:05

You must have basic understanding of binary tree to understand heap, so here in this lecture I have briefly explained binary tree data structure.

Brief idea of Binary Tree

05:02

Understand almost complete binary tree, a special type of binary tree.

Almost complete binary tree.

02:02

How to representation of almost complete binary tree using 1 dimensional array.

06:03

Understand heap data structure clearly.

Definition of Heap.

04:17

Understand clearly how we can insert an element in heap with visual description.

How to insert into heap.

11:12

Understand how we delete an element from heap.

How to delete from heap.

09:14

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.

Heap adjust.

07:42

This method is really awesome, it builds a heap from any arbitrary array using the heap adjust operation.

Heapify - build a heap from any arbitrary array.

08:52

Understand the heap sort.

Heap sort - understand how we can sort an array using a heap.

06:30

Watch how we can implement heap sort using C, **you can download the code attached with this lecture**.

Implementation of heap sort using C

15:50

Understand how we can implement heap sort using Java. You can download the code attached with this lecture.

Implementation of heap sort using Java

11:58

About the Instructor