- Joined
- Sep 20, 2011
- Messages
- 1
- Reaction score
- 0
I'm trying to teach myself how to efficiently use sorting algorithms. One of the issues presented in my book is the task of counting the number of iterations for each loop in the ShellSort. The code given:
public ArrayList<Integer> ShellSort(Element[] e, Integer Size, Comparator<Element> c){
ArrayList<Integer> L = new ArrayList<Integer>();
Integer dist = Size/2;
while (dist>0){
for (Integer i=0; i<Size-dist; i++){
Integer k = i;
Integer j = k+dist;
while ((k>=0) && (c.compare(e[k], e[j])>0)){
//System.out.println(k+"\t"+j);
Element temp = e[k];
e[k] = e[j];
e[j] = temp;
j=k;
k-=dist;
}
}
dist=dist/2;
}
return L;
}
How can I separately keep track of the loop iterations for each of the 3 loops. Here is the way I did it for the InsertionSort - I want it similar to this:
public ArrayList<Integer> InsertionSort(Element[] e, Integer Right, Comparator<Element> c){
ArrayList<Integer> L = new ArrayList<Integer>();
L.add(0);
L.add(0);
for(Integer i = 0; i < Right-1; i++){ // O(n)
L.set(0, L.get(0)+1); // add one to outer loop count
Integer j = i;
while((j>=0) && (c.compare(e[j], e[j+1]) > 0)){ // O(n)
L.set(1, L.get(1)+1); // add one to inner loop count
Element temp = e[j];
e[j] = e[j+1];
e[j+1] = temp;
j--;
}
}
return L;
}
public ArrayList<Integer> ShellSort(Element[] e, Integer Size, Comparator<Element> c){
ArrayList<Integer> L = new ArrayList<Integer>();
Integer dist = Size/2;
while (dist>0){
for (Integer i=0; i<Size-dist; i++){
Integer k = i;
Integer j = k+dist;
while ((k>=0) && (c.compare(e[k], e[j])>0)){
//System.out.println(k+"\t"+j);
Element temp = e[k];
e[k] = e[j];
e[j] = temp;
j=k;
k-=dist;
}
}
dist=dist/2;
}
return L;
}
How can I separately keep track of the loop iterations for each of the 3 loops. Here is the way I did it for the InsertionSort - I want it similar to this:
public ArrayList<Integer> InsertionSort(Element[] e, Integer Right, Comparator<Element> c){
ArrayList<Integer> L = new ArrayList<Integer>();
L.add(0);
L.add(0);
for(Integer i = 0; i < Right-1; i++){ // O(n)
L.set(0, L.get(0)+1); // add one to outer loop count
Integer j = i;
while((j>=0) && (c.compare(e[j], e[j+1]) > 0)){ // O(n)
L.set(1, L.get(1)+1); // add one to inner loop count
Element temp = e[j];
e[j] = e[j+1];
e[j+1] = temp;
j--;
}
}
return L;
}