Computer Notes

Header Right

Home » DS » Searching and Sorting

What is Hashing?

By Dinesh Thakur

A class of algorithm that helps to provide very rapid access to data items that can be distinguished by some KEY value, for example a person’s name, or a filename. This key value is passed through a HASH FUNCTION which creates from it a number that is used as an index into a HASH TABLE containing pointers to the actual data items.

A simple hash function might be the alphabetic order of the first letter of a person’s name, so that, say, Pountain would hash to the 16th slot in the table. However, this would be a very poor hash function since every name beginning with P would hash to the same slot, an occurrence known as a hash clash or hash collision. Whenever such a collision occurs, the new item that caused it must be stored either in the next free adjacent table slot, or on a LIN KED LIST pointed to by the table slot. If too many such collisions occur, the algorithm degenerates into a case of LINEAR SEARCH. Designing a good hashing algorithm involves choosing a hash function that distributes the items widely and evenly, without requiring too large a hash table.

What is Stack

By Dinesh Thakur

An important subclass of lists permits the insertion and deletion of an element to occur only at one end. A linear list of this type is known as ‘stack’.

The insertion is referred to as ‘push’. The deletion is referred to as ‘pop’. The two pointers used for accessing is top & bottom pointer.

 

PUSH – Storing the element into the stack.

Check top<= allowed size if yes increment the top position and store the value in the top position.

POP –  Deleting the element from the stack. If top<= we can not delete.

Otherwise decrement the top by one and return the top+1 element.

 

What is Sorting? Type of Sorting

By Dinesh Thakur

Sorting refers to ordering data in an increasing or decreasing fashion according to some linear relationship among the data items.

 Sorting can be done on names, numbers and records. Sorting reduces the For example, it is relatively easy to look up the phone number of a friend from a telephone dictionary because the names in the phone book have been sorted into alphabetical order.

This example clearly illustrates one of the main reasons that sorting large quantities of information is desirable. That is, sorting greatly improves the efficiency of searching. If we were to open a phone book, and find that the names were not presented in any logical order, it would take an incredibly long time to look up someone’s phone number.

Sorting can be performed using several methods, they are:

Insertion sort.

In this method, sorting is done by inserting elements into an existing sorted list. Initially, the sorted list has only one element. Other elements are gradually added into the list in the proper position.

Merge Sort.

In this method, the elements are divided into partitions until each partition has sorted elements. Then, these partitions are merged and the elements are properly positioned to get a fully sorted list.

Quick Sort.

In this method, an element called pivot is identified and that element is fixed in its place by moving all the elements less than that to its left and all the elements greater than that to its right.

Radix Sort.

In this method, sorting is done based on the place values of the number. In this scheme, sorting is done on the less-significant digits first. When all the numbers are sorted on a more significant digit, numbers that have the same digit in that position but different digits in a less-significant position are already sorted on the less-significant position.

Heap Sort

In this method, the file to be sorted is interpreted as a binary tree. Array, which is a sequential representation of binary tree, is used to implement the heap sort.

The basic premise behind sorting an array is that its elements start out in some random order and need to be arranged from lowest to highest.

It is easy to see that the list

1, 5, 6, 19, 23, 45, 67, 98, 124, 401

is sorted, whereas the list

4, 1, 90, 34, 100, 45, 23, 82, 11, 0, 600, 345

is not. The property that makes the second one “not sorted” is that there are adjacent elements that are out of order. The first item is greater than the second instead of less, and likewise the third is greater than the fourth and so on. Once this observation is made, it is not very hard to devise a sort that proceeds by examining adjacent elements to see if they are in order, and swapping them if they are not.

Selection sort: In this technique, the first element is selected andcompared with all other elements. If any other element is less thanthe first element swapping should take place.By the end of this comparison, the least element most top position in the array. This is known as pass1. In pass II, the second element is selected and compared with all other elements. Swapping takes place if any other element is less than selected element. This process continuous until array is sorted.

The no. of passes in array compare to size of array –1.

Bubble sort: This technique compares last element with the preceding element. If the last element is less than that of preceding element swapping takes place. Then the preceding element is compared with that previous element. This process continuous until the II and I elements are compared with each other. This is known as pass 1.

