HASH FUNCTION

Hashing is the transformation of a string of characters into a usually shorter fixed-length value or key that represents the original string. Hashing is used to index and retrieve items in a database because it is faster to find the item using the shorter hashed key than to find it using the original value. It is also used in many encryption algorithms.

Hash Function:

A Hash Function is a Unary Function that is used by Hashed Associative Containers: it maps its argument to a result of type size_t. A Hash Function must be deterministic and stateless. That is, the return value must depend only on the argument, and equal arguments must yield equal results.

Hash functions are mostly used in hash tables, to quickly locate a data record (for example, a dictionarydefinition) given its search key (the headword). Specifically, the hash function is used to map the search key to the index of a slot in the table where the corresponding record is supposedly stored.
Division Method:

2. Tree Traversal

What I've just called ``scanning through'' a tree is actually called traversing a tree.

General Definition: to traverse a data structure is to process, however you like, every node in the data structure exactly once.

Note: You may ``pass through'' a node as many times as you like but you must only process the node once.

E.g. we can talk about ``traversing a list'', which means going through the list and processing every node once. We had a special name for this: map.

For a specific data structure, we talk about the different orders in which it might be traversed. For a list there are two common traversal orders: first-to-last (the most common) and last-to-first.

The general recursive pattern for traversing a (non-empty) binary tree is this: At node N you must do these three things:

Structural Definition of Binary Trees

A binary tree is either empty or it has 3 parts:

• a value
• a left subtree
• a right subtree

