ShellSort

Discussion in 'Java' started by DECEPTI0N92, Sep 20, 2011.

  1. DECEPTI0N92

    DECEPTI0N92

    Joined:
    Sep 20, 2011
    Messages:
    1
    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;
    }
    DECEPTI0N92, Sep 20, 2011
    #1
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.

Share This Page