Selection Sort

Selection sort is a sorting algorithm that works by repeatedly selecting the smallest (or largest) element from the unsorted portion of the list and moving it to the sorted portion of the list. 

The smallest element is selected from the unsorted array and swapped with the leftmost element and it becomes part of sorted array. This process continues until all the elements are sorted.

This algorithm is not suitable for large data sets as its average and worst case complexities are of O(n²).

Ex:

14        33        27        10        35        19        42        44

Find the lowest value which is 10 and swap it with 14 which is left most value

10        33        27        14        35        19        42        44

For second position we find 14 is second lowest so it is swapped into second position

10        14        27        33        35        19        42        44

The same process is applied

10        14        19        33        35        27        42        44

 

10        14        19        27        35        33        42        44

 

10        14        19        27        33        35        42        44

Now the list is in sorted order.

Function Code:

void SelectionSort(int A[ ], int n)

{

int i, j;

int minpos, temp;

for(i = 0; i < n − 1; i++)

{

minpos = i;

for(j = i + 1; j < n; j++)

//find the position of min element as minpos from i + 1 to n − 1

{

if(A[j] < A[minpos])

minpos = j;

}

if(minpos != i)

{

temp = A[i];

// swap the i^th element and minpos element

A[i] = A[minpos];

A[minpos] = temp;

}

}

}

Insertion Sort

Insertion sort maintains a sub-list which is always sorted. The array is searched sequentially and unsorted items are moved and inserted into the sorted sub list.

The lower part of an array is maintained to be sorted. An element which is to be inserted in this sorted sub list has to find its appropriate place and then it has to be inserted there.

This algorithm is not suitable for large data sets as its average and worst case complexity are of O(n²).

Ex:

14        33        27        10        35        19        42        44

Insertion sort compares first two elements. Here both are already in ascending order. now 14 is in sorted sub list.

14        33        27        10        35        19        42        44

Insertion sort now compares 33 with 27 and finds 33 is not in correct position. It swaps 33 with 27.

14        27        33        10        35        19        42        44

It also checks all elements in sub list of sorted order. Here sub list is sorted.

Similarly 10 compared with 33

14        27        10        33        35        19        42        44

14        10        27        33        35        19        42        44

10        14        27        33        35        19        42        44

 

comparing 33 and 35, they are in order

10        14        27        33        35        19        42        44

compare 35 with 19, they are not in order, a swap is performed

10        14        27        33        19        35        42        44

Now sublist is sorted

10        14        19        27        33        35        42        44

This process is continued until all unsorted values are placed in the sorted sub list.

 

Insertion sort function code:

void InsertionSort(int A[], int n)

{

int i, j, element;

for(i = 1; i < n; i++)

{

element = A[i];

// insert ith element in 0 to i − 1 array

j = i;

while((j > 0) && (A[j − 1] > element))

//compare if A[j − 1] > element

{

A[j] = A[j − 1]; // shift elements

j = j − 1;

}

A[j] = element; // place element at jth position

}

}

Bubble Sort

Bubble sort is a comparison based algorithm. The bubble sort works by comparing each item in the list with the item next to it and swapping them if required. The algorithm repeats this process until it makes a pass all the way through the list without swapping any items

Example:

consider list : 2,9,5,4,1,3

The number of comparisons made at each of the iterations is as follows:

(n - 1) comparisons in the first iteration, (n - 2) comparisons in the second iteration, ... , one comparison in the last iteration. Thus, the total number of comparisons is n(n - 1)/2, which is O(n²).

Hence, the time complexity for each of the cases is given by the following:

1. Average case complexity = O(n²)

2. Best case complexity = O(n²)

3. Worst case complexity = O(n²)

Sorting

Sorting is the operation of arranging the records of a table according to the key value of each record, or it can be defined as the process of converting an unordered set of elements to an ordered set.

Sorting algorithms are divided into two categories: internal and external sorts.

Any sort algorithm that uses main memory exclusively during the sorting is called as an internal sort algorithm.

Any sort algorithm that uses external memory, such as tape or disk, during the sorting is called as an external sort algorithm.

Internal sorting is faster than external sorting.

Searching (Sequential and Binary search)

The process of locating required data is known as searching. Searching is the process of finding the location of the target among a list of objects.

A searching algorithm accepts two arguments as parameters—a target key value to be searched and the list to be searched. The search algorithm searches a target key value in the list until the target key is found or can conclude that it is not found.

Search techniques

The two basic search techniques are:

1. Sequential search

2. Binary search

i. Sequential Search

The easiest search technique is a sequential search. Sequential search begins with the first available record and proceeds to the next available record repeatedly until we find the target key or conclude that it is not found. Sequential search is also called as linear search.

Sequential search is suitable when the data is stored in an unordered manner and also when there is no way to directly access the data elements.

Algorithm:

1. Set i = 0, flag = 0

2. Compare key[i] and target

if(key[i] = target)

Set flag = 1, location = i and goto step 5

3. Move to next data element

i = i + 1

4. if(i < n) goto step 2

5. if(flag = 1) then

return i as position of target located

else

report as ‘Target not found’

6. stop

 

Consider the example

Index	0	1	2	3	4	5	6
Key	20	15	12	9	5	13	10

 

