User Tools

Site Tools


journal:fall2019:mgardne8:week5

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

journal:fall2019:mgardne8:week5 [2019/09/12 06:53]
127.0.0.1 external edit
journal:fall2019:mgardne8:week5 [2019/09/18 19:31] (current)
mgardne8
Line 1: Line 1:
 =====data week5===== =====data week5=====
----- +====SEPTEMBER 182019====
-====MONTH DayYEAR====+
  
 Filler text- your entry goes here; remove this line to receive full credit. Filler text- your entry goes here; remove this line to receive full credit.
 +== WDIDTW ==
 +What Did I Do This Week?
 +    - PCT4.
 +Yes, that's it, I'm sorry.
  
 +== Future improvements ==
 +This is going to be a running list of improvements I plan to make in the future, if our projects allows.
 +
 +   - Improve setpos function
 +      - depends on dll implementation.
 +      - instead of iterating from the start of the list, instead determin if it's more efficient to start at the front or the end of the list
 +      - contingent on if our list implementation will also track the running size of our list, otherwise may not be a fesible optimization if we have to parse the list to get it's length.
 +   - Implement a more efficient sorting function
 +      - bubblesort is an easy impelmentation
 +      - Quicksort looks fun, and realtivly simple to implement, I will most likely attempt this.
 +      - Recursive Bubble sort looks like a neat way to have a tiny tiny solution
 +
 +== On sorting ==
 +What sorting methods exist, what ones fit our use case, and are they efficiently implemented?​
 +
 +== Bubble sort ==
 +Bubble sort sorts a list simply by iterating through it's elements (nodes) and switching them if the first node is larger than the second (or the inverse depending on what direction you are sorting)
 +Best: O(n^2)
 +Worst: O(n^2)
 +Pros: Simple, can be implemented in less than 10 lines.
 +Cons: Always O(n^2) regardless of order of list, even if it's already sorted.
 +
 +== Modified Bubble sort ==
 +Bubble sort containing a flag that is modified when a change is made, if no change is made (list is sorted!) don't do more loops.
 +best: O(n)
 +Worst: O(n^2)
 +Pros: Stops as soon as the list is sorted
 +Cons: worst case still O(n^2)
 +
 +== Selection Sort == 
 +sets an index to the first object, moves the smallest object to that position, then moves to the next position and finds the next smallest, <this continutes until the list is sorted>
 +Best:  O(n^2)
 +Worst: O(n^2)
 +Pros: size of iterations shrink as list is sorted
 +Cons: always o(n^2) regardless of order of list, even if it's already sorted. (same as bubble sort)
 +
 +== Quick Sort ==
 +Quicksort divides and conquer'​s a list elements while sorting.
 +   - A node within the list list is chosen, this is the pivot
 +   ​- ​ all elements lower are placed on left side of the pivot, and larger elements are placed on the right. (in no order) (similar elements can be placed on either side)
 +      - At this point, the pivot is in it's correct location
 +   - the list on each side of the pivot, (up to, but not including the pivot) is then recurivly sent to it's own quicksort
 +      - A list of zero or one nodes is considered sorted
 +Best: O(n*log(n))
 +Worst:​O(n^2)
 +Pros: very quick to sort a list assuming it's not in it's worst case state. (reverse sorted)
 +Cons: A bit more complex to implement.
journal/fall2019/mgardne8/week5.txt · Last modified: 2019/09/18 19:31 by mgardne8