# Help with Sorting Algorithm

Printable View

• 09-20-2017, 08:11 PM
jeffsak
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:

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));     }    }```
• 09-20-2017, 09:10 PM
Norm
Re: Help with Sorting Algorithm
Quote:

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