Searching sorting algorithm

 DATA STRUCTURE

UNIT: - 7

Searching, Sorting and Complexity: -

 Searching

         Sequential Search

         Binary Search

Sorting

         Selection sort

         Bubble sort

         Quick sort

         Merge sort

 

Searching: -

1. Searching algorithms are designed to check for an element or retrieve an element from any data structure where it is stored.

2. Searching is the process of finding some particular element from the list.

3. The search is said to be successful or unsuccessful depending upon whether the element that is being searched is found or not.

4. In this algorithm if the element is found in the list then the process is called successful and the process returns the location of that element, otherwise the search is called unsuccessful.

5. Two popular searching methods that are widely used are: -

a. Sequential search

b. Binary search

 

Sequential Search: -

1. Sequential search is the simplest searching algorithm and also known as linear search.

2. This searching can be applied for both list of item sorted or unsorted.

3. The key which is to be searched is compared with each element of the list one by one.

4. If key is matched with the element then the search is terminated.

5. If the key is not matched with any element from the list then search is failed.

Time Complexity: -

1. The worst case performance of this algorithm is roughly proportional to n and represented as O(n).

2. The best case performance in which the first comparison returns a match it requires a single comparison and hence it is O(1).

3. The average case time depends on the probability that the key will found in the list. The average and worst case is proportional to n hence it is O(n).

Algorithm for sequential search: -

    Linear_search (Array A, value Y)

Step 1: -    for i = 1 to n; (n= number of element in array A)

Step 2: -    if A[i] = Y then go to step 4

Step 3: -    if i>n then go to step 5

Step 4: -    print element found and go to step 6

Step 5: -    print element not found

Step 6: -    Exit

Program Logic: -

        linear_Search(list, value)

             for each item in the list

                 if match item == value

                 return the item found

             end if

        end for

end function linear_search

 

Binary Search: -

1. Binary search tree technique is very fast and efficient.

2. Binary search algorithm applied only for sorted list of element.

3. In Binary search key is compared with the middle element of the given list, if key found search got stop.

4. Binary search followed divide and conquer approach in which the give item list is divide into two half after comparing middle element.

5. If key is not found then the key is searched in two halves depending upon the result produced through the match.

 

Time Complexity: -

1. The worst case performance of this algorithm is roughly proportional to lgn and represented as O(log n).

2. The best case performance in which the first comparison returns a match it requires a single comparison and hence it is O(1).

3. The average case time depends on the probability that the key will found in the list. The average and worst case is proportional to llgn hence it is O(log n).

 

Algorithm for sequential search: -

    Binary_search (Array A, value Y)

Step 1: -    Initialize i as first index and j as last index;

Step 2: -    while i <= j;

Step 3: -    (mid= (i+j)/2)

Step 4: -    if key == arr[mid] go to step 8

Step 5: -    else, compare key with mid is it greater then mid or smaller

Step 6: -    if mid < key, j= mid-1, go to step 2

Step 7: -    else, mid > key, i=mid + 1 go to step 2

Step 8: -    print element found go to step 10

Step 9: -    print element not found

Step 10: -  exit;

Program Logic: -

         binary_Search(arr, i, j, key)

             while(i<=j)

             mid = (i+j)/2;

if (key == arr[mid])

return k; //element found

if (key < arr [mid])

j = k-1;

else

i= k+1;

end while

return -1 //element not found

    end function binary_search

         

 

 Next update will available soon..!!

THANK YOU
Regards,

Diploma students

 

 

 

 

Circular linked list

 

UNIT: - 5 (Part - 2)

    Linked List: -

     Circular linked lists,

     Doubly linked lists

 

Circular Linked List: -

1.     A linked list in which the last node points back to the first node instead of containing NULL pointer is termed as a circular linked list.

 

        

 

Circular linked list have certain advantages over singly lined list.

1.   The first of these is concerned with the accessibility of a node is accessible from a given node.

2.   Deletion of node from a circular linked list is easy.

3.   Operation such as concatenation and splitting the list are more efficient on circular lists.

4.    A circular linked list would more likely to be used in an application which requires round-robbin scheduling or processing.

5.   However there us a disadvantage of circular linked is, if processing without care it is possible to get into infinite loop.

Operation of Circular linked list: -

1. Insertion operation: -

Inserting logic varies depending on where in the list element is going to be inserted, first, middle, or at the end. In all situations it is as simple as making the pointer point to different nodes and hence insertion at any place is must faster.

1. Inserting at beginning: -

Step 1: -  Create a new node using malloc().

Step 2: -  Make the next field of new node point to the node pointed by head.

Step 3: -  Make the head pointer point to new node.

Step 4: -  Make the last node next pointing to the node which is pointed by head. 

 

     

 

1. Inserting at middle: -

Step 1: -       Create a node using malloc() function.

Step 2: -       Point the new node to its successor by making the next field of new node point to the next of predecessor node.

Step 3: -       Make the predecessor node point to new node.

 

 

       

  

1. INSET AT END (After last node): -

Insert in end involves inserting any element at the end of the list.

Step 1: -       Create a node using malloc() function.

Step 2: -       Make the next field of new node point to NULL.

Step 3: -       Make the predecessor node point to new node.

            

 

             

 

 

    Deletion operation: -

Deletion logic varies depending on from where the node is getting deleted from beginning, middle or from the end.     

        1. Delete from beginning (First node): -

 

Step 1: -        Store the node to be deleted in a temporary pointer.

Step 2: -        Make head point to the first nodes successor in the list.

Step 3: -        Make the last node next pointing to the node pointed by head

Step 4: -        Delete the node pointed by temporary pointer. 

 

                                   

 

            

 

 

        2. Delete from middle: -

Step 1: -        Store the node to be deleted in a temporary pointer.

Step 2: -        Make the predecessor node point to the successor of the node being deleted.

Step 3: -        Delete the node pointed by the temporary pointer.

 

               

 

 

        3. Delete last node: -

Step 1: -        Store the node to be deleted in a temporary pointer.

Step 2: -        Move the head  pointer to the predecessor next field of last node.

Step 3: -        Delete the node pointed by temporary pointer.

        

 

 

 NEXT TOPIC DOUBLY LINKED LIST WILL UPLOADED SOON...

PLEASE COMMENT IF YOU LIKE THIS NOTES

THANK YOU