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                                                           

                        

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.

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.

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. 

                                   *****

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.

                                      *****

BUBBLE SORT

• A bubble sort compares adjacent array elements and exchange their value if they are out of order.
• It focuses on bringing the largest element to the end of the list with each successive pass.

EXAMPLE
  We take an unsorted array for our example. 
                         
      First pass,

         Second pass,

        Third pass,

        Fourth pass,

• Four passes were required to sort a list of 5 elements hence,we can says that bubble sort requires n-1 passes to sort an array of 'n' elements.
• Unlike selection sort it does not perform a search to identify the largest element,instead it repeatedly compares two consecutive elements & moves the largest amongst them to right.
• This process is repeated for all pairs of elements until the current iteration moves the largest elements element to the end of the list.

Efficiency of bubble sort: 

      Assume that an array containing n elements is sorted using bubble sort technique.

  No.of comparisons made in 1st pass=n-1

  No.of comparisons made in 2nd pass=n-2

  No.of comparisons made in last pass=1

Total no.of comparisons made

                           =(n-1)+(n-2)+....+1

                           =n*(n-1)/2

Efficiency of bubble sort=O(n^2)

Advantages:

• It is easy to understand and implement.
• It leverage the presence of any existing sort pattern in the list, thus resulting in better efficiency.

Disadvantages:

• The efficiency of O(n^2) is not well suited for large sized lists.
• It requires large number of elements to be shifted.
• It is slow in execution as large elements are moved elements towards the end of the list in a step_by_step fashion.

                                             *******     

               

SHELL SORT

• Shell sort works by comparing elements that are distant rather than adjacent element in an array (or) list where adjacent elements are compared.
• Shell sort uses an increment sequence.
• The increment size is reduced after each pass until the increment size is 1.

 EXAMPLE
        

• n=length of the list=8
• Increment=n/2=8/2=4

Initial segmenting gap=4

We take the interval of 4.Make a virtual sub_list of all values located at the interval of 4 positions.Here these values are {18,38},{32,33},{12,16}and{5,2). 

We compare values in each sub_list and swap them in the original array.

Resegmenting gap=2

Then,we take interval of 2 and this gap generates two sub_lists {18,12,38,16},{32,2,33,5}.

We compare and swap the values,

Resegmenting gap=1

Finally,we sort the rest of the array using interval of value 1.Shell sort  uses insertion sort to sort the array.

after the insertion sort we get the answer like this,

Shellsort Best case:

• The best case in the shell sort is when the array is already sorted in the right order.the no.of comparisons is less.

Shellsort worst case:

• The running time of shellsort depends on the choice of increment sequence.
• The problem with shell's increments is that pairs of increments are not necessarily relatively prime and smaller increments can have little effect.

Advantages:

• It's only efficient for medium size lists.For bigger lists, the algorithm is not the best choice.
• 5 times faster than the bubble sort & a litter over twice as fast as the insertion  sort.

Disadvantages:

• It is a complex algorithm & its not nearly as efficient as the merge,heap & quick sort.
• The shell sort is still significantly slower than the merge,heap & quick sorts.

        Also Refer INSERTION SORT                       

                                  ******

SELECTION SORT

• The idea of selection sort is rather simple, It basically determines the minimum (or) maximum of the list and swaps it with the element at the index where it supposed to be. The process is repeated such that the n minimum  (or) maximum element is swapped with the element at the n-1 index of the list.
• The principle of selection sort is different .if the array contains 'n' element is compared with the remaining (n-1) elements & which is the lower element, place that element in the first position .continue this process until all the elements in an array are sorted.  

EXAMPLE
      Consider the following array as an example.   
                       
For the first position in the sorted list,the whole list is scanned sequentially.The first position 24 is stored presently,we search the whole list and find that 8 is the lowest value. 
                       
So replace 8 with 23.after one iteration 8 which happens to be the minimum value in the list appears in the first position of the sorted list.
                
For the second position where 75 is residing we start scanning the rest of the list in a linear manner.we find 23 is the second lowest value in the list.
               
After two iterations two least values are positioned at the beginning in a sorted manner.
                
For the third position where 44 is residing we start scanning the rest of the list in a linear manner.we find 34 is the third lowest value in the list.
                
So replace 34 with 44.
               
The same process is applied to the rest of the item in the array.
                
Finally replace 44 with 75.we get the sorted list.
                

Efficiency of selection sort:

 Assume that an array containing 'n' elements is sorted using selection sort technique.

Now,

  The no.of comparisons made during first pass=n-1.

  No.of comparisons made during second pass=n-2.

  No.of comparisons made during last pass=1.

Total no.of comparisons=(n-1)+(n-2)+....+1

                                         =n*(n-1)/2

                                         =O(n^2)

Thus, efficiency of selection sort=O(n^2)

Advantages:

• It is one of the important simplest sorting technique.
• It is easy to understand and implement.
• It performs well in case of smaller list.
• It does not require additional memory.

Disadvantages:

• The efficiency of O(n^2) is not well suited for large sized list.
• It does not leverage the presence of any existing sort pattern in the list.

                             *****