[*Ten wpis będzie w całości po angielsku. Od czasu do czasu takie teksty będą się pojawiać. Robię tak z dwóch powodów – w Javie, tak jak w każdym języku programowania, trzeba przyswoić tony branżowej i językowej nomenklatury, która czasami (ba, nawet bardzo często) fatalnie przekłada się na język polski. Dobrze jest się więc „obywać” z angielskim, oryginalnym nazewnictwem. Druga sprawa to po prostu praktyka angielskiego. *

There is a time, when you have to take a hit with the wall of algorithms in Java. You can make it sooner or later, but eventually this time will come. So here i am – practicing the very basics of three different algorithms:

**– bubble sort**

**– selection sort
– quick sort**

And this text is nothing else but the quick evaluation of my experiences. Just before we start – there are literally thousands of explanations, tutorials, videos and texts all over the web how algorithms work. I wasted quite a lot of time going through a significant number of them – **don’t do this!** Yep, it is a waste of time in my opinion. The resource i found particulary good was an app called Algorithms:Explained and Animated. This app is simple and neatly designed! And thats all i need, really, in the very basic step of algorithm learning. Download it and play with it for some time – its great, even if you have 20 minutes in the tram or bus to work/school.

And one more thing, to clear the stage, we have to answer one more question…

## Why even learning when there is a sort method already in place?

Take a look at this magic power of Java 8:

1 2 3 4 5 6 7 |
{ salesmans .stream() .sorted((e1, e2) -> Integer.compare(e1.getSalesmansSalary(), e2.getSalesmansSalary())) .forEach(e -> System.out.println(e)); } |

Using streams and lambda in Java 8 i can within couple lines of code sort the salesmans in my shop by their salaries (or any other comparable measure). Easy? Definitely. But… do you get it? Do you understand what is happening behind? Mkhm…not really.

In the modern world of programming the new and shiny frameworks, libraries and tools popping out every month are pretty much the worst nightmare of the beginner programmer. You can spend hours and hours literally getting to know the new features, while your knowledge and experience stay basically in the same place. That’s why during the course in Software Developer Academy our mentor took different approach – **YOU HAVE TO KNOW WHAT IS HAPPENING BEHIND THE SCENE**. Have strong foundation before dipping in the other tools. In algorith

ms this idea means: we, experienced developers, know that in real life you will never have to write your own sorting method from the start to finish, because the vast libraries have them already in place. But, when you are learning, there is no better way to understand the logic than **simply writing the engine of the algorithm from the scratch**.

There is a reason why all the books explaining algorims and data structures are brick-solid, hundreds of pages worth of reading. Get a solid grip on this topic.

## Bubble sort – get them in couples, swap and repeat

Idea is simple. You have an unsorted, randomly putted integers in collection (let it be table for this purpose). Bubble sort takes two neighbours, compares them, swap them (if the second integer is bigger) and then goes to next integer, swap them, and until the set is sorted. Easy. By the way, take a look at this:

Nothing like romanian folk dance group performes hungarian folk dance in a goal to explain the bubble sorter. That’s something, ha? If this does not speak to you, than nothing else will 😉

Anyway, it is all about couples and swaping. Now try to put it in code. Hint: You need two for loopes and a temporary integer that is used for swapping.

Did you write it? If not, try this simple pseudocode:

1 2 3 4 5 6 |
func bubblesort( var a as array ) for i from 1 to N for j from 0 to N - 1 if a[j] > a[j + 1] swap( a[j], a[j + 1] ) end func |

Eventually the final code at its simplest form will look like this:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
int[] table1 = {1, 33, 4, 12, 2, 55, 77, 88, 99}; int temp = 0; boolean wasSwap = true; for (int i = 0; i < table1.length; i++) { wasSwap = false; for (int j = 1; j < (table1.length - i); j++) { if (table1[j - 1] > table1[j]) { temp = table1[j - 1]; table1[j - 1] = table1[j]; table1[j] = temp; wasSwap = true; } } if (!wasSwap) { break; } } for (int i = 0; i < table1.length; i++) { System.out.println("i = " + i + ", table1. sort[i]" + table1[i]); } |

Looks easy, right? Anyway i want you to remember that in fact **bubble sort algorithm basically… sucks**. It is not efficient. Especially not if we have another great options, like…selection sort.

## Selection sort – get one, find a smaller one and swap

Selection sort presents a bit smarter approach. Insted of iterating through the whole set like in the Bubble Sort, selection sort divides the input to two parts. The left one contains all sorted elements and the right one not sorted. What the algorithm is doing looks like this:

Let’s say we start with a table of integers: 44,2,21,13,5,6;

1 step: we took first position (44) and then algoritms should scan through the whole table and find that the 2 is the lowest number)

