Results 1 to 2 of 2
  1. #1
    jeffsak is offline Member
    Join Date
    Jan 2017
    Posts
    3
    Rep Power
    0

    Default Help with Sorting Algorithm

    I have been trying to get this program to work for sometime now and I am struggling. I am trying to call the InsertionSort method inside of the shell sort, to sort a random list of N numbers. I am also trying to make a counter for how many times it goes through the list to process, that is why I have count = count + insertionSort in there. I know that the InsertionSort code works, but I am getting the following error when I run it.

    Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 3
    at MyClass.ShellSort(MyClass.java:64)
    at MyClass.main(MyClass.java:18)

    Here is my code for it so far:

    Java Code:
    import java.util.Random;
     
    public class MyClass {
        public static void main(String args[]) {
            Random rn = new Random();
            int N = 16;     
             
            int list[] = new int[N+1];
            for (int i = 1; i <= N; ++i) {
                // -- random list
                list[i] = rn.nextInt(100);
            }
            System.out.println("unsorted");
            for (int i = 1; i <= N; ++i) {
                System.out.println(list[i]);
            }
            int shellsort = ShellSort(list, N);
            System.out.println(N + " -> " + shellsort);
            System.out.println("sorted");
            for (int i = 1; i <= N; ++i) {
                System.out.println(list[i]);
            }
        }
     
    public static int ShellSort(int list[], int N) {
            int count = 0;
            int passes = log2(N);
            while (passes >= 1) {
                int increment = (int) Math.pow(2, passes - 1);
                int start = 1;
                int size = N / increment;
                int sublist[] = new int[N / increment + 1];
                for (int i = start; i <= N; i += increment) {
                    int j = 1;
                    for (i = start; i <= N; i += increment) {
                        sublist[j] = list[i];
                        ++j;
                    }
                    InsertionSort(sublist, N / increment);
                    list[i] = sublist[j];
                    int insertionSort = InsertionSort(list, N);
                    count = count + insertionSort;
                }
                passes = passes - 1;                     
            }
            return count;
        }
         
         public static int InsertionSort(int list[], int N)
            {
            int counter = 0;
            for (int i = 2; i <= N; ++i) {
                int newElement = list[i];
                int location = i - 1;
                while ((location >= 1) && (list[location] > newElement)) {
                    ++counter;
                    list[location + 1] = list[location];
                    location = location - 1;
                }
                ++counter;
                list[location + 1] = newElement;
            }
            return counter;     
        }
         
        public static int log2(int x)
        {
            return (int)(Math.log(x) / Math.log(2));
        }    
    }

  2. #2
    Norm's Avatar
    Norm is online now Moderator
    Join Date
    Jun 2008
    Location
    Eastern Florida
    Posts
    20,001
    Rep Power
    33

    Default Re: Help with Sorting Algorithm

    Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 3
    at MyClass.ShellSort(MyClass.java:64)
    The code at line 64 used an index past the end of the array. The array needs to have at least 4 elements to be able to use an index of 3.
    Remember valid array indexes range from 0 to the array's length -1
    If you don't understand my response, don't ignore it, ask a question.

Similar Threads

  1. Replies: 8
    Last Post: 10-19-2016, 08:06 PM
  2. Natural Sorting vs Custom Sorting
    By suhaas_mohandos in forum New To Java
    Replies: 1
    Last Post: 04-10-2014, 08:09 AM
  3. Issues with sorting algorithm
    By RAW-BERRY in forum New To Java
    Replies: 2
    Last Post: 03-26-2012, 03:45 PM
  4. Replies: 5
    Last Post: 07-11-2011, 01:40 PM
  5. Help with a sorting algorithm
    By doobybug in forum New To Java
    Replies: 2
    Last Post: 01-14-2011, 12:39 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
  •