Whenever a data structure has a recursive definition like this, most of the `properties' of the data structure can be computed in a recursive manner which exactly mirrors the definition.

For example, here is a function to compute the number of nodes in a binary tree:

        int size(binary_tree *t)

        {

          return is_empty(t) ? 0 : 1 + size(t->left) + size(t->right);

        }

With lists we had an alternative to recursion - we could scan through a list as easily with normal loops (while, do ... while) as with recursion. This is not true for trees. It is possible to scan through a tree non-recursively, but it is not nearly as easy as scanning recursively.

Drawing Trees

Here is how we draw a tree:

The root is at the top; below it are its children. An arc connects a node to each of its children: we sometimes draw arrowheads on the arc, but they are optional because the direction parent->child is always top->bottom.

Then we continue in the same manner, the children of each node are drawn below the node.

For example, here is a binary tree:

       

In general, each child of a node is the root of a tree ``within the big tree''. For example, B is the root of a little tree (B,D,E), so is C. These inner trees are calledsubtrees. The subtrees of a node are the trees whose roots are the children of the node. e.g. the subtrees of A are the subtrees whose roots are B and C. In a binary tree we refer to the left subtree and the right subtree.

1. Introduction To Trees

We will now turn to tree structures, which is the subject of most of the rest of the course.

Definition of Trees

Trees are as common and important as lists. And like lists there are many variations - binary search trees, balanced trees, and heaps are the main ones we will look at.

Recall that a list is a collection of components in which

1.     each component (except one, the first) has exactly 1 predecessor.

2.     each component (except one, the last) has exactly 1 successor.

a tree is very similar: it has property (1) but (2) is slightly relaxed:

(2') each component has some number of successors.

If there is no limit on the number of successors that a node can have, the tree is called a general tree.

Radix sort

Radix sort

            Let a be an array of n numbers. Our aim is to sort this array in ascending order using radix sort. The steps to be followed are

i)                    Initialize ten queues namely q[0], q[1], ………, q[9]. That is set rear [i] = front [i] = NULL for all I = 0, 1, 2, ……,9.

ii)                  Scan the array from left to right and find the least significant digit for all array elements.

iii)                If it is 0, push the number in q[0]; if it is 1, push the number in q[1],….., and if it is 9, push the number in q[9].

iv)                After pushing all the elements in the respective queues, pop up the data from 0^th queue to 9^th queue and restore in the array a.

v)                  Again scan the array from left to right and find the second least significant digit for all array elements.

vi)                Repeats steps (iii) and (iv)

The repetition of the above process depends upon the width of the maximum element in the array. That is if the maximum width of the array element is 3, then scan the array three times and find the 1^st least significant digit and 3^rd least significant digit.

Example

Merge sort

Merge sort

            Let a be an array of n numbers. Our aim is to sort this array in ascending order using merge sort. The steps to be followed are

i)                    Divide the array into n sub arrays with size 1.

ii)                  Merge adjacent pair of sub arrays [a[1]] and [a[2]], [a[3]] and [a[4]], …….,

[a[n-1]] and [a[n]]. Now we will get a n/2 sorted sub arrays of size 2 or less.

iii)                Merge adjacent pairs of sub arrays [a[1]] and [a[2]], [a[3]] and [a[4]], ……., [a[n-3]], [a[n-2]] and [a[n-1

iv)                Repeat this process until ther]], [a[n]]. Now we will get a n/4 sorted sub arrays of size 4 or less.e is only one sub array of size n.

Now this array will be in sorted order

Example

Merge

Merge

            Merging is a process of combining two or more sorted arrays into a single sorted array.

Explanation

            Suppose A[m] and B[n] are two sorted arrays. Merging is a process of combining these two arrays into a single sorted array C[m+n]. Steps to be followed are

i)                    Scan both arrays left to right

ii)                  Compare A[1] with B[1]. If A[1] is less than B[1] put A[1] as C[1] and compare A[2] with B[1] and so on, else put B[1] as C[1] and compare A[1] with B[2] and so on.

iii)                Repeat step ii until any one array becomes empty.

iv)                If A array becomes empty, store all the remaining B array elements in the same order in the C array. Besides store all the remaining A array elements in the same order in the B array.

Procedure

Selection sort

Selection sort

            Let A be an array of n elements A[1], A[2], …., A[n]. Our aim is to sort the numbers in the array in ascending order. The steps are as follows

1)      Find the smallest element position in the list A[1], A[2], …., A[n] say k₁ and interchange the values A[1] and A[k₁]

2)      Find the smallest element position in the list A[2], A[3], ….., A[n] say k₂ and interchange the values A[2] and A[k₂].

3)      Find the smallest element position in the list A[3], A[4], ….., A[n] say k₃ and then interchange the values A[3] and A[k₃]

4)      Find the smallest element position in the list A[n-1] and A[n] say k_n-1 and then interchange the values A[n] and A[k_n-1].

Example -        Sort the array A using selection sort

                        A = (43, 72, 10, 23, 80, 1, 75)

           

Insertion sort

Insertion sort

            Let a be an array of numbers a[1], a[2] ….. a[n]. Our aim is to sort them in ascending order using insertion sort.

Principle

            Scan the array a from a[1] to a[n] and find the smallest elements a[r], r = 1, 2 ……, r and insert into its proper position in the previously sorted sub array a[1], a[2] ….  a[r]. This can be explained by the following steps.

i)                    For r = 1 the previously sorted such array is empty therefore a[1] by itself is sorted.

ii)                  For r =2 , a[2] is inserted into the proper position in the previously sorted sub array a[1] i.e.; a[2] is inserted after or before a[1].

iii)                For r = 3, a[3] is inserted into the proper position in the previously sorted sub array a[1], a[2]. i.e.; a[3] is inserted either before a[1] or after a[2] or in between a[1] and a[2].

The above steps are repeated until the last element a[n] is inserted into its proper position in the sorted sub array. Now the given array a is in sorted order.

Example

Bubble sort

Bubble sort

            Let a be an array of n numbers. Our aim is to sort the numbers in the array in ascending order. The principle is to scan the array sequentially n-1 times and in each scan do the following steps.

Scan – 1

i)                    Take the first element and compare it with the second element. If it is small don’t interchange; or else interchange the two elements.

ii)                  Then compare the second element with the third element. If it is small don’t interchange; or else interchange the two elements.

iii)                This process is continued till (n-1)^th element is compared with the n^th element.

iv)                At the end of the first scan, the highest element comes to the n^th position.

Scan – 2

SORTING

1 Sorting

General Concepts

            A file is an ordered collection of items.Each item in the file is called a record. The records are named as r[1], r[2],…..r[n], where n is the size of the file.

            A key is associated with each record r[i] and through this key only we can identify the records in the file.