Unit 5 Chapter 7 Advanced Sorting Code Flashcards

1
Q

shellSort

A
//--------------------------------------------------------------
class ArraySh
   {
   private long[] theArray;          // ref to array theArray
   private int nElems;               // number of data items
//--------------------------------------------------------------
   public ArraySh(int max)           // constructor
      {
      theArray = new long[max];      // create the array
      nElems = 0;                    // no items yet
      }
//--------------------------------------------------------------
   public void insert(long value)    // put element into array
      {
      theArray[nElems] = value;      // insert it
      nElems++;                      // increment size
      }
//--------------------------------------------------------------
   public void display()             // displays array contents
      {
      System.out.print("A=");
      for(int j=0; j0)                     // decreasing h, until h=1
         {
                                     // h-sort the file
         for(outer=h; outer h-1 && theArray[inner-h] >=  temp)
               {
               theArray[inner] = theArray[inner-h];
               inner -= h;
               }
            theArray[inner] = temp;
            }  // end for
         h = (h-1) / 3;              // decrease h
         }  // end while(h>0)
      }  // end shellSort()
//--------------------------------------------------------------
   }  // end class ArraySh
////////////////////////////////////////////////////////////////
class ShellSortApp
   {
   public static void main(String[] args)
      {
      int maxSize = 10;             // array size
      ArraySh arr;
      arr = new ArraySh(maxSize);   // create the array
  for(int j=0; j<maxSize; j++)  // fill array with
     {                          // random numbers
     long n = (int)(java.lang.Math.random()*99);
     arr.insert(n);
     }
  arr.display();                // display unsorted array
  arr.shellSort();              // shell sort the array
  arr.display();                // display sorted array
  }  // end main()    }  // end class ShellSortApp ////////////////////////////////////////////////////////////////
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

quickSort3

A
////////////////////////////////////////////////////////////////
class ArrayIns
   {
   private long[] theArray;          // ref to array theArray
   private int nElems;               // number of data items
//--------------------------------------------------------------
   public ArrayIns(int max)          // constructor
      {
      theArray = new long[max];      // create the array
      nElems = 0;                    // no items yet
      }
//--------------------------------------------------------------
   public void insert(long value)    // put element into array
      {
      theArray[nElems] = value;      // insert it
      nElems++;                      // increment size
      }
//--------------------------------------------------------------
   public void display()             // displays array contents
      {
      System.out.print("A=");
      for(int j=0; j< 10)                   // insertion sort if small
         insertionSort(left, right);
      else                            // quicksort if large
         {
         long median = medianOf3(left, right);
         int partition = partitionIt(left, right, median);
         recQuickSort(left, partition-1);
         recQuickSort(partition+1, right);
         }
      }  // end recQuickSort()
//--------------------------------------------------------------
   public long medianOf3(int left, int right)
      {
      int center = (left+right)/2;
                                       // order left & center
      if( theArray[left] > theArray[center] )
         swap(left, center);
                                       // order left & right
      if( theArray[left] > theArray[right] )
         swap(left, right);
                                       // order center & right
      if( theArray[center] > theArray[right] )
         swap(center, right);
      swap(center, right-1);           // put pivot on right
      return theArray[right-1];        // return median value
      }  // end medianOf3()
//--------------------------------------------------------------
   public void swap(int dex1, int dex2)  // swap two elements
      {
      long temp = theArray[dex1];        // A into temp
      theArray[dex1] = theArray[dex2];   // B into A
      theArray[dex2] = temp;             // temp into B
      }  // end swap(
//--------------------------------------------------------------
    public int partitionIt(int left, int right, long pivot)
       {
       int leftPtr = left;             // right of first elem
       int rightPtr = right - 1;       // left of pivot
       while(true)
          {
          while( theArray[++leftPtr] < pivot )  // find bigger
             ;                                  // (nop)
          while( theArray[--rightPtr] > pivot ) // find smaller
             ;                                  // (nop)
          if(leftPtr >= rightPtr)      // if pointers cross,
             break;                    //    partition done
          else                         // not crossed, so
             swap(leftPtr, rightPtr);  // swap elements
          }  // end while(true)
       swap(leftPtr, right-1);         // restore pivot
       return leftPtr;                 // return pivot location
       }  // end partitionIt()
//--------------------------------------------------------------
                                       // insertion sort
   public void insertionSort(int left, int right)
      {
      int in, out;
                                       //  sorted on left of out
      for(out=left+1; outleft && theArray[in-1] >= temp)
            {
            theArray[in] = theArray[in-1]; // shift item to right
            --in;                      // go left one position
            }
         theArray[in] = temp;          // insert marked item
         }  // end for
      }  // end insertionSort()
//--------------------------------------------------------------
   }  // end class ArrayIns
