Monday, May 27, 2019

HASHING

   Hashing finds the location of an element in a data structure without any comparisons.In contrast to the other comparison based searching techniques,like linear and binary search,hashing uses a mathematical function to determine the location of an elements.

   Hash Table: The hash table data structure is an array of some fixed size,containing the keys.A key is a value associated with each record.

    Hash Function: It accepts a value known as key as input and generates an output known as hash key. The hash function generates hash keys and stores elements corresponding to each hash key in the hash table. 

EXAMPLE

                 Hash(95)= 92 mod 10 =2
              
                Key value 92 is placed in location 2.

  • Hashing is used for faster access of elements and record from the collection of tables and files.
  • Hashing is applied where the array size is large and time taken for searching an element is more.

Collision:

  • Two different records are indicated to be stored at the same position in the hash table.this situation is termed as collision.
  • several collision resolution techniques are used to overcome this problem.These techniques are:
                        1.Separate chaining 
                        2.Open addressing
                        3.Rehashing
                        4. Extendible hashing                                                           





                        

Wednesday, May 22, 2019

BINARY SEARCH






  • Binary search is simpler and faster than the linear search.
  • For an given array of n elements, the basic idea of  binary search is that for a given elements,we 'probe' the middle element of an array.
                     
  • We continue in either lower or upper segment of the array depending on the outcome of the probe until we reached the required element.

EXAMPLE:

        Binary search (A,20,0,6)⇨Target 20.
  • Element 20 is in the position 6.


Efficiency:
  • Best case:O(n)
  • worst case:O(log2n)      
Advantages: 
  • It requires lesser number of iterations.
  • It is a lot faster  than linear search.
Disadvantages:
  • Unlike linear search ,it requires the list to be sorted before search can be performed.
  • In comparison to linear search, the binary search  technique may seem to be a little difficult to implement.




Thursday, March 28, 2019

LINEAR (OR) SEQUENTIAL SEARCH


  • This is the simplest known techniques for searching an array for a particular record or data element.
  • In  LINEAR  search we start with the first available element,that is the element that comes  first.
  • If this is the required element then our search is over,else we take up the second element and see if this is the element that we need.
  • If this too is not the require element then we pick up third element.
  • This process of considering the next record will go on till we find required element or all the elements in the table are empty.

EXAMPLE

        

To find the 61 from the given list.
        
61!=4,so we move the pointer to the next position,
           
          
61!=21,so we move the pointer to the next position,
        
            
61!=36,so we move the pointer to the next position,

             
61!=15,so we move the pointer to the next position. 

                 
  •  Element 61 is in the position 4.

Efficiency:

  • The efficiency of linear (or) sequential search is O(n).  

Advantages:    

  • It is a simple searching technique that is easy to implement.
  • It does not require the list to be sorted in a particular order.
Disadvantages:

  • It is quite inefficient for large sized lists.
  • It does not leverage the presence of any pre_existing  sort order in a list.
                               *****    








         

SEARCHING


  • Searching refers to determining whether an elements is present in a given list of elements or not.
  • If the element is found to be present in the list then the search is considered as successful, otherwise it is consider as an unsuccessful search. 
  • The search operation returns the location or address of the element found.
       

Searching Techniques

          To search an element in a given array,it can be done in following ways,
  1. Sequential search (or) linear search.
  2. Binary search.
We see this searching techniques on the following post.

Friday, March 22, 2019

RADIX SORT


  • Radix sort sorts the elements by processing its individual digits. Radix sort processing the digits either by LSD(Least Significant Digits) method by most processing digits (MSD) method. 
      Least Significant Digit(LSD):
         

  • It is the lowest digit in a number,located at the far right of the string.          
      Example
          
                  
      Most Significant Digit:

  • Most Significant Digit is the far left in a string of digit.
     Example
     
                      

  • Radix sort is clever and intuitive little sorting algorithm radix sort puts the elements in order by comparing the digits of the numbers. 
