Data Structure and Algorithm: Searching and Sorting

Searching and Sorting

1. Searching & Sorting

2. Linear Search is the simplest search algorithm used to find a particular element in a list or array by checking each element one by one until the desired element is found or the end is reached. When to Use: The list is unsorted The list is small Algorithm Steps: Start from the first element . Compare each element with the target value . If a match is found, return the index . If the end is reached without finding the element, return -1 (or indicate "not found"). Linear Search

3. #include < stdio.h > int linearSearch ( int arr [], int n, int key) { for ( int i = 0; i < n; i ++) { if ( arr [ i ] == key) return i ; // return index } return -1; // not found } Linear Search int main() { int arr [] = {10, 25, 30, 45, 50}; int n = sizeof ( arr ) / sizeof ( arr [0]); int key = 30; int result = linearSearch ( arr , n, key); if (result != -1) printf ("Element found at index %d\n", result); else printf ("Element not found\n"); return 0; }

4. Case Time Complexity Best Case O(1) (element at the start) Average O(n) Worst Case O(n) (element at the end or not present) Space Complexity: O(1) — uses constant memory

5. Binary Search Binary Search is an efficient algorithm for finding an element in a sorted array by repeatedly dividing the search interval in half .

6. #include < stdio.h > int binarySearch ( int arr [], int low, int high, int key) { while (low <= high) { int mid = (low + high) / 2; if ( arr [mid] == key) return mid; else if ( arr [mid] < key) low = mid + 1; else high = mid - 1; } return -1; // not found } int main() { int arr [] = {10, 20, 30, 40, 50}; int n = sizeof ( arr ) / sizeof ( arr [0]); int key = 40; int result = binarySearch ( arr , 0, n - 1, key); if (result != -1) printf ("Element found at index %d\n", result); else printf ("Element not found\n"); return 0; } Binary Search

7. Case Time Complexity Best Case O(1) Average O(log n) Worst Case O(log n)

8. Bubble Sort Bubble Sort  is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in the wrong order. This algorithm is not suitable for large data sets as its average and worst-case time complexity are quite high . We sort the array using multiple passes. After the first pass, the maximum element goes to end (its correct position ). Same way, after second pass, the second largest element goes to second last position and so on.

9. Example

10. Complexity Analysis of Bubble Sort: Time Complexity:  O(n 2 ) [( n(n-1))/ 2] Auxiliary Space:  O(1 ) Advantages of Bubble Sort: Bubble sort is easy to understand and implement. It does not require any additional memory space . Disadvantages of Bubble Sort: Bubble sort has a time complexity of O(n 2 ) which makes it very slow for large data sets. Bubble sort has almost no or limited real world applications. 

11. #include < stdio.h > void bubbleSort ( int arr [], int n) { int i , j, temp; for ( i = 0; i < n - 1; i ++) { // Outer loop for passes for (j = 0; j < n - i - 1; j++ ) { // Inner loop for comparisons if ( arr [j] > arr [j + 1]) { // Swap if elements are in wrong order temp = arr [j]; arr [j] = arr [j + 1]; arr [j + 1] = temp; } } } } int main() { int arr [100], n, i ; // Input size of array printf ("Enter number of elements: "); scanf ("%d", &n); // Input array elements printf ("Enter %d elements: ", n); for ( i = 0; i < n; i ++) { scanf ("%d", & arr [ i ]); } bubbleSort ( arr , n ); // Call bubble sort function printf ("Sorted array: "); // Display sorted array for ( i = 0; i < n; i ++) { printf ("%d ", arr [ i ]); } return 0; } Bubble Sort

12. Insertion Sort Insertion sort  is a simple sorting algorithm that works by iteratively inserting each element of an unsorted list into its correct position in a sorted portion of the list . It is like sorting playing cards in your hands. You split the cards into two groups: the sorted cards and the unsorted cards. Then, you pick a card from the unsorted group and put it in the right place in the sorted group. We start with the second element of the array as the first element is assumed to be sorted. Compare the second element with the first element if the second element is smaller then swap them. Move to the third element, compare it with the first two elements, and put it in its correct position Repeat until the entire array is sorted.

13. Complexity Analysis of Insertion Sort: Time Complexity:  O(n 2 ) Auxiliary Space:  O(1) Advantages of Insertion Sort: Simple and easy to implement. Stable  sorting algorithm. Efficient for small lists and nearly sorted lists. Space-efficient as it is an in-place algorithm. Disadvantages of Insertion Sort: Inefficient for large lists.

14. # include < stdio.h > void insertionSort ( int a[], int n) { for ( int i = 1; i < n; i ++) { int key = a[ i ]; int j = i - 1; // Move elements greater than key to one position ahead while (j >= 0 && a[j] > key) { a[j + 1] = a[j]; j--; } a[j + 1] = key; } } Insertion Sort int main() { int a[] = {5, 3, 8, 4, 2}; int n = 5; insertionSort (a, n); printf ("Sorted array: "); for ( int i = 0; i < n; i ++) printf ("%d ", a[ i ]); return 0; }

15. Selection Sort Selection Sort  is a comparison-based sorting algorithm. It sorts an array by repeatedly selecting the  smallest  element from the unsorted portion and swapping it with the first unsorted element. This process continues until the entire array is sorted. First we find the smallest element and swap it with the first element. This way we get the smallest element at its correct position. Then we find the smallest among remaining elements (or second smallest) and swap it with the second element. We keep doing this until we get all elements moved to correct position.

16. Time Complexity: O(n 2 )  ,as there are two nested loops. Auxiliary Space:  O(1) as the only extra memory used is for temporary variables . Easy to understand and implement, making it ideal for teaching basic sorting concepts. Requires only a constant O(1) extra memory space . Selection sort has a time complexity of O(n 2 ) makes it slower compared to algorithms like  Quick Sort  or  Merge Sort .

