Data Structures and Algorithms > Unit 1 Chapters 1,2,3 Data Structures Overview Code > Flashcards

Unit 1 Chapters 1,2,3 Data Structures Overview Code Flashcards

(7 cards)

Study These Flashcards
1
Q

bubble sort

A 
////////////////////////////////////////////////////////////////
class ArrayBub
   {
   private long[] a;                 // ref to array a
   private int nElems;               // number of data items
//--------------------------------------------------------------
   public ArrayBub(int max)          // constructor
      {
      a = new long[max];                 // create the array
      nElems = 0;                        // no items yet
      }
//--------------------------------------------------------------
   public void insert(long value)    // put element into array
      {
      a[nElems] = value;             // insert it
      nElems++;                      // increment size
      }
//--------------------------------------------------------------
   public void display()             // displays array contents
      {
      for(int j=0; j1; out--)   // outer loop (backward)
         for(in=0; in a[in+1] )       // out of order?
               swap(in, in+1);          // swap them
      }  // end bubbleSort()
//--------------------------------------------------------------
   private void swap(int one, int two)
      {
      long temp = a[one];
      a[one] = a[two];
      a[two] = temp;
      }
//--------------------------------------------------------------
   }  // end class ArrayBub
////////////////////////////////////////////////////////////////
class BubbleSortApp
   {
   public static void main(String[] args)
      {
      int maxSize = 100;            // array size
      ArrayBub arr;                 // reference to array
      arr = new ArrayBub(maxSize);  // create the array

  arr. insert(77);               // insert 10 items
  arr. insert(99);
  arr. insert(44);
  arr. insert(55);
  arr. insert(22);
  arr. insert(88);
  arr. insert(11);
  arr. insert(00);
  arr. insert(66);
  arr. insert(33);

  arr. display();                // display items
  arr. bubbleSort();             // bubble sort them
      arr.display();                // display them again
      }  // end main()
   }  // end class BubbleSortApp
////////////////////////////////////////////////////////////////
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

array

A 
class ArrayApp
   {
   public static void main(String[] args)
      {
      long[] arr;                  // reference to array
      arr = new long[100];         // make array
      int nElems = 0;              // number of items
      int j;                       // loop counter
      long searchKey;              // key of item to search for
//--------------------------------------------------------------
      arr[0] = 77;                 // insert 10 items
      arr[1] = 99;
      arr[2] = 44;
      arr[3] = 55;
      arr[4] = 22;
      arr[5] = 88;
      arr[6] = 11;
      arr[7] = 00;
      arr[8] = 66;
      arr[9] = 33;
      nElems = 10;                 // now 10 items in array
//--------------------------------------------------------------
      for(j=0; j);
      }  // end main()
   }  // end class ArrayApp
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

ordered array

A 
class OrdArray
   {
   private long[] a;                 // ref to array a
   private int nElems;               // number of data items
   //-----------------------------------------------------------
   public OrdArray(int max)          // constructor
      {
      a = new long[max];             // create array
      nElems = 0;
      }
   //-----------------------------------------------------------
   public int size()
      { return nElems; }
   //-----------------------------------------------------------
   public int find(long searchKey)
      {
      int lowerBound = 0;
      int upperBound = nElems-1;
      int curIn;

      while(true)
         {
         curIn = (lowerBound + upperBound ) / 2;
         if(a[curIn]==searchKey)
            return curIn;              // found it
         else if(lowerBound > upperBound)
            return nElems;             // can't find it
         else                          // divide range
            {
            if(a[curIn] < searchKey)
               lowerBound = curIn + 1; // it's in upper half
            else
               upperBound = curIn - 1; // it's in lower half
            }  // end else divide range
         }  // end while
      }  // end find()
   //-----------------------------------------------------------
   public void insert(long value)    // put element into array
      {
      int j;
      for(j=0; j value)            // (linear search)
            break;
      for(int k=nElems; k>j; k--)    // move bigger ones up
         a[k] = a[k-1];
      a[j] = value;                  // insert it
      nElems++;                      // increment size
      }  // end insert()
   //-----------------------------------------------------------
   public boolean delete(long value)
      {
      int j = find(value);
      if(j==nElems)                  // can't find it
         return false;
      else                           // found it
         {
         for(int k=j; k + searchKey);

  arr.display();                 // display items

  arr. delete(00);                // delete 3 items
  arr. delete(55);
  arr. delete(99);
      arr.display();                 // display items again
      }  // end main()
   }  // end class OrderedApp
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

high array

A 
////////////////////////////////////////////////////////////////
class HighArray
   {
   private long[] a;                 // ref to array a
   private int nElems;               // number of data items
   //-----------------------------------------------------------
   public HighArray(int max)         // constructor
      {
      a = new long[max];                 // create the array
      nElems = 0;                        // no items yet
      }
   //-----------------------------------------------------------
   public boolean find(long searchKey)
      {                              // find specified value
      int j;
      for(j=0; j + searchKey);

  arr. delete(00);               // delete 3 items
  arr. delete(55);
  arr. delete(99);
      arr.display();                // display items again
      }  // end main()
   }  // end class HighArrayApp
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

selection sort

A 
class ArraySel
   {
   private long[] a;                 // ref to array a
   private int nElems;               // number of data items
//--------------------------------------------------------------
   public ArraySel(int max)          // constructor
      {
      a = new long[max];                 // create the array
      nElems = 0;                        // no items yet
      }
//--------------------------------------------------------------
   public void insert(long value)    // put element into array
      {
      a[nElems] = value;             // insert it
      nElems++;                      // increment size
      }
//--------------------------------------------------------------
   public void display()             // displays array contents
      {
      for(int j=0; j< a[min] )         // if min greater,
                min = in;               // we have a new min
         swap(out, min);                // swap them
         }  // end for(out)
      }  // end selectionSort()
//--------------------------------------------------------------
   private void swap(int one, int two)
      {
      long temp = a[one];
      a[one] = a[two];
      a[two] = temp;
      }
//--------------------------------------------------------------
   }  // end class ArraySel