Let target data be 9.

Initially, i = 0 and the target element 9 is to be searched. At each pass, the target 9 is compared with the element at the i^th location till it is found or the index i exceeds the size.

The number of comparisons depends on where the target data is stored in the search list. If the target data is placed at the first location, we get it in just one comparison. Two comparisons are needed if the target data is in the second location. Similarly, i comparisons are required if the target data is at the i^th location and n comparisons, if it is at the nth location.

The average number of comparisons done by the sequential search method in the case of a successful search is (n + 1)/2.

An unsuccessful search is given by n comparisons. The number of comparisons is n and the complexity is denoted as O(n) which is worst case.

The best case complexity is 1, as the target data element is at the first location and requires only a single comparison.

Advantages

1. A simple and easy method

2. Efficient for small lists

3. Suitable for unsorted data

4. Suitable for storage structures which do not support direct access to data.

Disadvantages

1. Highly inefficient for large data.

ii. Binary Search

Binary search is the fast search algorithm with the time complexity of O(log n). It works on the principle of divide and conquer. This algorithm works on sorted data lists.

In binary search algorithm, to search for a particular element, it is first compared with the element at the middle position, and if it is found, the search is successful, else if the middle position value is greater than the target, the search will continue in the first half of the list; otherwise, the target will be searched in the second half of the list. The same process is repeated for one of the halves of the list till the list is reduced to size one.

Algorithm

1. Let n be size of the list

Let target be the element to be searched

Let flag = 0, low = 0, high = n-1

2. if low <= high, then

middle = (low + high)/2

   else goto step (5)

3. if(key[middle] = target)

Position = middle, fl ag = 1

Goto step (5)

   else if(key[middle] > target) then

high = middle − 1

   else

low = middle + 1

4. Goto step(2)

5. if flag = 1

report as target element found at location ‘position’

   else

report that element is not found in the list

6. stop

 

Consider the list

Index	0	1	2	3	4
Value	10	14	19	26	31

 

Let the target item be 26

compute mid= (low+high)/2

=(0+4)/2  = 2

So the mid of list is 2(index). It contains value 19. Compare 19 with target item 26. Since 19< 26

search is performed on right sublist.

 

Index	3	4
Value	26	31

 

Now low=mid+1   = 2+1  = 3

mid = (3+4)/2 =3

The data item in index 3 is 26 and it is equal to target data item. Search algorithm returns the index 3 and search is finished.

Advantages

1. Suitable for sorted data

2. Efficient for large lists

3. Suitable for storage structures that support direct access to data

4. Time complexity is O(log₂(n))

Disadvantages

1. Not applicable for unsorted data

2. Not suitable for storage structures that do not support direct access to data.

3. Inefficient for small lists

Threaded Binary Tree

In Binary tree representation using linked list, if there are 2N number of reference fields, then N+1 number of reference fields are filled with NULL. This NULL pointer has no role except indicating no link(no child).

To solve this problem, A.J. Perlis and C. Thornton have suggested replacing all the Null links by pointers, called threads. A tree with a thread is called a threaded binary tree (TBT).

Threaded Binary tree is a binary tree in which all the left child pointers that are NULL points to its in-order predecessor, and all right child pointers that are NULL points to its in-order successor. If there is no in-order predecessor or in-order successor, then it points to Root node.

Threads utilize the NULL pointers waste space to improve the processing efficiency.

Consider the following binary tree:

To convert the above example binary tree into a threaded binary tree, first find the in-order traversal of that tree.

In-order traversal of above binary tree is H - D - I - B - E - A - F - J - C - G

In the binary tree, nodes H, I, E, F, J and G left child pointers are NULL. This NULL is replaced by address of its in-order predecessor respectively. This NULL is replaced by address of its in-order predecessor (I to D, E to B, F to A, J to F, G to C). Here node H does not have its in-order predecessor, so it points to the root node A.

Nodes H, I, E, J and G right child pointers are NULL. These NULL pointers are replaced by address of its in-order successor respectively (H to D, I to B, E to A, and J to C), but here the node G does not have its in-order successor, so it points to the root node A.

The converted threaded binary tree is

Advantages and disadvantages over a non-threaded binary tree:

1. The traversal for a TBT is straightforward. No recursion or stack is needed.

2. At any node, the node’s successor and predecessor can be located. In case of nonthreaded binary tree, this task is time consuming and difficult. In addition, stack is needed for the same.

3. In a threaded tree, traversal can be done in either direction, and the nodes are in fact circularly linked. Hence, any node can be reached from any other node.

4. Insertions into and deletions from a threaded tree are time consuming as the link and thread are to be manipulated.

Binary Tree and Binary search Tree

1. A BST is a special case of the binary tree. Both of them are trees with degree two, that is, each node has utmost two children.

2. The BST is a binary tree with the property that the value in a node is greater than any value in a node’s left subtree and less than any value in a node’s right subtree.

3. The BST guarantees fast search time provided the tree is relatively balanced, whereas for a binary tree, the search is relatively slow.

Given a binary tree with no duplicates, we can construct a BST from a binary tree. The process is easy; one can traverse the binary tree and construct a BST for it by inserting each node in an initially empty BST.