This way the number of passes would be equal to size of array –1.

What is Bubble Sort

By Dinesh Thakur

This sorting technique is named so because of the logic is similar to the bubble in water. When a bubble is formed it is small at the bottom and when it moves up it becomes bigger and bigger i.e. bubbles are in ascending order of their size from the bottom to the top.

This sorting method proceeds by scanning through the elements one pair at a time, and swapping any adjacent pairs it finds to be out of order.

           Bubble Sort

Each pass consists of comparing each element in the file with its successor (x[i] > x[i+1]) Swap the two elements if they are not in proper order. After each pass i, the largest element x[n-(i- 1)] is in its proper position within the sorted array.

Bubble Sort – Algorithm

bubble(int x[], int n)

{

    int hold, j, pass;

    int switched = TRUE;

    for (pass = 0; pass < n – 1 && switched == TRUE; pass++)

     {

          switched = FALSE;

          for (j = 0; j < n-pass-1; j++)

               if (x[j] > x[j+1])

                  {

                       switched = TRUE; /* swap x[j], x[j+1] */

                       hold = x[j];

                       x[j] = x[j+1];

                      x[j+1] = hold;

                 }

      } /* it stops if there is no swap in the pass */

}

In the first pass, n-1 items have to be scanned. On the second pass, the second largest item will move to its correct position, and on the third pass (stopping at item n-3) the third largest will be in place. It is this gradual filtration, or bubbling of the larger items to the top end that gives this sorting technique its name.

There are two ways in which the sort can terminate with everything in the right order. It could complete by reaching the n-1st pass and placing the second smallest item in its correct position.

Alternatively, it could find on some earlier pass that nothing needs to be swapped. That is, all adjacent pairs are already in the correct order. In this case, there is no need to go on to subsequent passes, for the sort is complete already. If the list started in sorted order, this would happen on the very first pass. If it started in reverse order, it would not happen until the last one.

What is Quick Sort in C

By Dinesh Thakur

Quicksort in C follows the divide and conquer algorithm. In 1959, Tony Hoare, a British computer scientist, developed Quicksort, also known as partition-exchange sort. Since its publication in 1961, Quicksort has become one of the top algorithms to sort. It can be done in-place, which requires small additional memory to sort.

The Quicksort is the fastest known sort algorithm because of its highly optimized partitioning of an array of data into smaller arrays. An extensive array partition into two arrays holds values smaller than the specified value, say pivot, based on which the partition is made. Another array contains values more than the pivot value. Median-of-three partitioning is the best way to choose a suitable pivot element. Once a pivot has select, its position finalizes in the sorted array. It can’t change.

[Read more…] about What is Quick Sort in C

What is Heap Sort

By Dinesh Thakur

In heap sort the file to be sorted is interpreted as a binary tree. The sorting technique is implemented using array, which is a sequential representation of binary tree. The positioning of a node is given as follows

For a node at position i the parent is at position i/2, the left child is at position 2i and right child is at position 2i+1 ( 2i and 2i+1 <=n, otherwise children do not exist).

Heap sort is a two stage method. In the first stage the tree representing the input data is converted into a heap. A heap can be defined as a complete binary tree with the property that the value of each node is at least as large as the value of its children nodes. This, in turn, gives the root of the tree as the largest key. In the second stage the output sequence is generated in decreasing order by outputting the root and restructuring the remaining tree into a heap.

Example

The list of numbers 34, 8, 64, 51, 32, 21 is arranged in an array initially as in Input file of the example given below. Here the value of n is 6, hence the least parent is 6/2 = 3. Left child of 64 (index 3) is compared with largest child, since 64 > 21 it is retained in its position. Parent 8 (index 2) is compared with its largest child 51 and are interchanged since 8 < 51. Now root 31(index 1) is compared with its largest child 64 and are interchanged since 34 < 64 and is shown in initial heap.

 1

