0 Replies - 164 Views - Last Post: 06 February 2013 - 09:38 AM Rate Topic: ***** 1 Votes

#1 iridebmxnj  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 15
  • Joined: 15-December 12

BubbleSort random integers in array list question

Posted 06 February 2013 - 09:38 AM

I was given the following code to use to start my project, the project is to first create an array of random integers from 0-1000 and then sort them from least to greatest.
I have created the array of random integers but I am not sure how to implement the bubble sort class that was included.

here is the code I have written so far
class bubbleDriver
{
   public static void main(String args[])
	{
	  int capacity = Integer.parseInt(args[0]);
	 
	  
	  
	  SortableArrayList<Integer> integerList  = new bubbleSorting<Integer>(capacity);
									  
	 	 
		 int j = 10;
		 
		  int myarray[] = new int [j];

		 for (int i = 0 ; i < j ; i++)
		 {
		 myarray [i] = (int) (Math.random () * 1000);
		 
		 System.out.println(myarray[i]);
		
		 
		 }
		 
		 System.out.println("Array length is " + myarray.length);
		 
		 
	  
	   
	// Sort and print in numerical order
	  integerList.sort();
	  System.out.println("Contents of NumberList sorted : "  );
	  

 } // main
	
}



This was the code I was given to work with
bubble sorting class
class bubbleSorting<T extends Comparable<T>>
      extends SortableArrayList<T>
{

  public bubbleSorting(int capacity)
  {
     super(capacity);
  }
  // Sorts the sublist from lowIndex to highIndex using Bubble Sort
  // Uses recursion to sort smaller sublists
  protected void sortSublist(int lowIndex, int highIndex)
  {
    if(lowIndex < highIndex)
	 {
	   // The sublist has more than one element, so sort it
      /* "Bubble" largest value in listItem[lowIndex]...listItem[i]
		   to position i by swapping adjacent items that are out of order
	   */
	   for (int i = lowIndex; i < highIndex; i++)
	   {
		  if (listItem[i].compareTo(listItem[i+1]) > 0)
		  {
		    // swap items
		    T temp = listItem[i];
			 listItem[i] = listItem[i+1];
			 listItem[i+1] = temp;
		  }
	   } //for loop
	  
	   // Use bubble sort to sort the rest of the list
	   sortSublist(lowIndex,highIndex-1);
	 } //if statement
  }
} 



SortableArrayList Class
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];//position 
		else
		  return null;
	}
	
	// Return length of list
	public int getLength()
	{
	  return itemCount;
	}
	
	// Sort list
	public void sort()
	{
	  sortSublist(0,itemCount-1);
	}
	
	// Sort sublist from lowIndex to highIndex
	abstract protected void sortSublist(int lowIndex, int highIndex); // method does not get implemented in class
	// only used in this class, or a subclass
	/*
	  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();
	}	  
}



Is This A Good Question/Topic? 0
  • +

Page 1 of 1