Sorting Algorithms -Part 1
Hi I’m Lahiru Abegunawardena. This is my new article series on Sorting Algorithms. First we will see what is an Algorithm.
Algorithms
Simply an algorithm is a sequence of instructions to solve a problem or perform a computation. This can be written as pseudocode, line by line instructions, even you can use flowchart diagram.
Sorting Algorithm
A Sorting Algorithm is used to rearrange a given array or list of elements according to a certain order. In this article series we will discuss about sorting a list of numbers according to ascending or descending order. Sorting algorithms are divided into two main sections as “Comparison sort” and “Integer sort”.
Comparison Sort
Comparison sorts compare elements compare at each step of the algorithm to determine if one element should be to the left or right of another element.
Integer Sort
Integer sort is also called as counting sort. We will try to understand process of this sorting technique with following example.
Let’s think there is a list of 10 items. If item “x” is higher than 4 of other elements then x is placed on 5th position in the list. So we can continue the process until the list is sorted.
In this article series we will discuss about few types of sorting algorithms, their characteristics and there implementation or simplified algorithm level explanation.
Bubble Sort
Bubble sort is a simple comparison sorting algorithm. This will compare each pair of element in the list and exchange them if they are not in order. Let’s take a simple example on bubble sort and we will continue the discussion.
Unsorted array → 8, 5, 9, 3 need to sort in ascending order
8,5,9,3 → compare 8,5 (8>5) exchange 8&5.
5,8,9,3 → compare 8,9 (9>8)
5,8,9,3 → compare 3,9 (9>8)
5,8,3,9
This is only the first round that includes 4 steps. If you continue the process correctly you will see that this requires maximum 4 rounds to sort list in ascending order. That means 16 steps(4x4).
So if you have n element list you will need n² steps to complete the sorting. This is how complexity of Bubble sort is calculated as O(n²).
Now we will see how we can implement bubble sort using Java language.
Now we will discuss what I did in this code. Specially we need to focus on usage of “for loops”.
1st for loop iterates (int i) from the 0 to arr.length-1 of array. This helps to iterate the next for loop through the whole array. Second for loop is bit developed from the original Bubble Sort algorithm. In original algorithm iterates from 0 to arr.length-1, so this will iterate through whole array in every time whether the last elements are already sorted or not. How ever in the given code you will see that 2nd for loop iterates only to arr.length-i-1. With this change it only iterates to unsorted array items. This small change can increase the efficiency of this sorting. I hope to clarify this to you at the end of the code review.
In the if loop I check whether arr[j] is higher than arr[j+1] and if it’s true exchange them. I used variable temp to do this exchange easily.
Now we will see what is the effect we can get with this arr.length-i-1 instead of arr.length-1 in 2nd for loop.
First you should see “Iteration -image1” given below. In here I wrote a code to identify what are the array items compared when 2nd for loop iterates through 0 to arr.length-1. “Iteration -image2” is the screenshot of result you get when that code executes. You will see that it iterates through all array items in all rounds.
Now you can see “Iteration -image3” given below. In here I wrote a code to identify what are the array items compared when 2nd for loop iterates through 0 to arr.length-i-1. “Iteration -image4” is the screenshot you get when that code executes. You will see that it iterates only through unsorted array items.
Anyway I hope that you can understand what I meant by increasing the efficiency. Thinking about an array with hundred items and imagine how this efficiency would effect would help you to find this more understandable.
I hope you will find this article very helpful in learning basics of sorting algorithms. Next article will be about another sorting algorithm and its implementation or algorithm explanation. If there is anything to clarify or solve please don’t hesitate to contact me via my LinkedIn and fb page. Try all of this by yourself and if there is anything feel free to comment. Like and please Share with your friends.