17. #include < stdio.h > void selectionSort ( int arr [], int n) { int i , j, min_idx , temp ; // Move the boundary of the unsorted subarray one by one for ( i = 0; i < n - 1; i ++) { // Assume the current index is the minimum min_idx = i ; // Find the index of the minimum element in the remaining array for (j = i + 1; j < n; j++ ) { if ( arr [j] < arr [ min_idx ]) min_idx = j; } // Swap the found minimum with the current element temp = arr [ min_idx ]; arr [ min_idx ] = arr [ i ]; arr [ i ] = temp; }} // Function to print the array void printArray ( int arr [], int n) { int i ; for ( i = 0; i < n; i ++) printf ("%d ", arr [ i ]); printf ("\n"); } // Main function int main() { int arr [] = {64, 25, 12, 22, 11}; int n = sizeof ( arr ) / sizeof ( arr [0]); printf ("Original array: "); printArray ( arr , n); selectionSort ( arr , n); printf ("Sorted array: "); printArray ( arr , n); return 0; }

18. Merge Sort Merge sort  is a popular sorting algorithm known for its efficiency and stability. It follows the  divide-and-conquer  approach. It works by recursively dividing the input array into two halves, recursively sorting the two halves and finally merging them back together to obtain the sorted array . Time Complexity: Best Case:  O(n log n), When the array is already sorted or nearly sorted. Average Case:  O(n log n), When the array is randomly ordered. Worst Case:  O(n log n), When the array is sorted in reverse order. Auxiliary Space:  O(n), Additional space is required for the temporary array used during merging.

19. #include < stdio.h > // Function to merge two subarrays void merge( int arr [], int left, int mid, int right) { int i , j, k; int n1 = mid - left + 1; // Size of left subarray int n2 = right - mid; // Size of right subarray // Create temporary arrays int L[n1], R[n2]; // Copy data to temp arrays for ( i = 0; i < n1; i ++) L[ i ] = arr [left + i ]; for (j = 0; j < n2; j++ ) R[j] = arr [mid + 1 + j]; // Merge the temp arrays back into arr [ left..right ] i = 0; // Initial index of first subarray j = 0; // Initial index of second subarray k = left; // Initial index of merged array while ( i < n1 && j < n2 ) { if (L[ i ] <= R[j]) { arr [k] = L[ i ]; i ++; } else { arr [k] = R[j]; j++ ; } k++; } Merge Sort

20. while ( i < n1) { // Copy remaining elements of L[], if any arr [k] = L[ i ]; i ++; k++; } while (j < n2) { // Copy remaining elements of R[], if any arr [k] = R[j]; j++ ; k++; }} void mergeSort ( int arr [], int left, int right) { if (left < right) { int mid = left + (right - left) / 2 ; mergeSort ( arr , left, mid ); // Sort first and second halves mergeSort ( arr , mid + 1, right ); merge( arr , left, mid, right ); // Merge the sorted halves }} // Function to print the array void printArray ( int arr [], int size) { for ( int i = 0; i < size; i ++) printf ("%d ", arr [ i ]); printf ("\n"); } // Main function int main() { int arr [] = {38, 27, 43, 3, 9, 82, 10}; int size = sizeof ( arr ) / sizeof ( arr [0]); printf ("Original array:\n"); printArray ( arr , size); mergeSort ( arr , 0, size - 1); printf ("Sorted array:\n"); printArray ( arr , size); return 0; }

21. Quick Sort Quick sort is a well-known sorting algorithm. It is highly efficient and also known as partition exchange sort. In this sorting algorithm the array is divided into 2 sub array. One contain smaller values than pivot value and other array contain elements having greater values than pivot value. Pivot is an element that is used to compare and divide the elements of the main array into two. Quick sort partitions an array and then calls itself recursively twice to sort the two resulting sub arrays. This algorithm is quite efficient for large data sets. The Average and best time complexity are of this algorithm is Ο( nlogn ), where n is the number of items.

22. How does QuickSort Algorithm work? There are mainly three steps in the algorithm. 1. Choose a pivot 2. Partition the array around pivot. After partition, it is ensured that all elements are smaller than all right and we get index of the end point of smaller elements. The left and right may not be sorted individually. 3. Recursively call for the two partitioned left and right subarrays. 4. We stop recursion when there is only one element is left.

23. void quickSort ( int a[], int low, int high) { if (low < high) { int p = partition(a, low, high); quickSort (a, low, p - 1); quickSort (a, p + 1, high); } } int main() { int a[] = {5, 3, 8, 4, 2}; int n = 5; quickSort (a, 0, n - 1); printf ("Sorted array: "); for ( int i = 0; i < n; i ++) printf ("%d ", a[ i ]); return 0; } #include < stdio.h > int partition( int a[], int low, int high) { int pivot = a[high]; int i = low - 1, temp; for ( int j = low; j < high; j++ ) { if (a[j] < pivot) { i ++; temp = a[ i ]; a[ i ] = a[j]; a[j] = temp; } } temp = a[ i + 1]; a[ i + 1] = a[high]; a[high] = temp; return i + 1; }

24. Time Complexity: Best Case : Θ( n log2 n) Average Case: Θ( n log2 n) Worst Case : O(n2) Advantages of Quick Sort: It is a divide-and-conquer algorithm that makes it easier to solve problems. It is efficient on large data sets. It has a low overhead, as it only requires a small amount of memory to function.

25. Linear Search

26. Binary Search

27. Binary Search

28. Bubble Sort

29. Insertion Sort

30. Selection Sort

31. Merge Sort

32. Quick Sort