יום חמישי, 13 בינואר 2011

13/01/11 Linear Data Structures


 import java.util.ArrayList;
 import java.util.Random;
/**
* Class for demonstrating basic array processing
*
* @author (your name)
* @version (a version number or a date)
*/
public class ArrayDemo
{
int [] myArray;

ArrayDemo (int length)
{
    myArray = new int [length];
}

/**
* postcondition: myArray is filled with random int values from 0 to (limit-1)
*/

public void fillRandom(int limit)
{
    if (limit<=9 && limit>=0) {
    Random generator = new Random(limit);
    for(int i = 0; i<myArray.length; i++)
    {
        myArray[i] = generator.nextInt();
    }}
}


/**
* postcondition: writes the array to console
*/

public void writeArray()
{
    for(int i = 0; i<myArray.length; i++)
    {
        System.out.println(myArray[i]);
    }
}



/**
* postcondition: values in MyArray first and second have been swapped

* first < myArray.length, second < myArray.length

*/

public void swap (int first, int second)
{
      int hold = myArray[first];
      myArray[first] = myArray[second];
      myArray[second] = hold;
}

/**
* sorts myArray in ascending order using insertion sort algorithm
*/

public void insertionSort()
{
      int[] newArray = new int [myArray.length];
      for(int i = 0; i<myArray.length; i++)
      {
          for(int x = 0; x<myArray.length-1; x++)
          {
              if(myArray[x] > myArray[x+1])
                    swap(x, x+1);
            }
          newArray[myArray.length-1-i] = myArray[myArray.length-1-i];
        }
      myArray = newArray;
}

/**
* sorts myArray in ascending order using selection sort algorithm
*/

public void selectionSort()
{
     int large = myArray[0];
     int place = 0;
     for(int i = 0; i<myArray.length-1; i++)
     {
         for(int z = i+1; z<myArray.length; z++)
         {
             if(myArray[z] > large) {
                 large = myArray[z];
                 place = z; }
            }
         swap(i, place);
         large = myArray[i+1];
         place = 0;
        }
}


/**
* postcondition: returns the index of the first occurence of target
* returns -1 if target not found
*/

public int sequentialSearch (int target)
{
     for(int i = 0; i<myArray.length; i++)
     {
         if(myArray[i] == target)
             return i;
        }
     return 0;
}

/**
* postcondition: returns true if target found
*
*/

public boolean binarySearch (int target)
{
    int more = myArray.length-1;
    int less = 0;
    int mid;
  
    while(less <= more) {
    mid = (more + less)/2;
    if(myArray[mid]>target)
        less = mid+1;
    if(myArray[mid]<target)
        more = mid-1;
    else return true; }
    return false;
}
}

אין תגובות:

הוסף רשומת תגובה