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 ////////////////////////////////////////////////////////////////
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 ////////////////////////////////////////////////////////////////
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 ////////////////////////////////////////////////////////////////
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 ////////////////////////////////////////////////////////////////
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
////////////////////////////////////////////////////////////////