2 step: swap – 44 is swapping with 2. The table looks like this: 2,44,21,13,5,6;

3 step: the first step is repeated – 2 is a fixed position, so we took 44, than scan goes through others and find the next smallest one, which is 5

4 step: swap – 44 is swapping with 5; state of the table: 2,5,21,13,44,6;

5 step: You should notice now, that we have two parts here: the one on the left – 2,5 – that are already sorted and the rest. This is important. Algorithm is not going through the left set anymore. So now, the next fixed integer is 21, scanning with 6 and swapping.

Eventually we end up with the sorted table that looks like this: 2,5,6,13,21,44;

Try to do this on your own, before looking at the code below.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
public int[] selectionSorter(int[] tableOfInts) { for (int i = 0; i < tableOfInts.length - 1; i++) { int indexInt = i; for (int j = i + 1; j < tableOfInts.length; j++) { if (tableOfInts[i] < tableOfInts[indexInt]) { indexInt = j; } } int smallerIndex = tableOfInts[indexInt]; tableOfInts[indexInt] = tableOfInts[i]; tableOfInts[i] = smallerIndex; } for (int i = 0; i < tableOfInts.length; i++) { System.out.println("i = " + i + ", table1. sort[i]" + tableOfInts[i]); } return tableOfInts; } |

## Quick Sort – divide and conquer

While the previous examples of sorting were pretty simple this one requires a bit of imagination. Yep, imagination. Or maybe more precisely an imagination with visualizations skills. There are several steps on the way, but let’s just start with saying the Quick Sort is a **divide and conquer type of algorithm**. And it does… divide and conquer. Quick sort separetes an array into two sub-sets (or sub-parts) with smaller and larger values, and then it does it again on next level. We had array separated in two sub-sets, now we have four sub-sub-sets and it goes as deeper as it has to – depends how large is an array.

In order to separate an array to two sub-arrays, we need a pivot. And pivot is usually a median integer in the array. So it sits precisely in the middle.

Setting a pivot is a FIRST STEP.

1 2 3 4 5 |
int i = lowerIndex; int j = higherIndex; int pivot; pivot = table[lowerIndex + ((higherIndex - lowerIndex) / 2)]; |

So basically pivot sits in the middle. Easy. Next step.

