I have been working on this assignment for a while now and I can't figure this one issue out. I was given four files, Name.java, SortableArrayList.java, NameListDriver.java, and SortableArrayListWithBubbleSort.java. The program is meant to take a text file with a list of names and sort them alphabetically. Part one of the assignment was to change the bubble sort to a recursive selection sort. I seem to have completed that part as I am able to sort the list of names. The second part requires me to make a driver that does the following things: • Creates a reference to an object in the abstract class SortableArrayList<Integer>, fill an array with random integers, output the array before sorting, then sort the array and output the sorted array. The size of the array is determined by a command line argument. It is supposed to be sorted by the same method that sorts the text file. I am able to create the array of random integers and output them, but I cant sort them.

Here is what i have so far for the driver

import java.util.*;
import java.io.*;
import java.util.Arrays;

class randomDriver<T extends Comparable<T>>
{

public static void main (String args[])
{//start main
    int capacity = Integer.parseInt(args[0]);

    int[] listItem = new int[capacity];

    int lowIndex;

    Random generator = new Random();

    //fills array with random integers

    for (int i = 0; i < listItem.length; i++)
    {//for
        listItem[i] = (generator.nextInt(1000) + 1);
    }//for

SortableArrayList nameList = new SortableArrayListWithSelectionSortII(capacity);

//output array before sort

System.out.println("List of numbers before sort:\n");
System.out.println(Arrays.toString(listItem));

//sort array and display

nameList.sort(); //sort list
System.out.println("\nList of numbers after sort:\n");
System.out.println(Arrays.toString(listItem));

}//end main


}//end class

Here is the sortableArrayListWithSelectionSortII.java that handles the sorting

//class that uses a selection sort to sort the text file of names
class SortableArrayListWithSelectionSortII<T extends Comparable<T>>
      extends SortableArrayList<T>
{

  public SortableArrayListWithSelectionSortII(int capacity)
  {
     super(capacity);
  }
  // sortSublist method

   protected void sortSublist(int lowIndex, int highIndex)
   {//start sortSublist

    if (lowIndex < highIndex)
    {//start if
       for (int i = lowIndex; i < highIndex; i++)
        { //start for
            System.out.println("sortSublist is linked");
        int indexOfNextSmallest = getIndexOfSmallest(listItem, i, highIndex-1);
        swap(listItem, i, indexOfNextSmallest);
        }//end for
        sortSublist(lowIndex, highIndex - 1);//recursive call
    }// end if
   } //end sortSublist

   private static <T extends Comparable<T>>
           int getIndexOfSmallest(T[] listItem, int first, int last)
   {
      T min = listItem[first];
      int indexOfMin = first;
      for (int i = first + 1; i <= last; i++)
      {
         if (listItem[i].compareTo(min) < 0)
         {
            min = listItem[i];
            indexOfMin = i;
         } // end if
         // Assertion: min is the smallest of a[first] through a[index].
      } // end for

      return indexOfMin;
   } // end getIndexOfSmallest


   private static void swap(Object[] listItem, int i, int j)
   {
      Object temp = listItem[i];
      listItem[i] = listItem[j];
      listItem[j] = temp; 
   } // end swap
} // end SortArray

Here is the SortableArrayList.Java that has some of the classes that I am using

abstract class SortableArrayList<T extends Comparable<T>>
{
   protected T[] listItem;

    protected int itemCount;

    private static int DEFAULT_CAPACITY = 50;

    private boolean isSorted;

    // Constructs a list with the specified capacity
    public SortableArrayList(int capacity)
    {
       @SuppressWarnings("unchecked")
       T[] tempList = (T[]) new Comparable[DEFAULT_CAPACITY];
        listItem = tempList;
        itemCount = 0;
        isSorted = false;
   }


   // Constructs a list with the default capacity   
    public SortableArrayList()
    {
       this(DEFAULT_CAPACITY);
    }

