DAA
unknown
plain_text
2 years ago
11 kB
4
Indexable
// Binary Search
#include <stdio.h>
int binarySearch(int array[], int x, int low, int high) {
if (high >= low) {
int mid = low + (high - low) / 2;
// If found at mid, then return it
if (array[mid] == x)
return mid;
// Search the left half
if (array[mid] > x)
return binarySearch(array, x, low, mid - 1);
// Search the right half
return binarySearch(array, x, mid + 1, high);
}
return -1;
}
int main(void) {
int array[] = {3, 4, 5, 6, 7, 8, 9};
int n = sizeof(array) / sizeof(array[0]);
int x = 4;
int result = binarySearch(array, x, 0, n - 1);
if (result == -1)
printf("Not found");
else
printf("Element is found at index %d", result);
}
analysis: t(n)=T(n/2)+O(1)=O(log n) bestcase:in middle O(1)
-----------------------------------------------------------------
//sequential search
#include <stdio.h>
#include <conio.h>
main()
{
int arr[]={12,23,78,98,67,56,45,19,65,9},key,i,flag=0;
printf("\nENTER A NUMBER: ");
scanf("%d",&key);
for(i=0;i<10;i++)
{
if(key==arr[i])
flag=1;
}
if(flag==1)
printf("\nTHE NUMBER %d EXISTS IN THE ARRAY",key);
else
printf("\nTHE NUMBER %d DOES NOT EXIST IN THE ARRAY",key);
getch();
}
analysis: t(n)=O(n)
---------------------------------------------------------
/* Bubble sort code */
#include <stdio.h>
int main()
{
int array[100], n, c, d, swap;
printf("Enter number of elements\n");
scanf("%d", &n);
printf("Enter %d integers\n", n);
for (c = 0; c < n; c++)
scanf("%d", &array[c]);
for (c = 0 ; c < n - 1; c++)
{
for (d = 0 ; d < n - c - 1; d++)
{
if (array[d] > array[d+1]) /* For decreasing order use '<' instead of '>' */
{
swap = array[d];
array[d] = array[d+1];
array[d+1] = swap;
}
}
}
printf("Sorted list in ascending order:\n");
for (c = 0; c < n; c++)
printf("%d\n", array[c]);
return 0;
}
analysis: t(n)=(n-1)+(n-2)+...+(n-k)+..+3+2+1 = n(n-1)/2 = O(n^2)
---------------------------------------------------------------------
// Selection sort in C
#include <stdio.h>
// function to swap the the position of two elements
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
void selectionSort(int array[], int size) {
int step, i;
for ( step = 0; step < size - 1; step++) {
int min_idx = step;
for (i = step + 1; i < size; i++) {
// To sort in descending order, change > to < in this line.
// Select the minimum element in each loop.
if (array[i] < array[min_idx])
min_idx = i;
}
// put min at the correct position
swap(&array[min_idx], &array[step]);
}
}
// function to print an array
void printArray(int array[], int size) {
int i;
for (i = 0; i < size; ++i) {
printf("%d ", array[i]);
}
printf("\n");
}
// driver code
int main() {
int data[] = {20, 12, 10, 15, 2};
int size = sizeof(data) / sizeof(data[0]);
selectionSort(data, size);
printf("Sorted array in Acsending Order:\n");
printArray(data, size);
}
analysis: t(n)=(n-1)+(n-2)+...+(n-k)+.. = n(n-1)/2 = O(n^2)
----------------------------------------------------------------------
// Merge sort in C
#include <stdio.h>
// Merge two subarrays L and M into arr
void merge(int arr[], int p, int q, int r) {
int i,j;
// Create L ? A[p..q] and M ? A[q+1..r]
int n1 = q - p + 1;
int n2 = r - q;
int L[n1], M[n2];
for ( i = 0; i < n1; i++)
L[i] = arr[p + i];
for ( j = 0; j < n2; j++)
M[j] = arr[q + 1 + j];
// Maintain current index of sub-arrays and main array
int k;
i = 0;
j = 0;
k = p;
// Until we reach either end of either L or M, pick larger among
// elements L and M and place them in the correct position at A[p..r]
while (i < n1 && j < n2) {
if (L[i] <= M[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = M[j];
j++;
}
k++;
}
// When we run out of elements in either L or M,
// pick up the remaining elements and put in A[p..r]
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = M[j];
j++;
k++;
}
}
// Divide the array into two subarrays, sort them and merge them
void mergeSort(int arr[], int l, int r) {
if (l < r) {
// m is the point where the array is divided into two subarrays
int m = l + (r - l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
// Merge the sorted subarrays
merge(arr, l, m, r);
}
}
// Print the array
void printArray(int arr[], int size) {
int i;
for ( i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
// Driver program
int main() {
int arr[] = {6, 5, 12, 10, 9, 1};
int size = sizeof(arr) / sizeof(arr[0]);
mergeSort(arr, 0, size - 1);
printf("Sorted array: \n");
printArray(arr, size);
}
analysis: 2 subproblems each n/2,dividecost=const,mergingcost=n,recurrence relation:t(n)=2T(n/2)+O(n)
solving:T(n)=O(nlogn)
space=O(n)
--------------------------------------------------------------------
// Quick sort in C
#include <stdio.h>
// function to swap elements
void swap(int *a, int *b) {
int t = *a;
*a = *b;
*b = t;
}
// function to find the partition position
int partition(int array[], int low, int high) {
// select the rightmost element as pivot
int pivot = array[high];
// pointer for greater element
int i = (low - 1);
int j;
// traverse each element of the array
// compare them with the pivot
for (j = low; j < high; j++) {
if (array[j] <= pivot) {
// if element smaller than pivot is found
// swap it with the greater element pointed by i
i++;
// swap element at i with element at j
swap(&array[i], &array[j]);
}
}
// swap the pivot element with the greater element at i
swap(&array[i + 1], &array[high]);
// return the partition point
return (i + 1);
}
void quickSort(int array[], int low, int high) {
if (low < high) {
// find the pivot element such that
// elements smaller than pivot are on left of pivot
// elements greater than pivot are on right of pivot
int pi = partition(array, low, high);
// recursive call on the left of pivot
quickSort(array, low, pi - 1);
// recursive call on the right of pivot
quickSort(array, pi + 1, high);
}
}
// function to print array elements
void printArray(int array[], int size) {
int i;
for ( i = 0; i < size; ++i) {
printf("%d ", array[i]);
}
printf("\n");
}
// main function
int main() {
int data[] = {8, 7, 2, 1, 0, 9, 6};
int n = sizeof(data) / sizeof(data[0]);
printf("Unsorted Array\n");
printArray(data, n);
// perform quicksort on data
quickSort(data, 0, n - 1);
printf("Sorted array in ascending order: \n");
printArray(data, n);
}
analysis:
Worst Case: T(n) = T(n-1) + O(n)=O(n^2)
Best Case: T(n) = 2T(n/2) + O(n) = O(nlogn)
space=O(logn)
-----------------------------------------------------------------------
// Heap Sort in C
#include <stdio.h>
// Function to swap the the position of two elements
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
void heapify(int arr[], int n, int i) {
// Find largest among root, left child and right child
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest])
largest = left;
if (right < n && arr[right] > arr[largest])
largest = right;
// Swap and continue heapifying if root is not largest
if (largest != i) {
swap(&arr[i], &arr[largest]);
heapify(arr, n, largest);
}
}
// Main function to do heap sort
void heapSort(int arr[], int n) {
// Build max heap
int i;
for ( i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
// Heap sort
for ( i = n - 1; i >= 0; i--) {
swap(&arr[0], &arr[i]);
// Heapify root element to get highest element at root again
heapify(arr, i, 0);
}
}
// Print an array
void printArray(int arr[], int n) {
int i;
for ( i = 0; i < n; ++i)
printf("%d ", arr[i]);
printf("\n");
}
// Driver code
int main() {
int arr[] = {1, 12, 9, 5, 6, 10};
int n = sizeof(arr) / sizeof(arr[0]);
heapSort(arr, n);
printf("Sorted array is \n");
printArray(arr, n);
}
analysis: O(n) for heapbuild, For loop executes O(n), Heapyfy O(logn)
t(n)=O(n log n)
----------------------------------------------------------------------------------
// jobsequencing
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
// A structure to represent a job
typedef struct Job {
char id; // Job Id
int dead; // Deadline of job
int profit; // Profit if job is over before or on
// deadline
} Job;
// This function is used for sorting all jobs according to
// profit
int compare(const void* a, const void* b)
{
Job* temp1 = (Job*)a;
Job* temp2 = (Job*)b;
return (temp2->profit - temp1->profit);
}
// Find minimum between two numbers.
int min(int num1, int num2)
{
return (num1 > num2) ? num2 : num1;
}
// Returns maximum profit from jobs
void printJobScheduling(Job arr[], int n)
{
// Sort all jobs according to decreasing order of profit
qsort(arr, n, sizeof(Job), compare);
int result[n],i,j; // To store result (Sequence of jobs)
bool slot[n]; // To keep track of free time slots
// Initialize all slots to be free
for ( i = 0; i < n; i++)
slot[i] = false;
// Iterate through all given jobs
for ( i = 0; i < n; i++) {
// Find a free slot for this job (Note that we start
// from the last possible slot)
for ( j = min(n, arr[i].dead) - 1; j >= 0; j--) {
// Free slot found
if (slot[j] == false) {
result[j] = i; // Add this job to result
slot[j] = true; // Make this slot occupied
break;
}
}
}
// Print the result
for ( i = 0; i < n; i++)
if (slot[i])
printf("%c ", arr[result[i]].id);
}
// Driver's code
int main()
{
Job arr[] = { { 'a', 2, 100 },
{ 'b', 1, 19 },
{ 'c', 2, 27 },
{ 'd', 1, 25 },
{ 'e', 3, 15 } };
int n = sizeof(arr) / sizeof(arr[0]);
printf(
"Following is maximum profit sequence of jobs \n");
// Function call
printJobScheduling(arr, n);
return 0;
}
analysis: sorting requires O(nlogn), 2 loops O(n^2)
T(n)=O(nlogn)+O(n^2)=O(n^2)