////////////////////////////////////////////////////////////////
class QuickSort3App
   {
   public static void main(String[] args)
      {
      int maxSize = 16;             // array size
      ArrayIns arr;                 // reference to array
      arr = new ArrayIns(maxSize);  // create the array
  for(int j=0; j<maxSize; j++)  // fill array with
     {                          // random numbers
     long n = (int)(java.lang.Math.random()*99);
     arr.insert(n);
     }
  arr.display();                // display items
  arr.quickSort();              // quicksort them
  arr.display();                // display them again
  }  // end main()    }  // end class QuickSort3App ////////////////////////////////////////////////////////////////
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

quickSort2

A
////////////////////////////////////////////////////////////////
class ArrayIns
   {
   private long[] theArray;          // ref to array theArray
   private int nElems;               // number of data items
//--------------------------------------------------------------
   public ArrayIns(int max)          // constructor
      {
      theArray = new long[max];      // create the array
      nElems = 0;                    // no items yet
      }
//--------------------------------------------------------------
   public void insert(long value)    // put element into array
      {
      theArray[nElems] = value;      // insert it
      nElems++;                      // increment size
      }
//--------------------------------------------------------------
   public void display()             // displays array contents
      {
      System.out.print("A=");
      for(int j=0; j theArray[center] )
         swap(left, center);
                                         // order left & right
      if( theArray[left] > theArray[right] )
         swap(left, right);
                                         // order center & right
      if( theArray[center] > theArray[right] )
         swap(center, right);
      swap(center, right-1);             // put pivot on right
      return theArray[right-1];          // return median value
      }  // end medianOf3()
//--------------------------------------------------------------
   public void swap(int dex1, int dex2)  // swap two elements
      {
      long temp = theArray[dex1];        // A into temp
      theArray[dex1] = theArray[dex2];   // B into A
      theArray[dex2] = temp;             // temp into B
      }  // end swap(
//--------------------------------------------------------------
    public int partitionIt(int left, int right, long pivot)
       {
       int leftPtr = left;             // right of first elem
       int rightPtr = right - 1;       // left of pivot
   while(true)
      {
      while( theArray[++leftPtr] < pivot )  // find bigger
         ;                                  //    (nop)
      while( theArray[--rightPtr] > pivot ) // find smaller
         ;                                  //    (nop)
      if(leftPtr >= rightPtr)      // if pointers cross,
         break;                    //    partition done
      else                         // not crossed, so
         swap(leftPtr, rightPtr);  // swap elements
      }  // end while(true)
   swap(leftPtr, right-1);         // restore pivot
   return leftPtr;                 // return pivot location
   }  // end partitionIt() //--------------------------------------------------------------    public void manualSort(int left, int right)
  {
  int size = right-left+1;
  if(size  theArray[right] )
        swap(left, right);
     return;
     }
  else               // size is 3
     {               // 3-sort left, center, & right
     if( theArray[left] > theArray[right-1] )
        swap(left, right-1);                // left, center
     if( theArray[left] > theArray[right] )
        swap(left, right);                  // left, right
     if( theArray[right-1] > theArray[right] )
        swap(right-1, right);               // center, right
     }
  }  // end manualSort() //--------------------------------------------------------------    }  // end class ArrayIns //////////////////////////////////////////////////////////////// class QuickSort2App    {    public static void main(String[] args)
  {
  int maxSize = 16;             // array size
  ArrayIns arr;                 // reference to array
  arr = new ArrayIns(maxSize);  // create the array

  for(int j=0; j<maxSize; j++)  // fill array with
     {                          // random numbers
     long n = (int)(java.lang.Math.random()*99);
     arr.insert(n);
     }
  arr.display();                // display items
  arr.quickSort();              // quicksort them
  arr.display();                // display them again
  }  // end main()    }  // end class QuickSort2App ////////////////////////////////////////////////////////////////
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

quickSort1

A
////////////////////////////////////////////////////////////////
class ArrayIns
   {
   private long[] theArray;          // ref to array theArray
   private int nElems;               // number of data items
//--------------------------------------------------------------
   public ArrayIns(int max)          // constructor
      {
      theArray = new long[max];      // create the array
      nElems = 0;                    // no items yet
      }
//--------------------------------------------------------------
   public void insert(long value)    // put element into array
      {
      theArray[nElems] = value;      // insert it
      nElems++;                      // increment size
      }
//--------------------------------------------------------------
   public void display()             // displays array contents
      {
      System.out.print("A=");
      for(int j=0; j< pivot )
             ;  // (nop)
                                       // find smaller item
          while(rightPtr > 0 && theArray[--rightPtr] > pivot)
             ;  // (nop)
          if(leftPtr >= rightPtr)      // if pointers cross,
             break;                    //    partition done
          else                         // not crossed, so
             swap(leftPtr, rightPtr);  //    swap elements
          }  // end while(true)
       swap(leftPtr, right);           // restore pivot
       return leftPtr;                 // return pivot location
       }  // end partitionIt()
//--------------------------------------------------------------
   public void swap(int dex1, int dex2)  // swap two elements
      {
      long temp = theArray[dex1];        // A into temp
      theArray[dex1] = theArray[dex2];   // B into A
      theArray[dex2] = temp;             // temp into B
      }  // end swap(
//--------------------------------------------------------------
   }  // end class ArrayIns