   /* Adds item to end of list
       pre-contition: itemCount < listItem.length() - 1
        post-contition: itemCount == itemCount@pre + 1
                        item added to end of list
    */  
    public void append(T newItem)
    {
      listItem[itemCount] = newItem;
      itemCount++;
      isSorted = false;  //List may no longer be sorted
    }

    /* Return item in given position
       If position is out of range, return null
    */
    public T getItem(int position)
    {
       if (0 <= position && position < itemCount)
          return listItem[position-1];
        else
          return null;
    }

    // Return length of list
    public int getLength()
    {
      return itemCount;
    }

    // Sort list
    public void sort()
    {
      sortSublist(0,itemCount-1);
      System.out.println("\n sort is working\n");
    }

    // Sort sublist from lowIndex to highIndex
    abstract protected void sortSublist(int lowIndex, int highIndex);

    /*
      Returns the position of the item with the given value.
      If the item is not in the list, returns -1.
    */
    public int search(T searchValue)
    {
       if (isSorted)
        {
          return binarySearch(searchValue,0,itemCount-1);
        }
        else
        {
          return linearSearch(searchValue);
        }
    }

    /*
      Searches for the index of the given value using the binary search algorithm
    */ 
    private int binarySearch(T searchValue, int lowIndex, int highIndex)
    {
       if (highIndex < lowIndex)
        {
          return -1; // not in list
        }
        else
        {
          int midIndex = lowIndex + (highIndex-lowIndex)/2;

          if (listItem[midIndex].equals(searchValue))
          {
            return midIndex;  //found it -- position is one more than index
          }
          else if (listItem[midIndex].compareTo(searchValue) > 0)
          {
            // searchValue comes before midIndex in array
            return binarySearch(searchValue,lowIndex,midIndex-1);
          }
          else
          {
             // listItem[midIndex] comes after midIndex in array
             return binarySearch(searchValue,midIndex+1,highIndex);
          }
        }
    }

    // Searches for the index of the given value using linear search
    private int linearSearch(T searchValue)
    {
       int index = itemCount-1;

        while (index >= 0 && !listItem[index].equals(searchValue))
        {
           index--;
        }

        return index;
    }

    // Returns a string of the items in the list -- 
    public String toString()
    {
       StringBuilder returnStringBuilder = new StringBuilder();

        for (int i = 0; i < itemCount; i++)
        {
           returnStringBuilder.append(listItem[i].toString() + "\n");
       }

        return returnStringBuilder.toString();
    }     
}

I believe that my problem is related to these three files so I wont post the others. If no one finds anything wrong with these three then Ill post the others. There is a seperate driver that I use for sorting the list of names. I need to be able to run that driver and have it sort the txt list of names and run this driver to sort the array of integers. Both drivers need to use the other three files. It looks like the if statement in sortableArrayListWithSelectionSortII.java is not running and neither is the for statement so Im pretty sure the problem is with how my driver talks to the selection sort. I've spent a lot of time on this so any help is very much appreciated

Recommended Answers

All 2 Replies

SortableArrayList nameList = new SortableArrayListWithSelectionSortII(capacity);
//output array before sort
System.out.println("List of numbers before sort:\n");
System.out.println(Arrays.toString(listItem));
//sort array and display
nameList.sort(); //sort list
System.out.println("\nList of numbers after sort:\n");
System.out.println(Arrays.toString(listItem));

You create an empty SortableArrayList called nameList, then you print some stuff that's not connected to nameList, then you sort nameList even though it is empty, then you print some other stuff not connected to nameList. I expect that accomplishes very little.

I also notice that you print listItem twice without changing it between the two printings. That doesn't seem useful either.

I should mention that it displays the array with the integers, it just doesnt sort them so it is displaying the same thing twice.

What you say makes sense, but I'm not sure how to go about fixing that issue. What it needs to do is reference the method sort() in the abstract class sortableArrayList. The method sort calls the method sortSublist from SortableArrayListWithSelectionSortII.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.