×

### Let's log you in.

or

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

×

or

by: Nick

7

0

3

# CS 2420 Class Notes Week 4 CS 2420

Marketplace > University of Utah > Computer science > CS 2420 > CS 2420 Class Notes Week 4
Nick
The U
GPA 3.78

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

×
Unlock Preview

Sorting algorithms: selection sort, insertion sort, shell sort, bubble sort
COURSE
Intro Algorithms and Data Structures
PROF.
Miriah Meyer
TYPE
Class Notes
PAGES
3
WORDS
CONCEPTS
Computer Science, Sorting Algorithms
KARMA
25 ?

## Popular in Computer science

This 3 page Class Notes was uploaded by Nick on Friday September 16, 2016. The Class Notes belongs to CS 2420 at University of Utah taught by Miriah Meyer in Fall 2016. Since its upload, it has received 7 views. For similar materials see Intro Algorithms and Data Structures in Computer science at University of Utah.

×

## Reviews for CS 2420 Class Notes Week 4

×

×

### 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: 09/16/16
CS 2420 9-12-16 submit code together time code together, write up separate Don’t copy yourself if took the class previously. If you use it, make sure GitHub is private! algorithm analysis programs now need to terminate in a reasonable amount of time. so choose the right algorithm. Binary search reduces search space by half each time how find the complexity of code: asymptotic behavior is what happens when the limit of the function goes to infinity worst case- commonly used, easy to get average case: challenging to compute best case: not used much whenever see doubling or halving, it will be a logN smallest difference between two arrays binary search complexity log N adding to the array is complexity of 1 because it only adds one element grow function is complexity N because it loops over each item and copies to the new array remove is complexity N in best and worst case sorting is used everywhere in computer science easy sorting run in quadratic time more complicated algorithms run in NlogN selection sort - (simplest) find minimum item and swap with beginning, and then repeat on unsorted portion of the array. inner loop complexity is a sum Gouse’s trick: 1+2+3+4+5+ 10+9+8+7+6 =11+11+11+... answer: ((n-1)^2+(n-1))/2 = (n^2-n)/2 best, and worst cases are the same because never terminates early insertion sort- best case complexity is N the more unsorted an array the more work is needed. Its complexity is O(N+I) worst is when reverse sorted. Gauss’s trick: (n^2+n)/2 average is half of worst case, and complexity is still N^2 insertion sort is better than selection sort because sometimes it is better. bubble sort -- 9-14-16 there is a short homework due before Lab Friday. make sure running Java 8 on own machine Ryan has office hours at 630pm average 10-15 hours for assignment 3 selection sort is known as the simplest kind of sort insertion sort is good for small N it’s measure of unsortedness is the number of inversions Each swap removes one inversion O(N+I) need to remove more than one inversion in each step what if consider swaping non-adjacent items shell Sort known as the smallest sub quadratic algorithm set gap size to N/2 considder subarrays with elements at gap size from each other do insertion sort on each of the subarrays divide the gap size by 2 repreat steps 2-4 until the gap size is < 1 insertion sort is a specific case of shellSort (gap size of 1) invented by shell also called diminishing gap sort the compexity of the best case is NlogN insertion sort performs better the more sorted the array, more than shellSort this is good for small to medium N when use log N thought of as divide and conquer bubble sort usually the most inefficient sort (worst) fo each item, compare i ti its next neighbor ad swap if ecessary repeat untill sorted the largest finds its final position after the first iteration. They ‘bubble’ up to the top the best and worst case are the same complexity, because can’t escapt early. if don’t do any swaps then it is in order and can optimize to break out early. but, best case almost never happens it is an algoritm of rabbits and turtles large numbers move fast variations try to remove the turtiles cocktail sort: start to end then end to start comb sort: diminishing gap fr compareing pairs of items remove more than one inversion at once.

×

×

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

Bentley McCaw University of Florida

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

Anthony Lee UC Santa Barbara

#### "I bought an awesome study guide, which helped me get an A in my Math 34B class this quarter!"

Bentley McCaw University of Florida

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

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