Complexity analysis has a number of limitations. For example, big-O...

Complexity analysis has a number of limitations. For example, big-Oh analysis concerns the worst case scenario. For example, some sorting algorithms with a complexity of O(n²) often run considerably faster if the list that it receives as input is (almost) sorted; other sorting algorithms with a complexity of O(n²) always take the same amount of time, no matter what state the list is in. Also, in big-Oh, we look at the dominant term in out calculation of the complexity of the algorithm. Thus, when we analyze an algorithm and discover that it runs in 75,312 + n time units, we still say that it has a complexity of O(n). It is therefore deemed to be better than an algorithm that run in .007 + n² time units, as this algorithm has a complexity of O(n²). We also saw the rationale behind this: If n becomes sufficiently large, the other factors become insignificant.

Fortunately, there is another way to determine how long it takes for an algorithm to run, namely timing experiments. In a timing experiment, you actually implement the algorithm in a programming language, such as Java or C++, and simply measure how long it takes for the algorithm to run.

In the term project for this course, you are going to conduct a timing experiment and compare the results with the results you would get from a complexity analysis. We will compare bubble sort, which has a complexity of O(n²), with quick sort, which has a complexity of O(nlog(n)).

Assuming that the list contains n elements.
Compare the first and the second element in the list, and swap them if the last element is smaller than the preceding one; otherwise, do nothing to this pair.
Now, compare second and third element t and swap them if the first of them is larger than the second; otherwise, do nothing to this pair.
Move on the next pair and continue the process until you reach the end of the list.
A little reflection will show that at the end of this iteration, the last element in the list is now the largest element in the list. The last element has bubbled to the top.
Now repeat the process but rather than going to the end of the list, stop when you reach n-1.
Now repeat the process again, but rather than going to the end of the list, stop when you reach n-2.
Keep repeating this until you reach 1.

The Wikipedia entry has a little simulation that shows how bubble sort works. The code looks something like:

bubbleSort(array A){
   n = length(A);

   for(j = n; j > 0, j--)
       for(i = 1; i < j; i++) {
         if A[i-1] > A[i]
             swap(A,i-1, i);
       }
   }
}

swap obviously swaps the elements and can be defined as:

swap(A, pos1, pos2) {
    temp = A[pos1];
    A[pos1] = A[pos2];
    A[pos2] = temp;
}

A slightly more sophisticated version of bubble sort also keeps track of the last position at which two elements were swapped, and to only run the outer loop to where the last swap occurred. After all, if the last swap was at position lastswap, then you know that all the elements between lastsswap and the end of the list are in the right order. The pseudo-code for the more sophisticated form of bubble sort is:

bubbleSort(array A) {
   n = length(A);
   for(j = 0; j < n; j++){
       lastswap = 1;
       for(i = 1; i < j; i++) {
         if A[i-1] > A[i] {
             swap(A[i-1], A[i]);
             lastswap = i;
       }      
       n = lastswap;
    }
}

Another sort is selection sort. We saw selection sort in the question in the sub-module on how to determine the complexity of an algorithm. Array a contains n elements, the elements to be sorted. The algorithm starts at the first position in the array and looks through the array for the smallest element. Once it reaches the end of the array, it puts that element in the first cell of the array. It then restarts the whole process from the second position in the array, and continues until the entire array has been sorted.

selection_sort(array A) {
    int i,j
    int iMin;
    for(j = 0; j < n; j++){
       iMin = j;

   for ( i = j+1; i < n; i++) {
       if (a[i] < a[iMin]) {
            iMin = i;
       }
   }

   if ( iMin != j ) {
       swap(a[j], a[iMin]);
   }
    }
}

The purpose of the project is to perform a timing experiment. You are required to complete the following activities:

Write a computer program that prompts the user for a number, creates an array for that number of random integers, and then uses the sophisticated form of bubble sort to order the array. The program should print out the array prior to the call to the sorting algorithm and afterwards. You can write the program in either Java, C++, C#, or whatever language you are most comfortable in.
Repeat 1 but use insertion sort this time.
1 and 2 are primarily intended to make sure that your algorithms work.

Once you are convinced your programs work, do the following

Write a computer program that prompts the user for two numbers, n for the number of items in the array to sort, and num_ifor a number of iterations. Then do the following:
Initiate a variable running_time to 0

Create a for loop that iterates num_i times.

In the body of the loop,

Create an array of n random integers

Get the time and set this to start-time. You will have to figure out what the appropriate command is in the programming language you are using to find them time

Use sophisticated bubble sort to sort the array

Get the time and set this to end-time

Subtract end-time from start-time and add the result to running_time

Once the program has run, note

The number of items sorted

The number of iterations

The running time

Repeat the process nine times, using 5, 25 and 50 as the size of the array, and 10, 100 and 1000 as the number of iterations.

Repeat 3 using selection sort.
Create a spreadsheet showing the results of 3 and 4 and create a graph to graphically represent the information
Write a one page document explaining the results, bearing in mind that both algorithms have a complexity of O(n^2) and what you know about complexity analysis.
Please submit

Program code for 1 and the three program runs
Program code for 2 and the three program runs
Program code used in 3
Program code used in 4
The spreadsheet created in 5
The report. In the report, say which machine you ran the experiments on (type of processor, RAM, etc).

These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice. Unethical use is strictly forbidden.

import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Scanner;

public class Program1 {

    /**
    * @param args the command line arguments
    */
    public static void main(String[] args) {
       // TODO code application logic here
       int number;
       Scanner scanner = new Scanner(System.in);
       System.out.print("Enter a positive nubmer: ");
       number = scanner.nextInt();
       int [] numbers = createArray(number);
       System.out.println("before: " + Arrays.toString(numbers));
       bubblesort(numbers);
      
       System.out.println("after: " + Arrays.toString(numbers));
      
    }
   
   
    public static void bubblesort(int [] numbers){
       int i,j;
       int iMin;
       int tmp;
       for ( j = 0; j < numbers.length; j++) {
            iMin = j ;
            for ( i = j+1; i < numbers.length; i++) {
                if (numbers[i] < numbers[iMin]) {
                   iMin = i;
                }               
            }
            if (iMin != j) {...