×

### Let's log you in.

or

Don't have a StudySoup account? Create one here!

×

or

## PRINCIPLES OF OBJECT

by: Cleora Stiedemann

14

0

3

# PRINCIPLES OF OBJECT COMP 202

Marketplace > Rice University > ComputerScienence > COMP 202 > PRINCIPLES OF OBJECT
Cleora Stiedemann
Rice University
GPA 3.72

Staff

These notes were just uploaded, and will be ready to view shortly.

Either way, we'll remind you when they're ready :)

Get a free preview of these Notes, just enter your email below.

×
Unlock Preview

COURSE
PROF.
Staff
TYPE
Class Notes
PAGES
3
WORDS
KARMA
25 ?

## Popular in ComputerScienence

This 3 page Class Notes was uploaded by Cleora Stiedemann on Monday October 19, 2015. The Class Notes belongs to COMP 202 at Rice University taught by Staff in Fall. Since its upload, it has received 14 views. For similar materials see /class/224962/comp-202-rice-university in ComputerScienence at Rice University.

×

## Reviews for PRINCIPLES OF OBJECT

×

×

### What is Karma?

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

Date Created: 10/19/15
ObjectOriented Sorting Dung Zung Nguyen Stephen B Wong Dept of Computer Science Rice University Houston TX 77251 ggguyen csriceedu swong csriceedu Figure 1 below shows the recursive call tree for the sort method of a hypothetical sort algorithm unsorted sorted Figure 1 Hypothetical Sort Recursion Tree sort process Table 1 below summarizes the splitjoin operations of a few common sort algorithms Sort Split operation Join operation Insertion Return hi InserTAvn Into pmper locatron Merge Return midpoint index Merge subarrays Quick Find and return pivot point index Do nothing Selection Swap extremum withAhi and return hi Do nothing Bubble Bubble up extremum t0 Ahi and return hi Do nothing Heap Swap extremum Alo andAhi reheap1fyAlo hi l Do nothing and return hi Table 1 Concrete splitjoin Operations From Table 1 we can see that selection sort bubble sort and heap sort1 are essentially identical processes though they have different algorithmic complexities they all pull out the extremum from the array and split it off A trivial noop join then follows this Quick sort is similar to the selectionbubbleheap genera except that it pulls off a set of one or more extrema values On the ip side of the coin we see that insertion sort and merge sort are similar in that their split operations are trivial while their join operations are more complex Insertion splits off one element at a time while merge sort splits the array in half each time One can think of the join method in insertion sort as merging a sorted array with a oneelement array which is obviously sorted 1 Heap sort heapifies the array only once at construction time Complexity Analysis On one hand the sort template method engenders a recursion tree see Figure 1 which provides some heuristics on the sort complexity On the other hand it leads to a canonical recurrence relation that serves as a common starting point for the analysis of each of the concrete sort algorithms It is easy to see from Figure 1 that the total running time of a sort is equal to the sum of the running time of each level of the recursion sort tree If the running time at each level is uniformly bounded by some function n then the total running time is bounded by n times the height of the sort tree A formal treatment of complexity involves deriving a recurrence relation for Tlo hi the running time to sort an arrayAlohi indexed from lo to hi with lo lt hi The code for SOI t clearly indicates that R1 T hic lflh c saw Tls l Tsh JLsh1fl lth where c is the constant running time to compare lo with hi S o hi is the running time to split A into two subarrays Alosl and As hi and Jlo 3 hi is the running time for joining the two sorted subarrays Alosl andAshi to form the sorted arrayAlohi It is necessary to examine the code for the speci c Split and join methods of a particular sort algorithm to compute Slo hi and J 10 3 hi in order to solve R1 Let n denote the size of the array The steps in the computation of Tn are identical for all of the sort algorithms start with the canonical relation R1 plug in the values for s Slo hi and J 10 3 hi and simplify Note that the functional form of 3 may depend on whether one sorts from lo to hi or hi to lo The simplification will lead to one of the following two recurrence relations 01 ifn 1 R2 Tm Tnl 0 if n gt1 01 ifn 1 R339 Tm hime Ofn ifn gt1 R2 and R3 can then be solved using the same standard discrete mathematics technique yielding the results shown in Table 2 below worst case Selection Heap 39 Ologhilo Ol On log n Table 2 Running Time for Sorting

×

×

### BOOM! Enjoy Your Free Notes!

×

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

Steve Martinelli UC Los Angeles

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

Allison Fischer University of Alabama

#### "I signed up to be an Elite Notetaker with 2 of my sorority sisters this semester. We just posted our notes weekly and were each making over \$600 per month. I LOVE StudySoup!"

Steve Martinelli UC Los Angeles

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

Parker Thompson 500 Startups

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

Become an Elite Notetaker and start selling your notes online!
×

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