New User Special Price Expires in

Let's log you in.

Sign in with Facebook


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


Create a StudySoup account

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

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here

CS 2420 Class Notes Week 4

by: Nick

CS 2420 Class Notes Week 4 CS 2420

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

Preview These Notes for FREE

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

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Sorting algorithms: selection sort, insertion sort, shell sort, bubble sort
Intro Algorithms and Data Structures
Miriah Meyer
Class Notes
Computer Science, Sorting Algorithms
25 ?




Popular in Intro Algorithms and Data Structures

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.

Similar to CS 2420 at The U


Reviews for CS 2420 Class Notes Week 4


Report this Material


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: 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.


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

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

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


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


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:

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

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.