Results 1 to 12 of 12

Thread: shell sort

  1. #1
    fam2315 is offline Member
    Join Date
    Feb 2011
    Posts
    78
    Rep Power
    0

    Default shell sort

    I have been given an assignment to do an analysis on the runtimes of various sorting routines, one of which being the shell sort. We were given 4 sets of increments for the shell sort, but I can't find a shell sort algorithm that takes the increments in as an argument, or is that not the way the increment is used?

  2. #2
    fam2315 is offline Member
    Join Date
    Feb 2011
    Posts
    78
    Rep Power
    0

    Default

    here is one that I found that seems to only use 1 value as an increment, I have 6 values that I need to pass in as a sequence:

    Java Code:
    public static void shell(int[] a) {
    	int increment = a.length / 2;
    	while (increment > 0) {
    		for (int i = increment; i < a.length; i++) {
    			int j = i;
    			int temp = a[i];
    			while (j >= increment && a[j - increment] > temp) {
    				a[j] = a[j - increment];
    				j = j - increment;
    			}
    			a[j] = temp;
    		}
    		if (increment == 2) {
    			increment = 1;
    		} else {
    			increment *= (5.0 / 11);
    		}
    	}
    }
    Last edited by fam2315; 08-14-2011 at 11:59 PM.

  3. #3
    Junky's Avatar
    Junky is offline Grand Poobah
    Join Date
    Jan 2011
    Location
    Dystopia
    Posts
    3,798
    Rep Power
    7

    Default

    Quote Originally Posted by fam2315 View Post
    but I can't find a shell sort algorithm that takes the increments in as an argument
    So pass the increments in as a second parameter. Do you understand the code you posted? It calculates the next increment each time around the loop. Instead of doing that you just grab the next increment from the list of increments passed in as a parameter.

  4. #4
    fam2315 is offline Member
    Join Date
    Feb 2011
    Posts
    78
    Rep Power
    0

    Default

    Here is what I have

    Java Code:
    public static void shell(int[] a, int[] sequence) {
    	int increment =sequence[0];
    	while (increment > 0) {
    		for (int i = increment; i < a.length; i++) {
    			int j = i;
    			int temp = a[i];
    			while (j >= increment && a[j - increment] > temp) {
    				a[j] = a[j - increment];
    				j = j - increment;
    			}
    			a[j] = temp;
    		}
    		if (increment == 2) {
    			increment = 1;
    		} else {
    			increment *= sequence[i];
    		}
    	}
    }
    This wont work though, because i is inside the for loop.

  5. #5
    Junky's Avatar
    Junky is offline Grand Poobah
    Join Date
    Jan 2011
    Location
    Dystopia
    Posts
    3,798
    Rep Power
    7

    Default

    I may be on the wrong track but I imagine the increments passed into the method would be something like {6,4,2,1,0}. Then at the end of your loop where you get the next increment you don't need the if statement. Just assign the next increment in the array to the variable.

  6. #6
    fam2315 is offline Member
    Join Date
    Feb 2011
    Posts
    78
    Rep Power
    0

    Default

    that sounds right to me just about. My sequence ends with a 1, so I guess that while loop should be >=1?

    I just cant put it all together.

  7. #7
    Junky's Avatar
    Junky is offline Grand Poobah
    Join Date
    Jan 2011
    Location
    Dystopia
    Posts
    3,798
    Rep Power
    7

    Default

    It just takes a moment to think.
    Java Code:
    public static void shell(int[] a, int[] sequence) {
        int counter = 0;
        int increment =sequence[counter++];
        // loop
            increment = sequence[counter++];
        // end loop
    }

  8. #8
    fam2315 is offline Member
    Join Date
    Feb 2011
    Posts
    78
    Rep Power
    0

    Default

    Am I missing something?

    Java Code:
        public static void shellsort(int[] a, int[] sequence) {
            int counter = 0;
            int increment = sequence[counter++];
            for (int i = increment; i < a.length; i++) {
                int j = i;
                int temp = a[i];
                while (j >= increment && a[j - increment] > temp) {
                    a[j] = a[j - increment];
                    j = j - increment;
                }
                a[j] = temp;
            }
            increment = sequence[counter++];
        }

  9. #9
    Junky's Avatar
    Junky is offline Grand Poobah
    Join Date
    Jan 2011
    Location
    Dystopia
    Posts
    3,798
    Rep Power
    7

    Default

    Quote Originally Posted by fam2315 View Post
    Am I missing something?
    I don't know, are you? It would help if you explained things. Errors? Incorrect behaviour? Exploding mice?

    Just to reiterate:
    // loop
    increment = sequence[counter++];
    // end loop

  10. #10
    fam2315 is offline Member
    Join Date
    Feb 2011
    Posts
    78
    Rep Power
    0

    Default

    Well, when I print out the integer array after the sort, its all kinds of weird characters. No errors though.

  11. #11
    fam2315 is offline Member
    Join Date
    Feb 2011
    Posts
    78
    Rep Power
    0

    Default

    I am trying to now modify this sort. To take in as an argument the gap sequence as opposed to calculating it:

    Java Code:
       public static void shellsort( Comparable [ ] a )
        {
            for( int gap = a.length / 2; gap > 0;
                         gap = gap == 2 ? 1 : (int) ( gap / 2.2 ) )
                for( int i = gap; i < a.length; i++ )
                {
                    Comparable tmp = a[ i ];
                    int j = i;
    
                    for( ; j >= gap && tmp.compareTo( a[ j - gap ] ) < 0; j -= gap )
                        a[ j ] = a[ j - gap ];
                    a[ j ] = tmp;
                }
        }
    Here is what I have but it keeps blowing up with an indexOutofBoundsException on the last line

    There has to be an easier way to pass in a gap sequence.
    Java Code:
        public static void shellSort(Comparable[] data, int[] gs) {
            int counter = 0;
            for (int gap = gs[counter]; gap < data.length;) {
                for (int i = gap; i < data.length; i++) {
                    Comparable tmp = data[ i];
                    int c = i;
    
                    for (; c >= gap && tmp.compareTo(data[ c - gap]) < 0; c -= gap) {
                        data[ c] = data[ c - gap];
                        gap = gs[counter++];
                    }
                    data[ c] = tmp;
                }
              gap = gs[counter++];
            }
        }

  12. #12
    Junky's Avatar
    Junky is offline Grand Poobah
    Join Date
    Jan 2011
    Location
    Dystopia
    Posts
    3,798
    Rep Power
    7

    Default

    Java Code:
    for (int gap = gs[counter]; gap < data.length;) {
    What happens if the first gap value is 10 and you are trying to sort 3 items? 10 is not less than 3 so it never enters the loop. This is another problem besides your AIOOBE.

    Why are you making this much harder than it needs to be? Below is the original code you posted above with comments on the simple changes you need to make.
    Java Code:
    public static void shell(int[] a) { // add second parameter for gap values
        // declare counter variable
        int increment = a.length / 2; // assign first gap value to increment
        while (increment > 0) { // see note below
            for (int i = increment; i < a.length; i++) {
                	int j = i;
                	int temp = a[i];
                	while (j >= increment && a[j - increment] > temp) {
                    a[j] = a[j - increment];
                    j = j - increment;
                }
                a[j] = temp;
            }
            // replace below if statement with a single statement
            // which assigns the next gap value to increment
            if (increment == 2) {
                increment = 1;
            } else {
                increment *= (5.0 / 11);
            }
        }
    }
    NOTE: The current while loop will still work if the last gap value was 0 but you mentioned that it will be 1. Therefore you will need to change the condition. You could use a boolean flag and add an if statement to control it. Or you could just use the counter in the while condition.

Similar Threads

  1. Hibbard's Shell Sort
    By biglandphil in forum New To Java
    Replies: 2
    Last Post: 11-12-2009, 08:38 PM
  2. Using Merge Sort to sort an ArrayList of Strings
    By coldfire in forum New To Java
    Replies: 3
    Last Post: 03-13-2009, 01:03 AM
  3. How to sort a list using Bubble sort algorithm
    By Java Tip in forum Algorithms
    Replies: 3
    Last Post: 04-29-2008, 08:04 PM
  4. Shell Sort in Java
    By Java Tip in forum Algorithms
    Replies: 0
    Last Post: 04-15-2008, 07:44 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •