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

Week 10 Notes

by: Taylor Kahl

Week 10 Notes CSC 2310

Taylor Kahl
GPA 4.21

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

Notes from lectures 3/21 and 3/23, about searching and sorting methods.
Princliples of Computer Programming
Kebina Manandhar
Class Notes
25 ?




Popular in Princliples of Computer Programming

Popular in ComputerScienence

This 7 page Class Notes was uploaded by Taylor Kahl on Wednesday March 23, 2016. The Class Notes belongs to CSC 2310 at Georgia State University taught by Kebina Manandhar in Winter 2016. Since its upload, it has received 9 views. For similar materials see Princliples of Computer Programming in ComputerScienence at Georgia State University.

Similar to CSC 2310 at GSU

Popular in ComputerScienence


Reviews for Week 10 Notes


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: 03/23/16
 Sorting – rearranging elements of a collection in natural order o for numbers, from least to greatest o for Strings, alphabetically  Comparison-based sorting – ordering by comparing pairs of elements o Examples: < or > for primitive data types; compareTo for objects  Arrays & Collections have a static method sort o using these methods requires importing the java.util package (import java.util.*;) o Arrays.sort(name); o Collections.sort(name);  remember that this one can be used for ArrayLists  but only for ArrayLists of a type from a class that implements the Comparable interface  because the sort method requires being able to compare objects  Other methods in the Collections class: copy(listTo, listFrom) copies listFrom’s elements to listTo emptyList(); emptyMap(); emptySet() returns a read-only collection of the given type that has no elements fill(list, value) sets every element in a list to the given value max(collection); min(collection) returns the largest element; returns the smallest element replaceAll(list, old, new) replaces every occurrence of the old value with the new one reverse(list) reverses the order of elements shuffle(list) randomly shuffles elements  There are different algorithms for sorting, some more efficient than others:  Bogo sort – repeatedly shuffles a list and checks if it’s sorted o check if list is sorted; if so, stop o else, shuffle & repeat  terrible efficiency! No upper limit to how long it could take public static void bogoSort(int[] a) { while (!isSorted(a)) { //while a is not sorted shuffle(a); //calls shuffle } } public static boolean isSorted(int[] a) { for (int i = 0; i < a.length; i++) { if (a[i] > a[i +1]) { //if 2 adjacent elements are unordered return false; } } return true; //all elements are ordered } public static void shuffle(int[] a) { //randomly swaps elements for (inti = 0; i < a.length; i++) { int range = a.length -1 – (i + 1) + 1; int j = (int) (Math.random() * range + (i + 1); swap(a, i, j); //calls swap } } public static void swap(int[] a, int i, int j) { if (i != j) { int temp = a[i]; a[i] = a[j]; a[j] = temp; }  Selection sort – searches list for smallest (or largest) element, then puts it first (or last), then moves on to the second smallest (or largest) o search list for smallest value o swap it with the value at index 0  search for the next smallest value  swap it for the value at index 1. And so on public static void selectionSort(int[] a) { for (int i = 0; i < a.length - 1; i++) { //”a.length-1” bc this compares i to i + 1 int min = i; //the index of the minimum value, 1st assigned to 0 for (int j = i + 1; j < a.length; j++) { if (a[j] < a[min]) { min = j; //new index of minimum value } } swap(a, i, min); //swaps a[i] with a[min] } } o What is this algorithm’s complexity c2ass?  for loop within a for loop = O(N ) o Another way to think of it: how many comparisons need to be made? 1 comparison, then 2, then 3…all the way to N comparisons  How can we find the sum of comparisons to be made? S=1+2+3+…N−2+N−1+N This can also be written as: S=N+N−1+N−2+…3+2+1 If we add those 2 equations we get: 2 S=N+1+N +1+N+1+…N+1+N+1+N+1 So 2S = N+1 added together N times 2S=N(N+1) S= N (N+1 ) 2 The largest order of N will be N , so this algorithm is O(N ). Remember, big-oh notation only cares about the order (exponent) of N, not the coefficients  Bubble sort – compare every adjacent pair, swapping if they’re in the wrong order o run through the list again and swap pairs until it’s ordered o slower than selection sorting because it requires more comparisons o Also O(N )  if the smallest element were at the end, the code will have to run through the list N-1 times to swap it all the way to the beginning.  each time it runs through the list, it makes N-1 comparisons  (N-1)*(N-1) o Example: int[] a = {7, 3, 0, 1, 9}  {3, 7, 0, 1, 9}  {3, 0, 7, 1, 9}  {3, 0, 1, 7, 9}  {0, 3, 1, 7, 9}  {0, 1, 3, 7, 9} public static void bubbleSort(int[] a) { for (int i=0; i< a.length-1; i++) { //go through the list N-1 times for (int j=0; j<a.length-1; j++) {//for N-1 elements if (a[j]>a[j+1]) { //compare it to the next element; swap if needed int temp=a[j]; a[j]=a[j+1]; a[j+1]=temp; } } } }  Insertion sort – go through elements 1 at a time o When you reach an element that is less than the one before it, swap them. Then, compare the smaller element to every element that comes before it in the list, swapping with larger elements until it’s in its final spot o faster than selection sort  instead of comparing each element to the entire list, you only compare it to the beginning of the list, which is already sorted 2 o Also O(N ) o Example: int[] a = {7, 3, 0, 1, 9}  3<7. {3, 7, 0, 1, 9}  0<3 & 0<7. {0, 3, 7, 1, 9}  1<7 & 1<3. {0, 1, 3, 7, 9} public static void insertionSort(int[] a) { for (int i=0; i<a.length-1; i++) { //go through N-1 elements for (int j=i; j>=0; j--) { //go through the elements that come before a[i] if (a[j]>a[j+1]) { int temp=a[j]; a[j]=a[j+1]; a[j+1]=temp; } } } }  Merge sort – repeatedly divide the list in half, sort each half, and combine the sorted halves o implemented recursively  divide by half until each half has 1 element  go back and combine the halves o Example: int[] a = {2, 4, 5, 3, 7, 1, 9, 6} {2, 4, 5, 3} {7, 1, 9, 6} {2, 4}{5, 3} {7, 1} {9, 6} {2} {4} {5} {3} {7} {1} {9} {6} {2, 4}{3, 5} {1, 7} {6, 9} {2, 3, 4, 5} {1, 6, 7, 9} {1, 2, 3, 4, 5, 6, 7, 9} o O(Nlog 2)  N comparisons each time the halves are merged  2 = N  x divisions by 2 necessary to get from N to 1  x = log 2 public static void merge(int[] result, int[] left, int[] right) { int i1=0; //i1 keeps track of the index of the left half int i2=0; //i2 keeps track of the index of the right half for (int i=0; i<result.length; i++) { if (i2>=right.length|| i1<left.length&&left[i1]<=right[i2]) { //if i2 has exceeded the # of indexes in right OR i1 has not exceeded the last index in left AND the element at i1 < the one at i2 result[i]=left[i1]; i1++; } else { result[i]=right[i2]; i2++; // the next element will be assigned the next smallest value in either left or right. If an element is copied from left, i1 is incremented. If it’s copied from right, i2 is incremented } } } public static void mergeSort(int[] a) { if (a.length>=2) { //at least 2 elements in array; need to be divided int[] left=Arrays.copyOfRange(a, 0, a.length/2); int[] right=Arrays.copyOfRange(a, a.length/2, a.length); mergeSort(left); //divide again mergeSort(right); merge(a, left, right); //this will merge the halves } }


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

Jim McGreen Ohio University

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

Kyle Maynard Purdue

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

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.