Sorting algorithms- Selection sort, Quick sort, Merge sort, and Efficiency.

Selection sort algorithm

To execute selection sort, we firstly need to look for smallest item in the list and switch with the current index that we stand on. We read over the index from 0 to length of list – 1. We call the initial state of list is unsorted list that contains no sorted part. While processing the sort, the list becomes sorted from the first to the end. Here, the sorted part is at the index less than the current index, and the unsorted part is at the index greater or equal to the current index. Whenever we find the smallest value from the unsorted part, we switch that smallest value with the current value.

Quick sort algorithm

Firstly, we let item at index 0 in a given list be pivot, and look for items less than pivot and put them before the pivot, and also look for items greater or equal to pivot and put them after the pivot. Once we do this step, list is slightly sorted but not perfectly, so we separate it into two parts (one is left side of pivot and the other is right side). Then, we use recursion to repeat these steps for left and right. After finishing all recursion, the list must be sorted.

Merge sort algorithm

We continuously split the given list into left and right where one refers to first half of list and the other has last half until the list becomes length of one. Of course, these repeating steps should be done by recursion. Then when left and right reach the length of one, we start to compare these two to sort. For comparison, starting from index 0 of left and also index 0 of right, we append one of left item and right item to the new list, and when once we append the item, we need to increase the value of index of left or right that currently we read over. For example, if we append the item at index 0 from left to the new list, we increase the index of left by 1, but index of right must stay at index 0 since item at index 0 has not been appended yet. Then, when one of index of left and right becomes length of the corresponding list, we stop comparing and then append all item that is left over in left and right. These steps are all done by recursion, and after it totally ends, list is finally sorted.

Efficiency

In python, one of possible cases to code in efficient way is memoization. In the lecture, it is introduced by Fibonacci number. There is a nested function which has the outer function and the inner function, and the inner function is used in the outer function. When we execute the recursion in the inner function and also record the data of value came from any calculations done during recursion running, we no more need to repeat the calculations that we have done before since we already recorded that calculation in the dictionary. It means that we can simply recall the result of calculation from dictionary by giving the keys. This kind of work decreases running time since there is no repetition anymore.

Week 12- weekly post

This week’s topics were memory model, tracing, and consequences of recursion.

When searching for the names in python, it looks in order of innermost scope (local), enclosing scopes (non-local), global, and built-in names.

When tracing, we are recommended to trace the non-recursive case and then trace the next-most complex case.

Fibonacci number is introduced to apply in to show how to avoid redundant calls. We create another function inside of function, and inner function is recursive to collect Fibonacci- appropriate number (key-value) pair in dictionary created in outer function. This is useful for minimizing repeating steps that look for same value twice or more times. This is called memorization.

Finally in the lecture, professor Heap described the quicksort, one of fast sorting function we already have seen in lab 9. First quicksort just starts with index 0, and use recursion to collect numbers less than item at index 0 and item at index 0 and then numbers greater than or equal to item at index 0. In second quicksort function, we pick a random number to do the same steps as first quicksort but using that random number instead of index 0 item (number).

In a final lab, we use a single list which must represent the complete binary tree. Instead of using BTNode class, we only use a single list to execute the several methods.

Week 11

This week's topic was hiding attributes, equality and reduce.  I learned a built-in function, property that introduces how to do the hiding attribute and how to build property function to make it as read-only form.
Also, I learned __eq__ function. This function is used as class method to know whether two or more objects are equivalent or not.
Reduce is used when we want to get a single value from the nested list by reducing lists from inside to outside.
In lab, I and my partner a bit changes the given code to evaluate the time analysis of the various sort functions. We figured out that the built-in sort is fastest sort function, and bubble sort is one of slowest function for many items contained in list. However, when sorted, insertion took a similar time as tried in random list. This is because when sort functions try to sort the sorted list, the time analysis is dependent on how many compare statement has been executed. Lastly, for sorted and reversed list, again the bubble sort is slowest one because the bubble sort has to compare and switch the items for number of item in list times.

Week 8 - Weekly post

In this week, I started my assignment 2 alone, and I'm still figuring out how to do.
In the lectures of this week, I learned about time efficiency, how to program in the best way that takes the lowest time.
For exercise 6, as I code this, I learned how to transfer the recursion code to the loop code, and then in lab, I coded two types of recursion and transfer this code to the loop.
Now, on Sunday, I'm still working on assignment 2.

Week 7 - weekly post

I learned the application of recursion, linked list in this week’s lecture. On Wednesday, I tried the exercise 5 but stuck in part (a) temporarily. After looking at discussion forum, I realized that I misunderstood the handout. Then, soon I figured out how to code the recursion in the class and how to apply it to the type, list. Because in the previous week, I already learned about a binary tree so that I could code exercise 5 easily this time after I fully well understood the instruction on the handout. In lab, with my partner, I worked with linked list for the entire 2 hours. We felt the instruction was not clear, so we stuck in part (a) of lab handout. However, by calling the help from TA, we could successfully finish the lab. 

  In this week, it was good to know more about recursion because in my head, the recursion was a little bit not clear before doing this week’s exercise and lab.

SLOG topic, by October 14th

Topic: The object-oriented programming, recursion.

As the computer technology becomes complex, the programming becomes complex, too. For the computer scientists, it is getting harder to implement the program from the very detail. The object-oriented programming is an important type of programming to solve this complexity of the program. The programmers, instead of knowing the details of the program, abstract the image or the idea how to make the program works in the real world. It does not require the programmers to know the details so that it is much easier to develop the programs.

The recursion is an important concept for the programming. When the programmers develop the programs, they might use the repeated codes to do the repeated works. Instead of making the codes complex, they can create the recursive function to do these repeated works. The recursive function simplifies the codes and does the equivalent works. Moreover, when the other programmers try to understand the codes, instead of reading the long repeated code, it is much easier to understand one recursive function and how the program works.

Preview