Can you please give me answer in java: Create an unsorted array list with 100 ra
ID: 3840760 • Letter: C
Question
Can you please give me answer in java:
Create an unsorted array list with 100 random items in it and then sort it. Count the number of comparisons required to sort it. Do this for bubble sort and quick sort and do each algorithm 10 times, and plot the results on a graph showing how many comparisons are required for each of the sorting algorithms and finally you can answer the original question do the practical results match the theoretical results? Note be specific in your answer, and support your conclusion with the data results you have obtained.
Explanation / Answer
Hi,
Below code can help you count the number of swaps. I could not write code to plot graph in the allocated time. Please find below the answer-
1. Bubble sort swap count program-
public class BubbleSortAlgo<T> implements SearchSortADT<T>
{
//Initialize swap counter
int bubbleSwaps = 0;
public void bubbleSort(T list[], int length)
{
for (int iteration = 1; iteration < length; iteration++)
{
for (int index = 0; index < length - iteration;
index++)
{
Comparable<T> compElem =
(Comparable<T>) list[index];
if (compElem.compareTo(list[index + 1]) > 0)
{
T temp = list[index];
list[index] = list[index + 1];
list[index + 1] = temp;
this.bubbleSwaps++;
}
}
}
}
public int getBubbleSwaps(){
return this.bubbleSwaps;
}
}
public class numberSwapsReview{
public static void main(String [] args)
{
for (int i = 0; i < bubbleArray.length; i++) {
bubbleArray[i] = (int)(Math.random() * 100);
}
BubbleSortAlgo<Integer> sortObject = new BubbleSortAlgo<Integer>();
sortObject.bubbleSort(bubbleArray, 100);
sortObject.getBubbleSwaps();
}
}
2. Quck Sort Algorithm with swap counts-
public void sort() {
sort(this.array, 0, array.length - 1);
}
private void sort(int[] array, int left, int right) {
if(left >= right)
return;
int randomIndex = new Random().nextInt(array.length);
int pivot = array[randomIndex];
int index = partition(array, left, right, pivot);
sort(array, left, index - 1);
sort(array, index, right);
}
private int partition(int[] array, int left, int right, int pivot) {
while(left <= right) {
while(array[left] < pivot)
left++;
while(array[right] > pivot)
right--;
if(left <= right) {
swap(left, right);
left++;
right--;
totalSwaps++;
}
}
return left; // left will be at the partition point
}
class Calculation {
int swaps = 0;
void swap(int[] array, int index1, int index2) {
int temp = array[index1];
array[index1] = array[index2];
array[index2] = temp;
swaps++;
}
void printResult(String label) {
System.out.print(label);
System.out.print(swaps);
}
}
Thanks,
Vinay Singh