Scribd
Upload
2 views

1. Write a C Program to Implement Linear Search.--...

The document provides C programs for implementing linear search, binary search, and various sorting algorithms including selection sort, quick sort, and insertion sort. It explains the characteristics and use cases of linear and binary search techniques, as well as the time complexities of the sorting algorithms. Additionally, it includes example code for each algorithm and emphasizes the importance of including a main function for testing.

Uploaded by

kodurisaikiran1437
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
2 views

1. Write a C Program to Implement Linear Search.--...

The document provides C programs for implementing linear search, binary search, and various sorting algorithms including selection sort, quick sort, and insertion sort. It explains the characteristics and use cases of linear and binary search techniques, as well as the time complexities of the sorting algorithms. Additionally, it includes example code for each algorithm and emphasizes the importance of including a main function for testing.

Uploaded by

kodurisaikiran1437
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 4

Certainly, here are the C programs and explanations to help you with your micro-slip:

1. C Program to Implement Linear Search:


#include <stdio.h>

int linearSearch(int arr[], int size, int key) {


for (int i = 0; i < size; i++) {
if (arr[i] == key) {
return i; // Return the index if found
}
}
return -1; // Return -1 if not found
}

int main() {
int arr[] = {10, 5, 20, 8, 15};
int size = sizeof(arr) / sizeof(arr[0]);
int key = 20;

int result = linearSearch(arr, size, key);

if (result != -1) {
printf("Element found at index: %d\n", result);
} else {
printf("Element not found.\n");
}

return 0;
}

2. Choosing a Search Technique:


● Linear Search:
○ Simple to implement.
○ Suitable for unsorted arrays or when the array is small.
● Binary Search:
○ More efficient than linear search for sorted arrays.
○ Requires the array to be sorted.
Algorithm for Binary Search (Example):
1. Given array: 8, 22, 37, 49, 81, 99, 105, 113
2. Search for: 100
3. Find the middle element: (0 + 7) / 2 = 3 (index of 49)
4. Compare 100 with 49: 100 > 49
5. Search the right half: 81, 99, 105, 113
6. Find the middle element: (4 + 7) / 2 = 5 (index of 99)
7. Compare 100 with 99: 100 > 99
8. Search the right half: 105, 113
9. Find the middle element: (6 + 7) / 2 = 6 (index of 105)
10. Compare 100 with 105: 100 < 105
11. Search the left half: 105 (only one element)
12. Compare 100 with 105: 100 < 105
13. Element not found.
3. Sorting and Sorting Algorithms:
● Sorting: Arranging elements of a list in a specific order (e.g., ascending or descending).
● a) Selection Sort:
#include <stdio.h>

void selectionSort(int arr[], int n) {


for (int i = 0; i < n - 1; i++) {
int min_idx = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[min_idx]) {
min_idx = j;
}
}
// Swap the found minimum element with the first element
int temp = arr[i];
arr[i] = arr[min_idx];
arr[min_idx] = temp;
}
}

// ... (main function to test) ...

● b) Quick Sort:
#include <stdio.h>

int partition(int arr[], int low, int high) {


int pivot = arr[high]; // pivot
int i = (low - 1); // Index of smaller element

for (int j = low; j <= high - 1; j++) {


// If current element is smaller than or equal to pivot
if (arr[j] <= pivot) {
i++; // increment index of smaller element
// swap arr[i] and arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// swap arr[i+1] and arr[high] (or pivot)
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;

return (i + 1);
}

void quickSort(int arr[], int low, int high) {


if (low < high) {
/* pi is partitioning index, arr[p] is now
at right place */
int pi = partition(arr, low, high);
// Separately sort elements before
// partition and after partition
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}

// ... (main function to test) ...

● c) Insertion Sort:
#include <stdio.h>

void insertionSort(int arr[], int n) {


for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;

/* Move elements of arr[0..i-1], that are


greater than key, to one position ahead
of their current position */
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}

// ... (main function to test) ...

4. Recursive Search (Example: Binary Search)


● Recursive Binary Search:
#include <stdio.h>

int binarySearchRecursive(int arr[], int l, int r, int x) {


if (r >= l) {
int mid = l + (r - l) / 2;

// If the element is present at the middle


if (arr[mid] == x) {
return mid;
}

// If element is smaller than mid, then it can only


// be present in left subarray
if (arr[mid] > x) {
return binarySearchRecursive(arr, l, mid - 1, x);
}

// Else the element can only be present in right subarray


return binarySearchRecursive(arr, mid + 1, r, x);
}

// We reach here when the element is not present


// in array
return -1;
}

// ... (main function to test) ...

5. Running Time Complexity of Sorting Algorithms:


● Selection Sort: O(n^2)
● Quick Sort: O(n log n) (average case), O(n^2) (worst case)
● Insertion Sort: O(n^2) (average and worst case), O(n) (best case)
6. Sorting Algorithms with Functions (Implemented above)
● Selection Sort: selectionSort(int arr[], int n)
● Quick Sort: quickSort(int arr[], int low, int high)
● Insertion Sort: insertionSort(int arr[], int n)
Note:
● Please include the main() function in each of the sorting programs to test the
implementations.
● Remember to include appropriate header files (stdio.h) in each program.

You might also like