Join Raghavendra Dixit for an in-depth discussion in this video Counting sort, part of Introduction to Data Structures & Algorithms in Java.
- [Instructor] We have seen that for a general array…in which the data is in a completely random order,…and there are no bounds on the data,…the best algorithm that can be retained…will have a time complexity of the order of n log n,…and merge sort is a pure n log n algorithm,…while quicksort, on an average,…has a worst-case time of the order of n log n, all right?…But can we do better than that,…especially if we have some more information about the data?…What if we know that however large the array itself is,…each element can have a value between zero and 10,…let's say?…Well, it turns out that if we have…some kind of more information about the data,…we can sort it in linear time,…so in this chapter we will learn about counting sort,…radix sort,…and the bucket sort algorithms,…which are all linear-time algorithms,…that is, they take time…which is proportional to the data size.…
So let's start with counting sort.…This is a very simple algorithm,…and is effective if the data…is within some reasonable range.…For example, if we know that the numbers in the array…
Note: This course was created by Packt Publishing. We are pleased to host this training in our library.
- Why study data structures and algorithms?
- How to calculate the time complexity
- Using Big O notation
- Using basic sorting and search algorithms
- Searching elements in unordered arrays and ordered arrays
- Implementing a linked list in Java
- Implementing stacks using arrays
- Queues using arrays
- Binary search trees
- Representing heaps using arrays
Skill Level Intermediate
1. Introduction to Algorithms
2. Analysis of Algorithms
3. Basic Sorting and Search Algorithms
4. Linked Lists
5. Stacks and Queues
7. Binary Search Trees
8. More Sorting Algorithms
- Mark as unwatched
- Mark all as unwatched
Are you sure you want to mark all the videos in this course as unwatched?
This will not affect your course history, your reports, or your certificates of completion for this course.Cancel
Take notes with your new membership!
Type in the entry box, then click Enter to save your note.
1:30Press on any video thumbnail to jump immediately to the timecode shown.
Notes are saved with you account but can also be exported as plain text, MS Word, PDF, Google Doc, or Evernote.