Question

**C++ only, use standard library, no vectors

Write a program to generate a list of 5000 random numbers between 1 and 10,000 stored in an array.

Sorts:

Print out the middle 50 numbers of the original list to show the results.

Now sort the original numbers using bubble sort. Print out the number of swaps made.

Now sort the original numbers using selection sort. Print out the number of swaps made.

Now sort the original numbers using insertion sort. Print out the number of swaps made.

Now sort the original numbers using quick sort. Print out the number of swaps made.

       Searches:

             Now you are to search for 2000 different numbers in the array of 5000. You will generate a random number between 1 and 5000 which will be the subscript value to use in the array of 5000.   Select the number at that position (the random number subscript), then call your search routine below and search for that value, counting the number of probes needed to find the value.

Now generate 2000 random number between 1 and 5000, to be search one at a time.

Look up each number using a linear search on the sorted list.

Now generate 2000 random number between 1 and 5000

Look up each number using a binary search on a sorted list.

Determine the average number of probes for each search above.

Do the values represent the theoretical values?
               Print your values and the theoretical values.

Answer 1

1. Random number 1 to 10000 size 5k in array

#include<studio.h>

#include<conio.h>

int main()

{

int arr[5000];
int i;
for (int i = 0; i < 5000; i++)
{
   arr[i]=rand()%10000;
}

}

2. Bubble Sort

// Optimized implementation of Bubble sort
#include <stdio.h>

void swap(int *xp, int *yp)
{
   int temp = *xp;
   *xp = *yp;
   *yp = temp;
}

// An optimized version of Bubble Sort
void bubbleSort(int arr[], int n)
{
int i, j;
bool swapped;

int count=0;
for (i = 0; i < n-1; i++)
{
   swapped = false;
   for (j = 0; j < n-i-1; j++)
   {
       if (arr[j] > arr[j+1])
       {
       swap(&arr[j], &arr[j+1]);
       swapped = true;

count=count+1;
       }
   }

   // IF no two elements were swapped by inner loop, then break
   if (swapped == false)
       break;
}
}

int main()
{
  
   int n = sizeof(arr)/sizeof(arr[0]);
   bubbleSort(arr, n);
   printf("%d ", count);
   return 0;
}

3.Selection Sort
#include <bits/stdc++.h>
using namespace std;

int count=0;

void swap(int *xp, int *yp)
{

count=count+1;
   int temp = *xp;
   *xp = *yp;
   *yp = temp;
}

void selectionSort(int arr[], int n)
{
   int i, j, min_idx;

   // One by one move boundary of unsorted subarray
   for (i = 0; i < n-1; i++)
   {
       // Find the minimum element in unsorted array
       min_idx = i;
       for (j = i+1; j < n; j++)
       if (arr[j] < arr[min_idx])
           min_idx = j;

       // Swap the found minimum element with the first element
       swap(&arr[min_idx], &arr[i]);
   }
}
int main()
{
   int n = sizeof(arr)/sizeof(arr[0]);
   selectionSort(arr, n);
   printf("%d ", count);
   return 0;
}

4.Insertion Sort

#include<iostream>
using namespace std;
int insertionsort(int arr[], int s)
{
   int current,i,j,count=0;
   for(i=1;i<s;i++)
   {
       current=arr[i];
       for(j=i-1;j>=0;j--)
       {
           if(current<arr[j])
           {
               arr[j+1]=arr[j];
               count++;
           }
           else
               break;
       }
       arr[j+1]=current;
   }
   return count;
}
int main()
{
   int t,n,i,res;
   int arr[100000];
   cin>>t;
   while(t--)
   {
       cin>>n;
       for(i=0;i<n;i++)
       {
           cin>>arr[i];
       }
       res=insertionsort(arr,n);
       cout<<res<<endl;
       printf("%d\n",count );
   }
   return 0;
}

5. Quick Sort

void quicksort(int arr[],int first,int last)
{
int pivot,j,temp,i;
int _SwapCount = 0;

if(first<last)
{
pivot=first;
i=first;
j=last;

while(i<j)
{
while(arr[i]<=arr[pivot]&&i<last)
i++;
while(arr[j]>arr[pivot])
j--;
if(i<j)
{
temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}

temp=arr[pivot];
arr[pivot]=arr[j];
arr[j]=temp;
_SwapCount++;
quicksort(arr,first,j-1);
quicksort(arr,j+1,last);

}
}