EXAMPLE
Consider the following numbers, 
                 
  • We should starting by comparing  and ordering the one's digits.
  • Radix sort is generalized from bucket sort. it can be performed using buckets from 0 to 9. 
                 
  • In second pass the numbers are arranged according to the next least significant bit and so on.This process is repeated until it reaches the most significant bits of all numbers.
         

  • Now the sub-lists are created again, this time based on the ten's digit.
             
  • Now the sub-list are created according to the hundred's digit.
                   
After Radix Sort:

           

Complexity:

  • Worst case:O(n)
  • Best case:O(n)
  • Average case:O(n)

Advantages:

  • Radix sort is very simple.
  • A computer can do it fast.
  • Radix sort is in fact one of the fastest sorting algorithm for numbers or strings of letters.

Disadvantages:

  • Radix sort can be slower than some other algorithms such as Quick Sort and Merge Sort.
  • It can take-up more space than other sorting algorithms,since in addition to the array that will be sorted.
                            ****** 





    

QUICK SORT

Like Merge Sort ,Quick-sort is a divide and conquer algorithm.it picks an element as pivot and partitions the given array around the picked pivot. 
There are a number of ways to pick the pivot element for example,we will use the 1st element in the array as pivot.

  1. Move left index until we find an element > pivot.
  2. Move right index until we find an element < pivot.
  3. If indexes have not crossed, swap values and repeat step1 & step2.
  4. If indexes have crossed swap pivot & left index.
If array  only contains one element,return
else

  • Pick one element to use pivot.
  • partition element into two sub-arrays.
              1. Elements less than or equal to pivot.
            2. Elements greater than pivot.
  • Quick-sort two sub-arrays.
  • Return result.
EXAMPLE

Consider the following example.
        
Pass 1:
      
swap(i,j)
      
swap(i,j)
      
swap (i,j)
      
swap (i,j)
     
'i' and 'j' cross over ,in this type we swap(p,j)  
         
if 'i' >= 'j' then break,
Result of pass 1:Three sub-blocks.
             
    This block of elements are processed in the same fashion and eventually all the elements are placed at appropriate position. Then we get the answer like this.

            

Worst case time complexity[Big-O]:O(n^2)
Best case time complexity[Big-omega]:O(n*log n)
Average time complexity[Big-theta]:O(n*log n)

Advantages:

  • It is one of the fastest sorting algorithm.
  • Its implementation does not require any additional memory.

Disadvantages:

  • The worst case efficiency of O(n^2) is not well suited for large sized list.
  • Its algorithm is considered as a little more complex in comparison to some other sorting technique. 

                                   *****



Saturday, March 16, 2019

MERGE SORT


  • Divide: Partition the n_element sequence to be sorted into 2 sub-sequence of n/2 elements each.
  • Conquer: Sort the two sub-sequence recursively using the merge sort.
  • Combine:Merge the two sorted sub-sequence of size n/2 each to produce the sorted  sequence consisting of n elements.
          Procedure merge-sort(first,last,array)
                 Mid=(first,last)/2;
                 Merge-sort(first,mid,array)
                 Merge-sort(Mid+1,last,array)
                 Rejoin-two-halves(Mid,array)
         End Merge-sort. 

EXAMPLE 

To understand merge sort, we take an unsorted array as the following,
               
We  know that merge sort first divides the whole array iteratively into equal halves .
         
Now we divides these array into two halves.
       
We further divide these arrays and we achieve atomic value which can no more be divided.
Now,we combine them in exactly the same manner as they were broken down.we first compare the element for each list and then combine them into another list in a sorted manner.
In the next iteration of the combining phase,we compare lists of two data values,and merge them into a list of found data values placing all in a sorted order.
After the final merging the list should look like this,

Advantages:

  • It is fast and stable sorting method.
  • It is always ensure an efficiency of  O(nlogn)

Disadvantages:

  • It requires additional memory space to perform sorting .the size of the additional space is in direct proportion to the size of the input list.
  • Even though the number of comparisons made by merge sort are nearly optimal,its performance is slightly lesser than that of quick sort.
                                      *****