Searching and Sorting Algorithms

Algorithms for Searching and Sorting elements in an array in C language along with their respective space and time complexities

Searching

1. Linear Search

   Simplest searching Algorithm, each element of the array is iterated one by one until the target element is found

   Worst Case	Average Case	Best Case
   O(n)	O(n)	O(1)

2. Binary Search

   Faster than Linear Search, but works only on sorted arrays

   Worst Case	Average Case	Best Case
   O(log n)	O(log n)	O(1)

Sorting

1. Bubble Sort

   Starts with the first element, if it's bigger than the next element, they are swapped. Repeats loop n times. Simple but has higher time complexity.

   Worst Case	Average Case	Best Case
   O(n²)	O(n²)	O(n)

   In place, O(1) Space complexity

2. Insertion Sort

   For each element in the array, keeps shifting it to the left until a smaller number is encountered. Simple but has higher time complexity.

   Worst Case	Average Case	Best Case
   O(n²)	O(n²)	O(n)

   In place, O(1) Space complexity

3. Selection Sort

   Selects the smallest element in the array and puts it in the first place. In the next iteration, selects the next smallest element and puts it in the second position. Does the same for every element

   Worst Case	Average Case	Best Case
   O(n²)	O(n²)	O(n²)

   In place, O(1) Space complexity

4. Merge Sort

   Keeps dividing the Array; after completely dividing, compares the single elements and merges them into a single sorted array one by one. Faster sorting at the cost of some extra memory.

   Worst Case	Average Case	Best Case
   O( nlogn )	O( nlogn )	O( nlogn )

   O(n) Space Complexity

5. Quick Sort

   Worst Case	Average Case	Best Case
   O(nlogn)	O(nlogn)	O(nlogn)

   In-place, O(1) Space Complexity

6. Heap Sort

   Worst Case	Average Case	Best Case
   O( )	O( )	O( )