Java Merge Sort...
import java.util.*;
public class SortsCounting{
private long steps;
/**
* Description of Constructor
*
* @param list Description of Parameter
*/
public SortsCounting(){
steps = 0;
}
/**
* Description of the Method
*
* @param list reference to an array of integers to be sorted
*/
public void bubbleSort(ArrayList <Comparable> list){
steps = 0;
for (int outer = 0; outer < list.size() - 1; outer++){
for (int inner = 0; inner < list.size()-outer-1; inner++){
steps += 3;//count one compare and 2 gets
if (list.get(inner).compareTo(list.get(inner + 1)) > 0){
steps += 4;//count 2 gets and 2 sets
//swap list[inner] & list[inner+1]
Comparable temp = list.get(inner);
list.set(inner,list.get(inner + 1));
list.set(inner + 1,temp);
}
}
}
}
/**
* Description of the Method
*
* @param list reference to an array of integers to be sorted
*/
public void selectionSort(ArrayList <Comparable> list){
Comparable temp;
int min;
steps = 0;
for (int outer = 0; outer < list.size() - 1; outer++){
min = outer;
for (int inner = outer + 1; inner < list.size(); inner++){
steps += 3; //count one compare and 2 gets
if (list.get(inner).compareTo(list.get(min)) < 0){
min = inner; // a new smallest item is found
}
}
steps += 4;//count 2 gets and 2 sets
//swap list[outer] & list[min]
temp = list.get(outer);
list.set(outer,list.get(min));
list.set(min,temp);
}
}
/**
* Description of the Method
*
* @param list reference to an array of integers to be sorted
*/
public void insertionSort(ArrayList <Comparable> list){
steps = 0;
for (int outer = 1; outer < list.size(); outer++){
int position = outer;
steps++; //count one get
Comparable key = list.get(position);
// Shift larger values to the right
steps += 2;//the get and compare in the loop conditional
//are executed one more time than the loop body
while (position > 0 && list.get(position - 1).compareTo(key) > 0){
steps += 4; //count one compare, 2 gets, and 1 set
list.set(position,list.get(position - 1));
position--;
}
steps++; //count one set
list.set(position,key);
}
}
/**
* Takes in entire vector, but will merge the following sections
* together: Left sublist from a[first]..a[mid], right sublist from
* a[mid+1]..a[last]. Precondition: each sublist is already in
* ascending order
*
* @param a reference to an array of integers to be sorted
* @param first starting index of range of values to be sorted
* @param mid midpoint index of range of values to be sorted
* @param last last index of range of values to be sorted
*/
private void merge(ArrayList <Comparable> a, int first, int mid, int last){
int aPtr = first;
int bPtr = mid + 1;
int cPtr = first;
int total = last - first + 1;
int loop;
boolean doneA = false;
boolean doneB = false;
ArrayList <Comparable> c = new ArrayList <Comparable>(a);
for (loop = 1; loop <= total; loop++){
if (doneA){
steps += 2; // 1 set, 1 get
c.set(cPtr, a.get(bPtr));
bPtr++;
} else if (doneB){
steps += 2; // 1 set, 1 get
c.set(cPtr, a.get(aPtr));
aPtr++;
} else if (a.get(aPtr).compareTo(a.get(bPtr)) < 0){
// ok to compare, valid data in each sublist
steps += 2; // 1 get, 1 set
c.set(cPtr, a.get(aPtr));
aPtr++;
} else {
steps += 2; // 1 get, 1 set
c.set(cPtr, a.get(bPtr));
bPtr++;
}
steps += 3; // line 131, 2 gets, 1 compare
cPtr++;
if (aPtr > mid){
doneA = true;
}
if (bPtr > last){
doneB = true;
}
}
for (loop = first; loop <= last; loop++){
a.set(loop,c.get(loop));
steps += 2; // 1 set, 1 get
}
}
/**
* Recursive mergesort of an array of integers
*
* @param a reference to an array of integers to be sorted
* @param first starting index of range of values to be sorted
* @param last ending index of range of values to be sorted
*/
public void mergeSort(ArrayList <Comparable> a, int first, int last){
// Replace these lines with your code
int mid;
int temp;
steps = 0;
if (first == last){ // empty case, only 1 value, do nothing
}else{
if (first + 1 == last){
// list of 2 values, swap if necessary
steps+=3; // 2 gets 1 compare
if (a.get(first).compareTo(a.get(last)) < 0){
swap(a, first, last);
}
} else {
// general case
mid = (first + last) / 2;
mergeSort(a, first, mid);
mergeSort(a, mid + 1, last);
merge(a, first, mid, last);
// the function calls also require steps, but we won't count them
}
}
}
/**
* Accessor method to return the current value of steps
*
*/
public long getStepCount(){
return steps;
}
/**
* Modifier method to set or reset the step count. Usually called
* prior to invocation of a sort method.
*
* @param stepCount value assigned to steps
*/
public void setStepCount(long stepCount){
steps = stepCount;
}
/**
* Interchanges two elements in an ArrayList
*
* @param list reference to an array of integers
* @param a index of integer to be swapped
* @param b index of integer to be swapped
*/
public void swap(ArrayList <Comparable> list, int a, int b){
Comparable c = list.get(a);
list.set(a, list.get(b));
list.set(b, c);
steps += 4;// 2 gets 2 sets
}
public static void main(String[] args) {
ArrayList <Comparable> myArrayList = new ArrayList();
SortsCounting mySorts = new SortsCounting();
myArrayList.add(0,5); myArrayList.add(1,4); myArrayList.add(2,3); myArrayList.add(3,2); myArrayList.add(4,1);
System.out.println(myArrayList);
mySorts.mergeSort(myArrayList,0,4);
mySorts.merge(myArrayList,0,2,4);
System.out.println(myArrayList);
}
}
My output:
Y:\>java SortsCounting
[5, 4, 3, 2, 1]
[2, 1, 3, 5, 4]
Y:\>
The problem:
I know I am doing one of two things wrong...
1) My main method is totally wrong.
2) The recursive mergesort is wrong.
Someone help...
Comments