I am sorting the following list of numbers which is in descending order. I am using QuickSort to sort and it is known that the worst case running time of QuickSort is $O(n^2)$
import java.io.File;
import java.io.FileNotFoundException;
import java.util.*;
public class QuickSort
{
static int pivotversion;
static int datacomparison=0;
static int datamovement=0;
public static void main(String args[])
{
Vector<Integer> container = new Vector<Integer>();
String userinput = "data2.txt";
Scanner myScanner = new Scanner("foo"); // variable used to read file
Scanner scan = new Scanner(System.in);
System.out.println("Enter 1 to set pivot to be first element");
System.out.println("Enter 2 to set pivot to be median of first , middle , last element of the list");
System.out.println("Your choice : ");
//pivotversion = scan.nextInt();
try
{
File inputfile = new File("C:\\Users\\8382c\\workspace\\AdvanceAlgorithmA3_Quicksort\\src\\" + userinput);
myScanner = new Scanner(inputfile);
}
catch(FileNotFoundException e)
{
System.out.println("File cant be found");
}
String line = myScanner.nextLine(); //read 1st line which contains the number of numbers to be sorted
while(myScanner.hasNext())
{
container.add(myScanner.nextInt());
}
System.out.println(line);
quickSort(container,0,container.size()-1);
for (int i =0;i<container.size();i++)
{
System.out.println(container.get(i));
}
System.out.println("=========================");
System.out.println(datamovement);
System.out.println(datacomparison);
}
public static int partition(Vector<Integer> container, int left, int right)
{
int i = left, j = right;
int tmp;
int pivot= 0 ;
pivot = container.get(left);
boolean maxarraybound = false;
i++;
while (i <= j)
{
while ( container.get(i) < pivot && maxarraybound == false)
{
if ( i == container.size()-1 )
{
maxarraybound = true;
}
else
{
i++;
datacomparison++;
}
}
while ( container.get(j) > pivot)
{
j--;
datacomparison++;
}
if (i <= j)
{
tmp = container.get(i);// considered data movement??
container.set(i, container.get(j));
datamovement++;
container.set(j, tmp);
datamovement++;
i++;
j--;
}
};
tmp = container.get(left);
container.set(left, container.get(i-1));
datamovement++;
container.set(i-1, tmp);
datamovement++;
return i-1;
}
public static void quickSort(Vector<Integer> container, int left, int right)
{
int index = partition(container, left, right);
if (left < index - 1)
quickSort(container, left, index - 1);
if (index+1 < right)
quickSort(container, index+1, right);
}
}
I am trying to prove to myself that the worst-case running time of QuickSort is indeed $O(n^2)$ by summing up the total number of data comparisons and data movements in the algorithm.
In my current situtation, I have an input of 10000 numbers.
I would expect a total sum of data comparison and data movement to be around 100 million.
I am only getting a total sum of data comparsion and data movement of around 26 million.
I am sure I have miss out some "data movement" and "data comparsion" in my algorithm, can someone point out to me where as I have no clue?