uestion 2: Search and Sort Properties Can you perform a sequential search on eac

Question

uestion 2: Search and Sort Properties Can you perform a sequential search on each of the following? What about a binary search? unsorted array, sorted array, unsorted linked list, sorted linked list What is the efficiency (big-oh) of sequential search? binary search? What are the big-ohs of merge sort, quick sort, and radix sort? How do these compare to the big-oh of insertion sort, selection sort, and Shell sort? In quick sort, what is true about the array after a single pass of the partition method?

Explanation / Answer

Sequential search

.........................................

1) Unsorted array : -

..............................

template <class S>
int sequential_search(S arr[], int size_of_arr, const S& Element_to_search)
   {
   int k;

   for (k = 0; k < size; k++)
      if (Element_to_search == arr[k])
         return k;

   return NO;
   }

...........................................................................................................................................

Sorted array:-

........................

template <class S>
int sequential_search(S arr[], int size_of_arr, const S& Element_to_search)
   {
   int k;

   for (k = 0;Element_to_search <= arr[k]; k++)
    if ( Element_to_search == arr[k])
             return i;

      return NO;
   }

....................................................................................................................

Unsorted linked list

.....................................

template <class S>
LNode<S>* List<S>::sequential_search(const S& ELement_to_search) const
   {
   LNode<S>* cur;

   for (cur = 1; cur != NULL; cur = cur->next)
      if (ELement_to_search == cur->data)
         return cur;

   return NULL;
   }

..................................................................................................................................

Sorted linked list

........................

template <class S>
LNode<S>* List<S>::sequential_search(const S& ELement_to_search) const
   {
   LNode<S>* cur;

   for (cur = 1; Element_to_search <= cur->data;cur = cur->next)
      if (ELement_to_search == cur->data)
         return cur;

   return NULL;
   }

..............................................................................................................................................

Binary search

..................................................................

Unsorted array

...............................

For Binary search in Unsorted array, first sort the array and then you can applied the binary search in sorted array which I implemented below.

..............................................................................................................................

Sorted array:-

............................

int binary_search(int unsorted_arr[],int size_of_unsorted_arr,int Element_to_search)
{
   int f = 0,l = size_of_unsorted_arr - 1, mid, pos = -1;
   bool k = false;
  
   while( (!k) && (f <= l) )    
   {
       mid = (f + l) / 2;
       if (unsorted_arr[mid] == Element_to_search)    
       {
       k = true;
       pos = mid;
       return pos;
       }
       else if (unsorted_arr[mid] > Element_to_search)  
           l = mid - 1;
       else
           f = mid - 1;              
   }
   return NO;
}

....................................................................................................................................

Unsorted and Sorted linked list

...........................................................

It is not good to use the binary search on sorted and unsorted linked list.The main purpose of binary search is to reduce the searching in half time. But in linked list it will traverse half of the list to find middle element and then does the comparison which will consume the time.So, according to me binary search is not good and cannot be applied for linked list.

..................................................................................................................................

Efficiency of binary search and sequential search:-

..................................................................................

.................................................................................................................................................

Big-ohs of merge sort, quick sort, and radix sort

...........................................................................

NOTE:- k is the size of key and d is the size of digit

..............................................................................................................................................................

Comparison of merge sort, quick sort, and radix sort, insertion sort, selection sort, and Shell sort

..................................................................................................................................................

..............................................................................................................................................

Array after a single pass of the partition method in quick sort:-

.........................................................................................

In quick sort, initially one element is picked in array generally the first one, which will be called as pivot. After one pass in the partition method, the pivot will get its proper place and the entries left to pivot are smaller than pivot and the right enteries to pivot are larger than pivot.

Efficiency Sequential Binary Unsorted array O(N) O(N) Sorted array O(N) O(LOG N) Unsorted linked list O(N) O(N) Sorted linked list O(N) O(N)

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.