Assignment Problem

Design and implement an experiment to compare in real time the running times of the following searching algorithms:

- binary search

- sequential search - sorted search

An implementation of quicksort is given in a separate file (you are required to use it to sort the data in the sorted and binary searches). Time the searching algorithms several times each, and save the results in a .csv file that can be open in an Excel file later. Format your .csv file as follows:

, < binary search time>, , < sorted search time > , < binary search time>, , < sorted search time > , < binary search time>, , < sorted search time > , < binary search time>, , < sorted search time > , < binary search time>, , < sorted search time >

...

For example (the numbers are not taken from a real example; they are offered to illustrate the content of the file)

100 165448 5553 200 635102 6291 300 1475774 9324 400 457126 12153 500 626482 18096

...

 85531 170288 60707 63218 92991 

All of the data (array values and search values) should be randomly generated using the method nextInt() from the java.util.Random class. Time not less than 5000 runs of these algorithms (i.e. your .csv file should have, at least, that number of lines). To time your code use System.nanoTime().

Use Excel to depict graphically the results of your experiment. What did you observe?

SearchingAlgorithms

+static boolean binarySearch(int[] list, int x) +static boolean sequentialSearch(int[] list, int x) +static boolean sortedSearch(int[] list, int x) +static void quickSort(int[] list)

+static void fillArray(int[] list)

+static void printArray(int[] list)

Main

+static void main(String[] args) +Main()

quicksort

public static void quickSort(int[] list)

{

quicksort(list, 0, list.length - 1);

}

private static void quicksort(int[] list, int begin, int end)

{

int temp;

int pivot = findPivotLocation(begin, end);

// swap list[pivot] and list[end]

temp = list[pivot];

list[pivot] = list[end];

list[end] = temp;

pivot = end;

int i = begin,

j = end - 1;

boolean iterationCompleted = false;

while (!iterationCompleted)

{

while (list[i] < list[pivot])

i++;

while ((j >= 0) && (list[pivot] < list[j]))

j--;

if (i < j)

{

//swap list[i] and list[j]

temp = list[i];

list[i] = list[j];

list[j] = temp;

i++;

j--;

} else

iterationCompleted = true;

}

//swap list[i] and list[pivot]

temp = list[i];

list[i] = list[pivot];

list[pivot] = temp;

if (begin < i - 1) quicksort(list, begin, i - 1);

if (i + 1 < end) quicksort(list, i + 1, end);

}

/*

* Computes the pivot

*/

private static int findPivotLocation(int b, int e)

{

return (b + e) / 2;

}

Main

import java.io.FileWriter;

import java.io.IOException;

import java.io.PrintWriter;

import java.util.Random;

public class WritingToTextfile

{

public static void main(String[] args)

{

String outputFilename = "output.csv";

PrintWriter output = null;

//open output stream

try

{

output = new PrintWriter(new FileWriter(outputFilename));

} catch (IOException ex)

{

System.exit(1);

}

Random rnd = new Random();

int n = 100;

for (int i = 0; i < n; i++)

{

output.println(i + "," + rnd.nextInt(10) + "," + rnd.nextInt(100) + "," + rnd.nextInt(1000));

}

//close output stream

output.close();

}

}