Need code in Java, please! Description: (Using The Module Two Readings) One of t
ID: 3720332 • Letter: N
Question
Need code in Java, please!
Description: (Using The Module Two Readings) One of the points we made in Module 2 was that the different sorts can have different efficiencies/complexities. This is in contrast to binary search, which we can expect to work in approximately O(log2 n) of the size n of the sorted list. In other classes you can get into the theoretical elements of the computational complexity of sorting. Here we will look at it experimentally We wil look at the behavior of two different sorts on randomly generated lists of different sizes .The two sorts are bubblesort and quicksort. Randomly generate integers in the range 0-99 for your random numbers. You may choose your own random number generation technique. You must document the source of your random number generation in the code. Here is what your code should do: 1. Do this 10 times: a. Generate a random list of 100 items b. Have each algorithm sort the list. c. Give the original list, the sorted list, and the number of comparisons done by each algorithm 2. At the end: For each algorithm and each list length give the average of the number of comparisons a.Explanation / Answer
#include <stdio.h>
#include <stdlib.h>
int main()
{
int list[100],num,k,len;
int bCount=0, qCount=0;
int bCompareArr[10], qCompareArr[10];
len = sizeof(list)/sizeof(list[0]);
for(k=0;k < 10; k++)
{
printf(" Array List: %d ",k);
for (i = 0; i < 100; i++)
{
int num = (rand() + 0) % (99 + 1);
list[i] = num
}
bCount = BubbleSort(list, len);
bCompareArr[k] = bCount;
printf("Comparisions required for Bubble sort=%d",bCount);
printf(" Quick SOrt Original Array ");
for (i=0; i < len; i++)
printf("%d ", list[i]);
qCount = QuickSort(list, 0, len-1);
printf("Comparisions required for Quick sort=%d",bCount);
qCompareArr[k] = qCount;
printf(" ---------------------------------------- ");
}
for(k=0;k < 10; k++)
{
printf(" For Bubble sort, Average comparision needed to sort list %d is %f ",k,(bCompareArr[k]/100));
printf(" For Quick sort, Average comparision needed to sort list %d is %f ",k,(qCompareArr[k]/100));
}
return 0;
}
int BubbleSort(int arr[], int len)
{
int i, j, comparisionCount=0;
printf(" Bubble Sort Original Array ");
for (i=0; i < len; i++)
printf("%d ", arr[i]);
for (i = 0; i < len-1; i++)
{
for (j = 0; j < len-i-1; j++)
{
comparisionCount++;
if (arr[j] > arr[j+1])
{
temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
}
printf(" Sorted Array ");
for (i=0; i < len; i++)
printf("%d ", arr[i]);
return comparisionCount;
}
int Partition(int arr[],int low,int high)
{
int p = arr[high],j,temp;
int i = low-1;
for(j = low;j <= high -1;j++){
if(arr[j] <= p)
{
i++;
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
temp = arr[i+1];
arr[i+1] = arr[high];
arr[high]= temp;
return i+1;
}
int QuickSort(int arr[],int startPos,int length)
{
int pivot,i, comparisionCount;
static int tempCount=0;
if (startPos < length)
{
tempCount++;
Pivot = partition(arr, low, high);
QuickSort(arr, startPos, pivot - 1);
QuickSort(arr, pivot + 1, length);
}
comparisionCount = tempCount;
tempCount = 0;
printf(" Sorted Array ");
for (i=0; i < size; i++)
printf("%d ", arr[i]);
return comparisionCount;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.