In fig (a) given below, the first largest number 64 which was brought into root is interchanged with the last element 21 (index 6) in the tree. For easy identification of arranged elements the edge is removed from its parent. In fig (b) given below, the same procedure is followed to bring 51 to root and is interchanged with the element in index 5. The same step is followed in fig (c) and fig (d) to get a sorted file as given in fig (e)

AB

 

CD

E

Algorithm 1 : Heap Sort implementation

Heap is an algorithm which sorts the given set of numbers using heap sort technique. Where ‘n’ is the number of elements, ‘a’ is the array representation of elements in the input binary tree. The heap algorithm 1 calls adjust algorithm 2 each time when heaping is needed.

 

heap(a,n)

{

Int i,t;

for(i=n/2;i>=1;i–)

{

adjust(a,i,n);

}

for(i=n;i>=2;i–)

{

t=a[i];

a[i]=a[1];

a[i]=t;

adjust(a,1,i-1);

}

}

 

Algorithm 2

 

adjust(int x[10],int i, int n)

{

int item, j;

j=2 * i;

item = x[i];

while (j <=n)

{

if((j<n)&&(x[j]<x[j+1]))

j=j+1;

if(item>=x[j])

break;

x[j/2]=x[j];

j=2 * j;

}

x[j/2]=item;

return 0;

}

What is Searching

By Dinesh Thakur

Searching is a process of locating a particular element present in a given set of elements. The element may be a record, a table, or a file.

A search algorithm is an algorithm that accepts an argument ‘a’ and tries to find an element whose value is ‘a’. It is possible that the search for a particular element in a set is unsuccessful if that element does not exist. There are number of techniques available for searching.

 

 

What is Linear Search

By Dinesh Thakur

In Linear Search the list is searched sequentially and the position is returned if the key element to be searched is available in the list, otherwise -1 is returned. The search in Linear Search starts at the beginning of an array and move to the end, testing for a match at each item.

All the elements preceding the search element are traversed before the search element is traversed. i.e. if the element to be searched is in position 10, all elements form 1-9 are checked before 10.

Algorithm : Linear search implementation

bool linear_search ( int *list, int size, int key, int* rec )

{

     // Basic Linear search

     bool found = false;

     int i;

     for ( i = 0; i < size; i++ )

           {

                if ( key == list[i] )

                      break;

            }

              if ( i < size )

                 {

                      found = true;

                      rec = &list[i];

                 }

               return found;

} 

The code searches for the element through a loop starting form 0 to n. The loop can terminate in one of two ways. If the index variable i reach the end of the list, the loop condition fails. If the current item in the list matches the key, the loop is terminated early with a break statement. Then the algorithm tests the index variable to see if it is less than that size (thus the loop was terminated early and the item was found), or not (and the item was not found).

Ex.

Assume the element 45 is searched from a sequence of sorted elements 12, 18, 25, 36, 45, 48, 50. The Linear search starts from the first element 12, since the value to be searched is not 12 (value 45), the next element 18 is compared and is also not 45, by this way all the elements before 45 are compared and when the index is 5, the element 45 is compared with the search value and is equal, hence the element is found and the element position is 5.

     Linear Search

What is Binary Search

By Dinesh Thakur

In a linear search the search is done over the entire list even if the element to be searched is not available. Some of our improvements work to minimize the cost of traversing the whole data set, but those improvements only cover up what is really a problem with the algorithm.

By thinking of the data in a different way, we can make speed improvements that are much better than anything linear search can guarantee. Consider a list in sorted order. It would work to search from the beginning until an item is found or the end is reached, but it makes more sense to remove as much of the working data set as possible so that the item is found more quickly.

 

If we started at the middle of the list we could determine which half the item is in (because the list is sorted). This effectively divides the working range in half with a single test. This in turn reduces the time complexity.

 

Algorithm:

 

bool Binary_Search ( int *list, int size, int key, int* rec )

{

bool found = false;

int low = 0, high = size – 1;

while ( high >= low )

{

int mid = ( low + high ) / 2;

if ( key < list[mid] )

high = mid – 1;

else

if ( key > list[mid] )

low = mid + 1;

else

{

found = true;

rec = &list[mid];

break;

}

}

return found;

}

 

Binary Search