### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Computer Science II CIS 162

Central Oregon Community College

GPA 3.73

### View Full Document

## 10

## 0

## Popular in Course

## Popular in Computer Information Systems

This 6 page Class Notes was uploaded by Jamir Treutel on Monday October 5, 2015. The Class Notes belongs to CIS 162 at Central Oregon Community College taught by Peter Casey in Fall. Since its upload, it has received 10 views. For similar materials see /class/218972/cis-162-central-oregon-community-college in Computer Information Systems at Central Oregon Community College.

## Similar to CIS 162 at Central Oregon Community College

## Reviews for Computer Science II

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/05/15

A class that contains several sorting routines implemented as static methods Arrays are rearranged with smallest item first using compares author Mark Allen Weiss public final class Sort kk Simple insertion sort param a an array of Comparable items public static void insertionSort Comparable l a for int p 7 l p lt alength p Comparable tmp a p 1 int j p for j gt O ampamp tmpcompareTo a j l lt O 3 a j l a j 1 l a j l tmp Shellsort using a sequence suggested by Gonnet param a an array of Comparable items public static void shellsort Comparable l a for int gap alength 2 gap gt 0 gap gap l int gap 22 for int i gap i lt alength i Comparable tmp int j 39 7 a i l l for j gt gap ampamp tmpcompareTo a j gap lt 0 j 7 a j l a j gap 1 a j l gap tmp Standard heapsort param a an array of Comparable items public static void heapsort Comparable a for int i i 7 alength 2 i gt O i buildHeap percDown a i alength for int i alength l i gt O i swapReferences a O i percDown a O deleteMax i Internal method for heapsort param i the index of an item in the heap return the index of the left child private static int leftChild int i return 2 i l k k Internal method for heapsort that is used in deleteMax and buildHea param a an array of Comparable items index i the position from which to percolate down int n the logical size of the binary heap private static void percDown Comparable a int i int n int child Comparable tmp for tmp a i leftChild i lt n i 7 child child 7 leftChild i if child l n l ampamp a child compareTo a child l child lt O lf tmpcompareTo a child lt O a i a child else break a l tmp k k Mergesort algorithm param a an array of Comparable items public static void mergeSort Comparable a Comparable tmpArray new Comparable alength mergeSort a tmpArray O alength l kk Internal method that makes recursive calls param a an array of Comparable items param tmpArray an array to place the merged result param left the left most index of the subarray param right the right most index of the subarray private static void mergeSort Comparable a Comparable tmpArray int left int right if left lt right int center left right 2 mergeSort a tmpArray left center mergeSort a tmpArray center 1 right merge a tmpArray left center l right k k Internal method that merges two sorted halves of a subarray param a an array of Comparable items param tmpArray an array to place the merged result param leftPos the left most index of the subarray param rightPos the index of the start of the second half param rightEnd the right most index of the subarray private static void merge Comparable a Comparable int leftPos int rightPos int leftEnd rightPos 1 int tmpPos leftPos int numElements tmpArray int rightEnd 7 rightEnd leftPos l Main loop while leftPos lt leftEnd ampamp rightPos lt rightEnd if a leftPos compareTo a rightPos lt O tmpArray tmpPos a leftPos else tmpArray tmpPos i 7 a rightPos while leftPos lt leftEnd Copy rest of first half tmpArray tmpPos a leftPos while rightPos lt rightEnd Copy rest of right half tmpArray tmpPos a rightPos Copy tmpArray back for int i i lt numElements a rightEnd i rightEnd tmpArray rightEnd kk Quicksort algorithm param a an array of Comparable items public static void quicksort Comparable a quicksort a O alength l private static final int CUTOFF lO kk Method to swap to param a an array param indexl the param index2 the k elements in an array of objects index of the first object index of the second object public static final void swapReferences Object a int indexl int index2 a indexl a index2 a index2 tmp Object tmp a indexl Internal quicksort method that makes recursive calls Uses median of three partitioning and a cutoff of 10 param a an array of Comparable items param low the left most index of the subarray param high the right most index of the subarray private static void guicksort Comparable a int low int high if low CUTOFF gt high insertionSort a low high else Sort low middle high int middle low high 2 if a middle compareTo a low lt O swapReferences a low middle if a high compareTo a low lt O swapReferences a low high if a high compareTo a middle lt O swapReferences a middle high Place pivot at position high l swapReferences a middle high l Comparable pivot a high l Begin partitioning int i j for i low j high l while a i compareTo pivot lt 0 while pivotcompareTo a j lt 0 if i gt j break swapReferences a i j Restore pivot swapReferences a i high l guicksort a low i l Sort small elements guicksort a i 1 high Sort large elements kk Internal insertion sort routine for subarrays that is used by quicksort param a an array of Comparable items param low the left most index of the subarray param n the number of items to sort private static void insertionSort Comparable a int low int high for int p low 1 p lt high p Comparable tmp a p int j for p j gt low ampamp tmpcompareTo a j l lt 0 j j a j l al 3 l l kk Quick selection algorithm Places the kth smallest item in ak l param a an array of Comparable items param k the desired rank 1 is minimum in the entire array public static void quickSelect Comparable a int k quickSelect a O alength l k kk Internal selection method that makes recursive calls Uses median of three partitioning and a cutoff of 10 Places the kth smallest item in ak l param a an array of Comparable items param low the left most index of the subarray param high the right most index of the subarray param k the desired rank 1 is minimum in the entire array private static void quickSelect Comparable a int low int high int k if low CUTOFF gt high insertionSort a low high else Sort low middle high int middle low high 2 if a middle compareTo a low lt O swapReferences a low middle if a high compareTo a low lt O swapReferences a low high if a high compareTo a middle lt O swapReferences a middle high Place pivot at position high l swapReferences a middle high l Comparable pivot a high l Begin partitioning int i j for i low j high l while a i compareTo pivot lt 0 while pivotcompareTo a j lt 0 if i gt j swapReferences a i j Restore pivot swapReferences a i high l Recurse only this part changes if klti quickSelect a low i l k else if k gt i l quickSelect a i 1 high k

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "When you're taking detailed notes and trying to help everyone else out in the class, it really helps you learn and understand the material...plus I made $280 on my first study guide!"

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.