////////////////////////////////////////////////////////////////
class SelectSortApp
   {
   public static void main(String[] args)
      {
      int maxSize = 100;            // array size
      ArraySel arr;                 // reference to array
      arr = new ArraySel(maxSize);  // create the array

  arr. insert(77);               // insert 10 items
  arr. insert(99);
  arr. insert(44);
  arr. insert(55);
  arr. insert(22);
  arr. insert(88);
  arr. insert(11);
  arr. insert(00);
  arr. insert(66);
  arr. insert(33);

  arr. display();                // display items
  arr. selectionSort();          // selection-sort them
      arr.display();                // display them again
      }  // end main()
   }  // end class SelectSortApp
////////////////////////////////////////////////////////////////
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

object sort

A 
////////////////////////////////////////////////////////////////
class Person
   {
   private String lastName;
   private String firstName;
   private int age;
   //-----------------------------------------------------------
   public Person(String last, String first, int a)
      {                               // constructor
      lastName = last;
      firstName = first;
      age = a;
      }
   //-----------------------------------------------------------
   public void displayPerson()
      {
      System.out.print("   Last name: " + lastName);
      System.out.print(", First name: " + firstName);
      System.out.println(", Age: " + age);
      }
   //-----------------------------------------------------------
   public String getLast()           // get last name
      { return lastName; }
   }  // end class Person
////////////////////////////////////////////////////////////////
class ArrayInOb
   {
   private Person[] a;               // ref to array a
   private int nElems;               // number of data items
//--------------------------------------------------------------
   public ArrayInOb(int max)         // constructor
      {
      a = new Person[max];               // create the array
      nElems = 0;                        // no items yet
      }
//--------------------------------------------------------------
                                     // put person into array
   public void insert(String last, String first, int age)
      {
      a[nElems] = new Person(last, first, age);
      nElems++;                          // increment size
      }
//--------------------------------------------------------------
   public void display()             // displays array contents
      {
      for(int j=0; j0 &&               // until smaller one found,
               a[in-1].getLast().compareTo(temp.getLast())>0)
            {
            a[in] = a[in-1];         // shift item to the right
            --in;                    // go left one position
            }
         a[in] = temp;               // insert marked item
         }  // end for
      }  // end insertionSort()
//--------------------------------------------------------------
   }  // end class ArrayInOb
////////////////////////////////////////////////////////////////
class ObjectSortApp
   {
   public static void main(String[] args)
      {
      int maxSize = 100;             // array size
      ArrayInOb arr;                 // reference to array
      arr = new ArrayInOb(maxSize);  // create the array

  arr. insert("Evans", "Patty", 24);
  arr. insert("Smith", "Doc", 59);
  arr. insert("Smith", "Lorraine", 37);
  arr. insert("Smith", "Paul", 37);
  arr. insert("Yee", "Tom", 43);
  arr. insert("Hashimoto", "Sato", 21);
  arr. insert("Stimson", "Henry", 29);
  arr. insert("Velasquez", "Jose", 72);
  arr. insert("Vang", "Minh", 22);
  arr. insert("Creswell", "Lucinda", 18);

  System.out.println("Before sorting:");
  arr.display();                 // display items

  arr.insertionSort();           // insertion-sort them
      System.out.println("After sorting:");
      arr.display();                 // display them again
      }  // end main()
   }  // end class ObjectSortApp
////////////////////////////////////////////////////////////////
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

insertion sort

A 
//--------------------------------------------------------------
class ArrayIns
   {
   private long[] a;                 // ref to array a
   private int nElems;               // number of data items
//--------------------------------------------------------------
   public ArrayIns(int max)          // constructor
      {
      a = new long[max];                 // create the array
      nElems = 0;                        // no items yet
      }
//--------------------------------------------------------------
   public void insert(long value)    // put element into array
      {
      a[nElems] = value;             // insert it
      nElems++;                      // increment size
      }
//--------------------------------------------------------------
   public void display()             // displays array contents
      {
      for(int j=0; j0 && a[in-1] >= temp) // 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()
//--------------------------------------------------------------
   }  // end class ArrayIns
////////////////////////////////////////////////////////////////
class InsertSortApp
   {
   public static void main(String[] args)
      {
      int maxSize = 100;            // array size
      ArrayIns arr;                 // reference to array
      arr = new ArrayIns(maxSize);  // create the array

  arr. insert(77);               // insert 10 items
  arr. insert(99);
  arr. insert(44);
  arr. insert(55);
  arr. insert(22);
  arr. insert(88);
  arr. insert(11);
  arr. insert(00);
  arr. insert(66);
  arr. insert(33);

  arr. display();                // display items
  arr. insertionSort();          // insertion-sort them
      arr.display();                // display them again
      }  // end main()
   }  // end class InsertSortApp
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
Data Structures and Algorithms
flashcards
Decks in class (25)
# Cards
Brainscape helps you reach your goals faster, through stronger study habits.
© 2026 Bold Learning Solutions. Terms and Conditions