////////////////////////////////////////////////////////////////
class QuickSort1App
   {
   public static void main(String[] args)
      {
      int maxSize = 16;             // array size
      ArrayIns arr;
      arr = new ArrayIns(maxSize);  // create array
  for(int j=0; j<maxSize; j++)  // fill array with
     {                          // random numbers
     long n = (int)(java.lang.Math.random()*99);
     arr.insert(n);
     }
  arr.display();                // display items
  arr.quickSort();              // quicksort them
  arr.display();                // display them again
  }  // end main()    }  // end class QuickSort1App ////////////////////////////////////////////////////////////////
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

partition

A
////////////////////////////////////////////////////////////////
class ArrayPar
   {
   private long[] theArray;          // ref to array theArray
   private int nElems;               // number of data items
//--------------------------------------------------------------
   public ArrayPar(int max)          // constructor
      {
      theArray = new long[max];      // create the array
      nElems = 0;                    // no items yet
      }
//--------------------------------------------------------------
   public void insert(long value)    // put element into array
      {
      theArray[nElems] = value;      // insert it
      nElems++;                      // increment size
      }
//--------------------------------------------------------------
   public int size()                 // return number of items
      { return nElems; }
//--------------------------------------------------------------
   public void display()             // displays array contents
      {
      System.out.print("A=");
      for(int j=0; j< right &&       // find bigger item
                theArray[++leftPtr] < pivot)
             ;  // (nop)
          while(rightPtr > left &&       // find smaller item
                theArray[--rightPtr] > pivot)
             ;  // (nop)
          if(leftPtr >= rightPtr)        // if pointers cross,
             break;                      //    partition done
          else                           // not crossed, so
             swap(leftPtr, rightPtr);    //    swap elements
          }  // end while(true)
       return leftPtr;                   // return partition
       }  // end partitionIt()
//--------------------------------------------------------------
   public void swap(int dex1, int dex2)  // swap two elements
      {
      long temp;
      temp = theArray[dex1];             // A into temp
      theArray[dex1] = theArray[dex2];   // B into A
      theArray[dex2] = temp;             // temp into B
      }  // end swap()
//--------------------------------------------------------------
   }  // end class ArrayPar
////////////////////////////////////////////////////////////////
class PartitionApp
   {
   public static void main(String[] args)
      {
      int maxSize = 16;             // array size
      ArrayPar arr;                 // reference to array
      arr = new ArrayPar(maxSize);  // create the array
      for(int j=0; j + partDex);
      arr.display();                // display partitioned array
      }  // end main()
   }  // end class PartitionApp
////////////////////////////////////////////////////////////////
How well did you know this?
1
Not at all
2
3
4
5
Perfectly