D Learning Academy by Deshani Jayasuriya

Algorithms
Algorithms are step-by-step plans for solving problems. Algorithms can be designed using pseudo-code,
flowcharts, written descriptions and program code. There are also some standard algorithms for searching and
sorting.

What are sorting algorithms

• Rearranging the elements of a list in ascending or descending order is called sorting.
• Sorting algorithms are based on comparing values or some may be based on analyzing properties
of values.
• For example, if you know that your list only holds values from 0 to 9, you can just count how
many of each in one sweep (O(n)) and construct the sorted list.
Examples of sorting applications:

• a directory of files sorted by name or date

• bank checks sorted by account #
• addresses in a mailing list sorted by zip code
• hits found by a search engine sorted by relevance
• credit card transactions sorted by date
Sorting Categories

• Sorting by Insertion-> insertion sort, shellsort

• Sorting by Exchange-> bubble sort, quicksort

• Sorting by Selection-> selection sort, heapsort

• Sorting by Merging-> merge sort

• Sorting by Distribution-> radix sort

Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are
in the wrong order. This algorithm is not suitable for large data sets as its average and worst-case time complexity
is quite high.

• Compares adjacent array elements

– Exchanges their values if they are wrong order

• Smaller values bubble up to the top of the array

– Larger values sink to the bottom

2 9 5 4 8 1 2 5 4 8 1 9 2 4 5 1 8 9 2 4 1 5 8 9 1 2 4 5 8 9
2 5 9 4 8 1 2 4 5 8 1 9 2 4 5 1 8 9 2 1 4 5 8 9
2 5 4 9 8 1 2 4 5 8 1 9 2 4 1 5 8 9
2 5 4 8 9 1 2 4 5 1 8 9
2 5 4 8 1 9

(a) 1st pass (b) 2nd pass (c) 3rd pass (d) 4th pass (e) 5th pass

1
 D Learning Academy by Deshani Jayasuriya

How does Bubble Sort Work?

Input: arr[] = {5, 1, 4, 2, 8}

