### Create a StudySoup account

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

Already have a StudySoup account? Login here

# Week 10 Notes CSC 2310

GSU

GPA 4.21

### View Full Document

## 9

## 0

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

## Reviews for Week 10 Notes

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

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

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

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