Answer to Question #327858 in C# for madhu

Question

1. Write algorithms/pseudocode on:

• Linear Search
• Binary Search
• Bubble Sort
• Quick Sort

2.After the algorithm/pseudocode ends, provide the time complexity for each of them

Answer 1

1.

Linear Search

public int LinearSearch(int[] arr, int x)
{
   var n = arr.Length;
   for (var i = 0; i < n; i++)
   {
      if (arr[i] == x)
      {
         return i;
      }
   }

   return -1;
}

BinarySearch

public int BinarySearch(int[] arr, int x)
{
   var min = 0;
   var max = arr.Length - 1; 

   while (min <=max)
   {
      var mid = (min + max) / 2;
      if (x == arr[mid])
      {
         return ++mid;
      }
      else if (x < arr[mid])
      {
         max = mid - 1;
      }
      else 
      {
         min = mid + 1;  
      }
   }

   return -1;

}

Bubble Sort

public void BubbleSort(int[] arr)
{
   var n = arr.Length;
   for (var i = 0; i < n - 1; i++)
   {
      for (var j = 0; j < n - i - 1; j++)
      {
         if (arr[j] > arr[j + 1])
         {
            (arr[j], arr[j + 1]) = (arr[j + 1], arr[j]);
         }
      }
   }

}

Quick Sort

public void QuickSort(int[] arr, int left, int right)
{
   if (left >= right)
   {
      return;
   }

   var pivot = QuickSortPartition(arr, left, right);

   if (pivot > 1) {
      QuickSort(arr, left, pivot - 1);
   }
   if (pivot + 1 < right) {
      QuickSort(arr, pivot + 1, right);
   }
}

private int QuickSortPartition(int[] arr, int left, int right)
{
   var pivot = arr[left];
   while (true) 
   {

      while (arr[left] < pivot) 
      {
         left++;
      }

      while (arr[right] > pivot)
      {
         right--;
      }

      if (left < right)
      {
         if (arr[left] == arr[right])
         {
            return right;
         }

         (arr[left], arr[right]) = (arr[right], arr[left]);
      }
      else 
      {
         return right;
      }
   }

}

2.Time complexity

Linear Search - best case -O(1), average(n/2), worst - O(n)

Binary Search - best case -O(1), average/worst cases O(log n)

Bubble Sort - O(n^2)

Linear Sort - best/average case - O(n logn), worst case O(n^2)