Insertion Sort using a String

Question

I combined 2 main classes into one to display the unsorted and sorted values of the inserted array Strings. The code given was using integers and I changed it to do Strings instead. I am having a problem with my insertionSort(). The compare to line is causing it to crash and I cannot figure out why!

 public void insertionSort()
  {
  int in, out;

  for(out=1; out<nElems; out++)     // out is dividing line
     {
     String temp = a[out];            // remove marked item
     in = out;                      // start shifts at out
     System.out.println(a[in]);
   --->while(a[in].compareTo(a[in+1])>0 ) // until one is smaller,
        {
        a[in] = a[in-1];            // shift item to right
        --in;                       // go left one position
        }
     a[in] = temp;                  // insert marked item
     }  // end for
  }  // end insertionSort()

Here is my main class:

   class SortApp
  {
  public static void main(String[] args)
    {
    int maxSize = 100;            // array size

  ArraySel arr;//reference to ray1--> selection sort
  ArrayIns arr2;// reference to array2--> insertion sort
  arr = new ArraySel(maxSize);  // create the array
  arr2 = new ArrayIns(maxSize);

  arr.insert("hello"); //insert words into the array
    arr.insert("this");
    arr.insert("is");
    arr.insert("a");
    arr.insert("random");
    arr.insert("weird ");
    arr.insert("sentence");
    arr.insert("that");
    arr.insert("does");
    arr.insert("not");
    arr.insert("make");
    arr.insert("any");
    arr.insert("sense");

    arr2.insert("hello");
    arr2.insert("this");
    arr2.insert("is");
    arr2.insert("a");
    arr2.insert("random");
    arr2.insert("weird ");
    arr2.insert("sentence");
    arr2.insert("that");
    arr2.insert("does");
    arr2.insert("not");
    arr2.insert("make");
    arr2.insert("any");
    arr2.insert("sense");

    arr.display();                // display items
  arr2.display();

  arr.selectionSort();//sort the 2 arrays
  arr2.insertionSort();

  arr.display();                // display them again
  arr2.display();
  }  // end main()
   }  // end class SelectSortApp

And here is the updated selectionSort class

public void selectionSort()
  {
  int out, in, min;

  for(out=0; out<nElems-1; out++)   // outer loop
     {
     min = out;                     // minimum
     for(in=out+1; in<nElems; in++) // inner loop

         if((a[in].compareTo(a[in-1])>0 ))        // if min greater,
            min = in;               // we have a new min
     swap(out, min);                // swap them

And what is the error? What are the values of a[] and nElems? — gtgaxiola
– gtgaxiola, Commented Feb 12, 2015 at 19:57
The values for a[ ] are 13 words that were inserted and the values for nElems would be 0-12 — joN
– joN, Commented Feb 12, 2015 at 20:07

Neil Masson · Accepted Answer · 2015-02-12 20:06:48Z

1

You need to compare a[in] with a[in-1] not a[in+1]. Your swap already uses the correct elements. With the code as is, a[in+1] can exceed the upper bound of your array,

answered Feb 12, 2015 at 20:06

Neil Masson

2,6891 gold badge17 silver badges23 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

joN Over a year ago

it definitely stopped crashing, thank you. However, it is still messing up the sort. I will post a more in depth result shortly.

gtgaxiola · Accepted Answer · 2015-02-12 20:52:52Z

0

You are really close to the solution

You should compare temp vs a[in-1] instead of a[in] vs a[in+1]

Also you need to check the in is always positive on the while loop in order to avoid IndexOutOfBoundsException

while(in > 0 && temp.compareTo(a[in-1]) < 0) 
{

edited Feb 12, 2015 at 20:52

answered Feb 12, 2015 at 20:24

gtgaxiola

9,3165 gold badges47 silver badges67 bronze badges

Comments

Sergey Kalinichenko · Accepted Answer · 2015-12-18 17:58:48Z

0

Here is my selection sort which works now:

public void selectionSort() {
   int out, in, min;
    for(out=0; out<nElems-1; out++)   // outer loop
    {
       min = out;                     // minimum
       for(in=out+1; in<nElems; in++) // inner loop
           if((a[in].compareTo(a[min])<0 ))        // if min greater,
               min = in;               // we have a new min
       swap(out, min);                // swap them
     }  // end for(out)
  }  // end selectionSort()

edited Dec 18, 2015 at 17:58

Sergey Kalinichenko

729k85 gold badges1.2k silver badges1.6k bronze badges

answered Feb 12, 2015 at 20:46

joN

54 bronze badges

Collectives™ on Stack Overflow

Insertion Sort using a String

3 Answers 3

1 Comment

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related