Lab 3 part 2 Code

mail@pastecode.io avatar
unknown
plain_text
2 years ago
2.2 kB
3
Indexable
Never
#include "stdio.h"
#include <stdlib.h>



int* generate_random_array(int n)
{
	//create array of n elements
	int* arr=(int*)malloc(n*sizeof(int));
	//int* arr=(int*)calloc(n,sizeof(int));
	
	
	//initialize it with random numbers
	
	int seed =13;
	srandom(seed);
	int i;
	for(i=0;i<n;i++)
	{
		int rnd=(int)random(); //0 -> 2,147,483,648
		rnd=(int)(((double)rnd/(double)RAND_MAX)*100.0);
		arr[i]=rnd;
	}
	
	return arr;
}

int selection_sort(int* arr,int n)
{
	//implement selection sort
	int i;
	//loop to do n searches for the minimum
	for(i=0;i<n;i++)
	{
		//for loop to find the minimum
		int min =arr[i];
		int min_idx=i;
		int j;
		for (j=i;j<n;j++)
		{
			if(min>arr[j])
			{
				min=arr[j];
				min_idx=j;
			}

		}
		//swap the min found with the first element (exchange arr[i] with arr[min_idx]
		int temp=arr[i];
		arr[i]=arr[min_idx];
		arr[min_idx]=temp;		
	}
	
	return 0;
	
}

int binary_search(int* arr,int n,int val)
{
	int idx=-1;
	int start=0;
	int end=n-1;
	
	int middle;
	//keep changing the start and the end variables
	//depending of which part of the array the value might be
	
	for(;;)
	{
		middle=(start+end)/2;
		if(val>arr[middle])
		{
			//we are at the right side of the array
			
			//change the start to be middle
			start=middle;
			
			
			if((end-start<2))
			{
			idx=start;
			return idx;
			}
			
			
		}
		else if(val<arr[middle])
		{
			//we are at the left side of the array
			
			//change the start to be middle
			end=middle;
			
			
			if((end-start<2))
			{
			idx=start;
			return idx;
			}
		}
		else
		{
			val=arr[middle];
			
			idx=middle;
			return idx;
			
		}
	
	}
	return idx;
}


int print_array(int* arr,int n)
{
	int i;
	for (i=0;i<n;i++)
	{
		printf("%d, ",arr[i]);
	}
	printf("\n");
	
	
	return 0;
}


int main()
{
	int n=20;

	int* arr = generate_random_array(n);
	//print the array before sorting  
	print_array(arr,n);
	
	selection_sort(arr,n);
	//print the array after sorting  
	print_array(arr,n);
	
	
	//binary search for a value
	int idx=binary_search(arr,n,64);
	printf("idx= %d\n",idx);
	
	
	

	
}