Week 11: Sorting and Efficiency

     In programming we are always looking for the most efficient way to execute a program. Simply by discarding other variables such as hardware, programming language and other random events, we would like to analyze how a specific algorithim performs given the size of the input. If we define the size of the input as n, and our algorithm as f(n), this will run no more than cg(n) (for some constant c) which we will call O(g(n)). This notation known as big-oh gives an upper-bound that explains the algorithm running time at most depending on the size of the input . It is also important to note that because we are looking at how an algorithm scales depending on n, a relatively large input will allow us to ignore the constants. For example, one program that runs in 5n^2 + 4^n + 3, we will call that O(n^2). Different algorithms have different runtimes which in turn can be categorized by it function's growth. A slower growth (which is good) means that an algorithm will take less additional time given by input n. A constant runtime will complete its task regardless of how large the input is, while a exponential runtime increases horrendously fast (which is bad).

   By the establishing a good knowledge of big-oh, we can determine how different sorting algorithms perform against each other. In the case of this class, sorting deals with unique integers in a list and ordering them from smallest to largest. I will be analyzing quick sort, merge source and insertion sort which are all common sorting algorithims used today.

Quick Sort
      The initial step of quick sort is to retrieve a pivot that enables the list to have integers that have smaller values than the pivot on the left and integers that have larger values on the right of the list. Those two smaller partitions will then have their own pivots and the process repeats itself until each partition becomes a single integer element. If all goes correctly and a proper pivot is selected, the average case run time will be O(nlogn). This can be justified because it takes n times to sort each partitioned list and it takes logn to split the list into smaller sizes (divide and conquer idea).

Merge Sort
     Merge sort can be thought of very similarly to how quick sort functions. However, each element in the list will be thought of as their own sorted list. We merge two pairs of list together by checking each index of the list in contrast to the other. This is done until a single list is created after merging recursive pairs of the lists. Similarly, merge sort also has O(nlogn) behaviour.

Insertion Sort
     In insertion sort we treat the list as having a sorted section on left and unsorted section on the right. The first element of the list will be considered sorted and we will iterate through the list and compare the unsorted elements to the sorted elements. If the unsorted element is larger than the sorted element at the end of the list, we will leave that element to be at that position. However if it is smaller, we will check each element of the sorted section to see where the unsorted elements fits in. Once the sorting process has been completed, the sorted section of the list will be the length of the total list moving from left to right. The average case run time of insertion sort is O(n^2) because it iterates through the list of unsorted elements and iterating through the sorted portion of the list placing the unsorted element. If the list is already sorted, the time complexity of insertion sort will be O(n) because all elements are already in it's proper place.

Week 8: Linked List and Assignment 2

This week we focused more on LinkedList and the general functionalities of the wrapper classes. In our new LinkedList class, we implemented a new LListNode class that allows for better implementation of nodes. By doing so, it made it easier for us to delete, reverse and insert new values for our LinkedList by using the attributes of LListNode. Assignment 2 part one was also extended to Sunday, but luckily I had already finished before the due date. The first part of A2 was pretty straight forward going over the topics of classes and inheritance.