Yep, but, wait a second, why we need a pivot? To separate the set to two sub sets. But before that we need to separate larger integers from the smaller integers. Smaller will stay on the left side of pivot, while the larger will be moved to the right one.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
while (i <= j) { while (table[i] < pivot) { i++; //while loop is going through the index of the integers in the table } //I loop is going to RIGHT, and Y is going LEFT while (table[j] > pivot) { j--; } //if checks if the two i and j have crossed, if not they swap if (i <= j) { exchangeNumbers(i, j); i++; j--; } } |

For the purpose of the quick sort i created a separete exchange numbers method.

1 2 3 4 5 |
private void exchangeNumbers(int i, int j) { int temp = table[i]; table[i] = table[j]; table[j] = temp; } |

Up until this point it looks easy right? We are just moving the integers around the pivot. And it is the **core of the quicksort**. However one pivot and one separation is usually not enough. So what we need right now? **The RECURSION**.

### Few sentences about recursion

In order to understand recursion, you need to understand recursion – this quote never gets old. And it sums up pretty neatly what the recusion really is. It is a method that calls itself. Let’s step outside of the computer science for the second. Did you ever try to capture an image your display while in the same time streaming on the display from your camera? Even if you didn’t you have probably seen this kind of image many times:

In fact it is recursion. The picture is endlessly repeating itself. In programming recursion is an **immensly poweful tool**. But it requires a cautious approach – stackoverflow is very much likely on many ocassions.

Back to our quicksort. So what we need right here is use recursion in order to get deeper and deeper.

1 2 3 4 5 6 |
if (lowerIndex < j) { quickSort(lowerIndex, j); } if (i < higherIndex) { quickSort(i, higherIndex); } |

It is very important when you are calling the the same methods within the methods to set the limitations for them. In our quicksort example im calling the recursion only within two conditions. Thats all.

And thats how it should looke like at the end:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 |
public void quickSort(int lowerIndex, int higherIndex) { int i = lowerIndex; int j = higherIndex; //setting the pivot in MIDDLE OF THE TABLE, important! int pivot; pivot = table[lowerIndex + ((higherIndex - lowerIndex) / 2)]; //while loops within the while loops //idea is that each index in the table is compared to the pivotal value (set above), and then (in the if operator) //it executes the exchange numbers method, that takes two integers and swap them while (i <= j) { while (table[i] < pivot) { i++; //while loop is going through the index of the integers in the table } //I loop is going to RIGHT, and Y is going LEFT while (table[j] > pivot) { j--; } //if checks if the two i and j have crossed, if not they swap if (i <= j) { exchangeNumbers(i, j); i++; j--; } } //this is where the magic RECURSION happens - method calls themselve, by te smaller index if (lowerIndex < j) { quickSort(lowerIndex, j); } if (i < higherIndex) { quickSort(i, higherIndex); } } private void exchangeNumbers(int i, int j) { int temp = table[i]; table[i] = table[j]; table[j] = temp; } public void sortTheTableFinalMethod(int[] inputTable) { if (inputTable == null || inputTable.length == 0) { return; } this.table = inputTable; length = inputTable.length; //here we have an y - higher index is set to the highest index (and while the index is always counted from 0, we have //to make it -1 quickSort(0, length - 1); } |

The final method – sortTheTableFinalMethod (sorry for the long name but i really need to write it the way i understand it) collects all the pieces together. Then you just go to the main and launch it.

## Complexity and why it is very important

While some people may tell you that math skills are irrelevant when learning to code, i stand on the position that at least strong basics needs to be covered. And here is why.

On your learning path you will probably learn at least 8 most popular sorting algorithms. However sorting is just a small branch in the world of algorithms. Important, but really small. At some moment in your career, probably later than sooner, choosing and implementing certain algorithm in your project will be very important decision. So in order to choose wisely, you need to obtain a bit of theory behind algorithms.

**Computational complexity** is what basically defines the efficiency of algorithms. In computer science we use time complexity and space complexity. That makes sense, right? We want to use the algorithm that is quick (in terms of time complexity) and doesn’t need a whole lot of memory (space complexity). So lets take a look at sorting methods i described above:

Bubble Sort – ouch, the ugly one. In worst case scenario complexity of Bubble Sort is O(n^2), when n is a number of integers to sort.

Selecion Sort – a bit better, but in the worst case scenario quick sort has O(n^2) time complexity

Quick Sort – most efficient one – O(n log n) – logarythmic complexity.

However, this is not that easy. While picking for the right one simple complexity is not enough. It requires a careful delibaration on what kind of data collection we are aim to sort, and many other variables.

## Few final words

**Write the code!**

Did you mange to write every single algorithm? So now lets try on different collections. Try to sort an objects using their parameters (like for example age in the person object or time for running event). Than think about making algorithm more efficient – there are many ways to make it easier and faster. Think about it.

And remember – at the end of the day, **written code is all that matters!** 😉

Other resources worth exploring:

Sorting out the basics behind sorting algorithms basically explains the algorithms through and out. An author of this text – Vaidehi Joshi – was a huge inspiration for me. She did what im doing right now – took the coding course and through hard work and dedication made it to the IT. I strongly recommend all her articles published at dev.to

Tutorials Point – Data Structures and Algoritms – well, tutorials point never dissapoints. Well explained, well written.

Polish book that is a Bible for algoritms and data collections

## Dodaj komentarz