First Pass:
• Bubble sort starts with very first two elements, comparing them to check which one is greater.
• ( 5 1 4 2 8 ) –> ( 1 5 4 2 8 ), Here, algorithm compares the first two elements, and swaps since 5 > 1.
• ( 1 5 4 2 8 ) –> ( 1 4 5 2 8 ), Swap since 5 > 4
• ( 1 4 5 2 8 ) –> ( 1 4 2 5 8 ), Swap since 5 > 2
• ( 1 4 2 5 8 ) –> ( 1 4 2 5 8 ), Now, since these elements are already in order (8 > 5), algorithm does not
swap them.
Second Pass:
• Now, during second iteration it should look like this:
• ( 1 4 2 5 8 ) –> ( 1 4 2 5 8 )
• ( 1 4 2 5 8 ) –> ( 1 2 4 5 8 ), Swap since 4 > 2
• ( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
• ( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
Third Pass:
• Now, the array is already sorted, but our algorithm does not know if it is completed.
• The algorithm needs one whole pass without any swap to know it is sorted.
• ( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
• ( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
• ( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
• ( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
Illustration:

2
D Learning Academy by Deshani Jayasuriya
Recommended Problem

3
 D Learning Academy by Deshani Jayasuriya
Merge sort

A merge sort is a more complex sort, but also a highly efficient one. A merge sort uses a technique called
Divide and Conquer. The list is repeatedly divided into two until all the elements are separated
individually. Pairs of elements are then compared, placed into order and combined. The process is then
repeated until the list is recompiled as a whole.

Merge Sort: Idea

• Divide: divide the n-element sequence to be sorted into two subsequences of n/2 elements each
• Conquer: sort the two subsequences recursively using merge sort
• Combine: merge the two sorted subsequences to produce the sorted answer

2 9 5 4 8 1 67
split
2 9 5 4 8 1 6 7
split divide
2 9 5 4 8 1 6 7
split
2 9 5 4 8 1 6 7
merge
2 9 4 5 1 8 6 7
conqure
merge
2 4 5 9 1 6 7 8

merge
1 2 4 5 6 7 89

4
 D Learning Academy by Deshani Jayasuriya
• Merge Algorithm
– Access the first item from both sequences
– While not finished with either sequence
• Compare the current items from the two sequences, copy the smaller current item to
the output sequence, and access the next item from the input sequence whose item
was copied
– Copy any remaining items from the first sequence to the output sequence
– Copy any remaining items from the second sequence to the output sequence

Consider this unsorted list:

The list is split into half:

The process repeats:

Until all elements are individually separated:

5
 D Learning Academy by Deshani Jayasuriya
The algorithm looks at the individual elements and compares them as pairs. Each pair is sorted into
order:

The pairs are then compared, starting with the first number in each pair. If the left-hand number is
smaller than the right-hand number, it is placed in order. The comparison then moves up to the second
number on the left-hand side and the process repeats. If the right-hand number is smaller, it is placed in
order and the comparison moves to the next number on that side.

Here, 7 is the first left hand number and 5 is the first right hand number. 7 is bigger than 5, so 5 is placed
in order:

5
The next right-hand number is 10. 7 is smaller than 10, so 7 is placed in order:
5 7
The next left-hand number is 11. 11 is bigger than 10, so 10 is placed in order:
5 7 10
There are no more right-hand numbers to compare, so the remaining left-hand numbers are placed in
order:
5 7 10 11
The process is repeated for the initial right-hand division:

Eventually the list is recompiled:

The list is now sorted into the correct order.

The Merge Sort algorithm is a sorting algorithm that is based on the Divide and Conquer paradigm. In this
algorithm, the list of numbers is initially divided into two equal halves and then they are combined in a sorted
manner.

The first stage is where the list is split until it forms individual elements called sub-lists. After this, the 'merge'
stage begins. Here the sub-lists are paired up and are arranged according to the order stated
(ascending/descending). these paired lists are paired again to form groups of 4 and are again arranged according
to the intended/ given order. This process happens until the sub-lists form one list.

6
 D Learning Academy by Deshani Jayasuriya
Merge Sort Working Process:

Think of it as a recursive algorithm continuously splits the array in half until it cannot be further divided. This
means that if the array becomes empty or has only one element left, the dividing will stop, i.e. it is the base case
to stop the recursion. If the array has multiple elements, split the array into halves and recursively invoke the
merge sort on each of the halves. Finally, when both halves are sorted, the merge operation is applied. Merge
operation is the process of taking two smaller sorted arrays and combining them to eventually make a larger one.

Illustration:

To know the functioning of merge sort, lets consider an array arr[] = {38, 27, 43, 3, 9, 82, 10}

• At first, check if the left index of array is less than the right index, if yes then calculate its mid-point

Now, as we already know that merge sort first divides the whole array iteratively into equal halves, unless the
atomic values are achieved.

• Here, we see that an array of 7 items is divided into two arrays of size 4 and 3 respectively.

• Now, again find that is left index is less than the right index for both arrays, if found yes, then again calculate
mid points for both the arrays.

• Now, further divide these two arrays into further halves, until the atomic units of the array is reached and further
division is not possible.

7
 D Learning Academy by Deshani Jayasuriya
• After dividing the array into smallest units, start merging the elements again based on comparison of size of
elements
• Firstly, compare the element for each list and then combine them into another list in a sorted manner.

• After the final merging, the list looks like this:

The following diagram shows the complete merge sort process for an example array {38, 27, 43, 3, 9, 82, 10}.

If we take a closer look at the diagram, we can see that the array is recursively divided into two halves till the size
becomes 1. Once the size becomes 1, the merge processes come into action and start merging arrays back till the
complete array is merged.

8
 D Learning Academy by Deshani Jayasuriya
Recursive steps of merge sort

Algorithm:

step 1: start
step 2: declare array and left, right, mid variable
step 3: perform merge function.
if left > right
return
mid= (left+right)/2
mergesort(array, left, mid)
mergesort(array, mid+1, right)
merge(array, left, mid, right)
step 4: Stop
Merge sort, advantages and disadvantages

9
 D Learning Academy by Deshani Jayasuriya

Exercises
1.Complete the following exercises using Bubble sort

5 2 1 3 7 4

2 3 1 5 6 4

1 4 3 6 2 5

6 5 1 3 2 4

2.What is the use of pass in bubble sort?

3.Name 3 types of sorting techniques and briefly explain them.

10