5 Sorting Algorithms Every Software Engineer Should Know
Welcome to Geek Talk Advanced, where we break down techie stuff without the tech jargon.
As a software engineer and student of computer science, I’ve realized that to be a top-notch software engineer, you’ve got to understand the ABCs of algorithms. Today, we’re going to talk about sorting algorithms — the unsung heroes that make our coding lives easier.
Picture this: you’re dealing with loads of data, but it’s all jumbled up like a messy room. That’s where sorting algorithms come in. They’re like the neat freaks of the coding world, putting everything in order so we can find what we need without tearing our hair out.
In this article, we’ll dive into five simple yet powerful sorting algorithms which will enhance your applications.
Note: In this article we won’t talk about Big-Oh and Space/Time Complexity.
Sorting Algorithms in a Nutshell
Sorting algorithms are like your tech assistants, helping you arrange a messy pile of data in a systematic order. Imagine you have a list of numbers, and you want them in ascending order. That’s where sorting algorithms step in.
public class Sort {
public static void main(String[] args) {
int[] numbers = {5, 2, 8, 1, 6};
int[] sortedNumbers = sort(numbers); // some magic sorting algorithm
// Now, 'numbers' array is sorted
for (int number : sortedNumbers) {
System.out.print(number + " ");
}
}
}Bubble Sort
Alright, let’s break down Bubble Sort — a simple yet fundamental sorting algorithm.
Imagine you have a bunch of numbers in a list, and you want to arrange them in order. Bubble Sort does it like this:
- It goes through the list multiple times
- Comparing pairs of numbers one by one
- If a pair is in the wrong order, it swaps them
It keeps doing this until the entire list is sorted. Now, let me show you a piece of code:
public class BubbleSort {
public static void main(String[] args) {
int[] numbers = {5, 2, 8, 1, 6};
sort(numbers);
// Now, 'numbers' array is sorted
for (int number : numbers) {
System.out.print(number + " "); // 1 2 5 6 8
}
}
public static void sort(final int[] numbers) {
for (int i = 0; i < numbers.length - 1; i++) {
for (int j = 0; j < numbers.length - i - 1; j++) {
if (numbers[j] > numbers[j + 1]) {
// Swap numbers[j] and numbers[j+1]
int temp = numbers[j];
numbers[j] = numbers[j + 1];
numbers[j + 1] = temp;
}
}
}
}
}It iterates through the numbers, compares adjacent ones, and swaps them if they’re out of order. It’s like telling your computer to arrange your messy list — a bit slow for large lists but a great way to grasp the basics of sorting algorithms.
Selection Sort
Let’s delve into the world of Selection Sort, a straightforward way of sorting a bunch of numbers.
Imagine you have a list, and you want to find the smallest number and put it at the beginning. Selection Sort does just that — it repeatedly scans through the list, finds the smallest number, and places it in the sorted section.
It then moves to the next unsorted part and repeats the process until the entire list is sorted. Here’s a simple Java code snippet that shows how this works:
public class SelectionSort {
/**
* Returns the index of the smallest item in the array.
* */
public static int findSmallest(final Collection<Integer> array) {
ArrayList<Integer> arrayList = new ArrayList<>(array);
int smallest = arrayList.get(0);
int smallest_index = 0;
for(int i = 0; i < array.size(); i++) {
if(arrayList.get(i) < smallest) {
smallest = arrayList.get(i);
smallest_index = i;
}
}
return smallest_index;
}
/**
* Returns a new array which is sorted in ascending order.
* */
public static Collection<Integer> sort(final Collection<Integer> array) {
ArrayList<Integer> oldArray = new ArrayList<>(array);
Collection<Integer> newArray = new ArrayList<>(array.size());
for(int i = 0; i < array.size(); i++) {
int smallest = findSmallest(oldArray);
newArray.add(oldArray.get(smallest));
oldArray.remove(smallest);
}
return newArray;
}
}It goes through the list, finds the smallest number, and puts it in the right spot. The process repeats until the entire list is neatly sorted (n-times = length of list), making it an easy-to-understand method for organizing items.
Insertion Sort
Let’s unravel Insertion Sort.
Picture it like sorting a deck of cards in your hands — you pick a card, find its spot, and insert it there. Insertion Sort does something similar with numbers in a list.
Here’s a simple Java code snippet that shows how it works:
public class InsertionSort {
public static void main(String[] args) {
int[] numbers = {5, 2, 8, 1, 6};
int n = numbers.length;
for (int i = 1; i < n; ++i) {
int key = numbers[i];
int j = i - 1;
while (j >= 0 && numbers[j] > key) {
numbers[j + 1] = numbers[j];
j = j - 1;
}
numbers[j + 1] = key;
}
// Now, 'numbers' array is sorted
for (int number : numbers) {
System.out.print(number + " ");
}
}
}This simple Java code reflects how Insertion Sort operates.
- It goes through each number
- Finds its rightful place in the sorted part of the list
- And inserts it there.
It repeats this process until the entire list is neatly organized. It’s like arranging your numbers as if you were dealing cards, making it a straightforward way to grasp the concept of sorting algorithms.
Quick Sort
Let’s explore the Quick Sort algorithm, a clever way to sort numbers that might sound complex but is surprisingly simple.
Imagine you have a bunch of numbers, and you want to organize them in order. Quick Sort does it like this: it picks a “pivot” number from the list and rearranges the other numbers, putting smaller ones on the left and larger ones on the right.
This process repeats for the smaller and larger sections until the entire list is sorted. Here’s a straightforward Java code snippet that demonstrates how Quick Sort works:
public class QuickSort {
/**
* Returns a new array which is sorted in ascending order.
* */
public static Collection<Integer> sort(final Collection<Integer> array) {
ArrayList<Integer> list = new ArrayList<>(array);
if (list.size() < 2) {
return list;
} else {
Integer pivot = list.getFirst();
List<Integer> less = list.stream().skip(1).filter(element -> element <= pivot).toList();
List<Integer> greater = list.stream().skip(1).filter(element -> element > pivot).toList();
return Stream.of(
sort(less).stream(),
Stream.of(pivot),
sort(greater).stream()).flatMap(Function.identity()).collect(Collectors.toList());
}
}
}This code embodies the simplicity of Quick Sort. It selects a pivot, rearranges the numbers around it, and repeats until the entire list is sorted. Despite sounding intricate, Quick Sort’s logic is quite straightforward, making it a powerful tool for sorting in the coding world.
Merge Sort
Alright, let’s get to the last but not least one — Merge Sort.
Merge Sort is like a calm organizer; it breaks down the list into smaller bits, sorts them individually, and then cleverly merges them back together in the right order. Check out this simple code to see how it works:
public class MergeSort {
public static void main(String[] args) {
int[] numbers = {5, 2, 8, 1, 6};
mergeSort(numbers, 0, numbers.length - 1);
// Now, 'numbers' array is sorted
for (int number : numbers) {
System.out.print(number + " ");
}
}
public static void mergeSort(int[] arr, int left, int right) {
if (left < right) {
int middle = left + (right - left) / 2;
mergeSort(arr, left, middle);
mergeSort(arr, middle + 1, right);
merge(arr, left, middle, right);
}
}
public static void merge(int[] arr, int left, int middle, int right) {
int n1 = middle - left + 1;
int n2 = right - middle;
int[] leftArr = new int[n1];
int[] rightArr = new int[n2];
for (int i = 0; i < n1; ++i) {
leftArr[i] = arr[left + i];
}
for (int j = 0; j < n2; ++j) {
rightArr[j] = arr[middle + 1 + j];
}
int i = 0, j = 0;
int k = left;
while (i < n1 && j < n2) {
if (leftArr[i] <= rightArr[j]) {
arr[k] = leftArr[i];
i++;
} else {
arr[k] = rightArr[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = leftArr[i];
i++;
k++;
}
while (j < n2) {
arr[k] = rightArr[j];
j++;
k++;
}
}
}It’s like dealing with a big problem by breaking it into smaller, more manageable pieces. In this case, the list gets split, each part gets sorted, and then everything gets neatly merged back together. It might seem like a few more steps, but it’s a clever way to organize your numbers systematically.
Fin
In the vast world of coding, working with data is like trying to find your favorite book in a library without any order.
It’s chaos. But fear not, because the sorting algorithms we explored — Bubble Sort, Selection Sort, Insertion Sort, Quick Sort, and Merge Sort — are like your trusty assistants, helping you tidy up that digital mess. These algorithms might seem like a bunch of steps, but they all share a common goal: making your data more organized.
Whether it’s the simplicity of Bubble and Selection Sort or the strategic moves of Insertion, Quick, and Merge Sort, each method is like a tool in your coding toolkit.
Now, armed with this essential knowledge, you’ve got the power to arrange your data in different ways, making your coding journey a bit smoother and your applications a bit more efficient. So, embrace these sorting superheroes — they’re here to help you level up your coding game!
