journal:fall2019:mgardne8:week5

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

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 18, 2019==== |

- | ====MONTH Day, YEAR==== | + | |

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

Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution-Share Alike 4.0 International