Skip to main content

Selection Sort Explained

Introduction

If you are trying to get a remote job in a top IT consulting company, you will definitely fall into a live code exercise where your algorithms, logical thinking and problem solving skills will be tested and you will have to demonstrate a solid knowledge of these concepts.

Today I decided to write about a type of sorting algorithm that I found several times in interviews and decided, after studying the approach used, to create an initial solution in the simplest possible way.

Understanding the logic

As we know, the sort algorithm basically uses three basic principles to sort the items in a list. A comparator, a swap function, and recursion. For this selection sort algorithm I will focus in the first two.

Given that we have the following list of numbers: 64, 25, 12, 22, 11, how would we use selection sort to swap and sort the list in an ascending order?

The following code from the init function uses two for loops to create a temporary list (line 2) with the remaining values of the original list, which will be shorter in each new loop.

for (int j = 0; j < list.size(); j++) {
List<Integer> tmpList = new ArrayList<>();
for (int k = j; k < list.size(); k++) {
tmpList.add(list.get(k));
}
int min = Collections.min(tmpList);
int pos = list.indexOf(min);
if(!list.get(j).equals(list.get(pos))) {
swap(pos, j);
}
}
view raw gistfile1.txt hosted with ❤ by GitHub

For each temporary list created we determine what is the minimum value for each new list (line 6) and get its position in the original list (line 7) so that we can change or order it. Basically, we have the follwing four steps.

1. Get the minimum value from the list
2. Get the position of the value in the list
3. Check if the item is not ordered
4. Swap/sort the item in the original list

With the first item of the list sorted, we skip it and create a new temporary list with the remaining values to obtain the next minimum value of the list to be swaped, repeating the steps from 1 to 4 until the end of the list. and in case the item is not in the sorted position we apply the logic of the swap function so that we can sort it by placing it in the next position of the original list.

The swap function will get the value of the current index in the list (line 2) and swap it with the value that is in the position of the next minimum value (line 3 and 4).

private static void swap(int pos, int i) {
int swap = list.get(i);
list.set(i,list.get(pos));
list.set(pos, swap);
System.out.println(list);
}
view raw gistfile1.txt hosted with ❤ by GitHub

Full Code

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
public class SelectionSort {
private static List<Integer> list = Arrays.asList(64, 25, 12, 22, 11);
public static void init() {
showHeader();
for (int j = 0; j < list.size(); j++) {
List<Integer> tmpList = new ArrayList<>();
for (int k = j; k < list.size(); k++) {
tmpList.add(list.get(k));
}
int min = Collections.min(tmpList);
int pos = list.indexOf(min);
if(!list.get(j).equals(list.get(pos))) {
swap(pos, j);
}
}
}
private static void swap(int pos, int i) {
int swap = list.get(i);
list.set(i,list.get(pos));
list.set(pos, swap);
System.out.println(list);
}
private static void showHeader() {
System.out.println("Initial Array");
System.out.println("--------------------");
System.out.println(list);
System.out.println("--------------------");
}
}
view raw gistfile1.txt hosted with ❤ by GitHub

Code Execution

Conclusion

If you are studying for a remote position it is a good idea to take the time to delve into algorithms, data structures and design patterns.

Github

GitHub Repo

References

Learning Algorithms
Algorithms in a Nutshell
Design Patterns

Comments

Post a Comment

Popular posts from this blog

How to run OPA in Docker

From the introduction of the openpolicyagent.org site: OPA generates policy decisions by evaluating the query input against policies and data. In this post i am going to show you an easy and fast way to test your policies by running OPA in Docker. First, make sure you have already installed Docker and have it running: docker ps Inside your choosen directory, create two files. One called input.json file for your system representation and one file called example.rego for your rego policy rules. Add the following content to your json file: Add the following content for the example.rego: Each violation block represents the rule that you want to validate your system against. The first violation block checks if any of the system servers have the http protocol in it. If that is the case, the server id is added to the array. In the same way, the second violation block checks for the servers that have the telnet protocol in it and if it finds a match the server id is also...
Post a Comment
Read more

How to use Splunk SPL commands to write better queries - Part I

Introduction As a software engineer, we are quite used to deal with logs in our daily lives, but in addition to ensuring that the necessary logs are being sent by the application itself or through a service mesh, we often have to go a little further and interact with some log tool to extract more meaningful data. This post is inspired by a problem I had to solve for a client who uses Splunk as their main data analysis tool and this is the first in a series of articles where we will delve deeper and learn how to use different Splunk commands. Running Splunk with Docker To run Splunk with docker, just run the following command: docker run -d —rm -p 8000:8000 -e SPLUNK_START_ARGS=--accept-license -e SPLUNK_PASSWORD=SOME_PASSWORD --name splunk splunk/splunk:latest Sample Data We are going to use the sample data provided by Splunk. You can find more information and download the zip file from their web site . How does it work? In order to be able to interact with Splunk t...
Post a Comment
Read more

How to create a REST API Pagination in Spring Boot with Spring HATEOAS using MongoDB

Introduction In this post we are going to see how we can create a REST API pagination in Spring Boot with Spring HATEOAS and Spring Data MongoDB . For basic queries, we can interact with MongoDB using the MongoRepository interface which is what we are going to use in this tutorial. For more advanced operations like update and aggregations we can use the MongoTemplate class. With Spring applications we start adding the needed dependencies to our pom file if using Maven as our build tool. For this project we are going to use the following dependencies: Spring Web , Spring Data MongoDB and Spring HATEOAS . To quickly create your Spring Boot project with all your dependencies you can go to the Spring Initializr web page. This is how your project should look like: As with any MVC application like Spring there are some minimal layers that we need to create in our application in order to make it accessible like the Controller , Service , Model and Repository layers . For this...
Post a Comment
Read more