Join Raghavendra Dixit for an in-depth discussion in this video Selection sort, part of Introduction to Data Structures & Algorithms in Java.
- [Instructor] There are three commonly used n-squared algorithms for sorting. You already know and should have implemented the bubble sort algorithm. In this chapter we will learn two more sorting algorithms which take n-squared time. The first one is the Selection Sort and the other is called Insertion Sort. So let us start by understanding what the selection sort algorithm is. Let's consider the cue balls in a bin again. We have an empty bin, which we can make use of, and again we can use a cue stick to keep track of item or items if we want to.
In the Selection Sort algorithm what we do is that we search for the smallest element and swap it with the item in the first bin, which is the leftmost bin. So the first element becomes sorted because that contains the ball with the smallest number. So this was hydration one. In the next hydration we do exactly the same thing with the remaining added. That is, starting from the second position, we search for the cue ball with the smallest number out of the remaining ones and when we find that we swap it with the ball in the second bin.
So now the ball with the next smallest number is in the second bin. So the first two bins are sorted. And we keep repeating this process until all the balls are sorted. So it is called the Selection Sort algorithm because every time we select the smallest number and then swap it with the item in the relevant bin.
So if we have an area of numbers we go through all the elements to find the minimum and then exchange it with the first area element. So that this is how the area looks like with the first element as sorted. Then from the remaining elements that is starting from the second area element we find the minimum and then exchange it with the second element of the area.
So now the first two elements are sorted. And we keep doing this until the whole area is sorted.
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.