Sorting and Efficiency

This is my entry on sorting and efficiency. Sorting refers to any type of algorithm/function that can be used to order the elements of a list or some other kind of data structure. We normally consider the efficiency of a sorting algorithm by how many calls the algorithm will make in the worst case scenario. The efficiency of different types of algorithms are categorized by "big Oh", for example O(n^2) would mean that in the worst case scenario the algorithm will have to make some constant multiplied by n^2 calls in order to sort n elements. Below are some of the main sort algorithms we have used specifically on lists and their efficiency.

Selection sort: Searches through the entire unsorted section of the list to find the smallest element, and moves it to the end of the sorted part of the list (efficiency is O(n^2))
Insertion sort: Sorts the list by moving the next element in the unsorted portion of the list to the appropriate place in the sorted part of the list (efficiency is O(n^2))
Bubble sort: Repeatedly searches through the entire list and swaps the position of adjacent elements that are not in the correct order (efficiency is O(n^2))
Merge sort: Recursively splits the list into halves, then sorts the halves and merges them back together (efficiency is O(nlog(n)))
Quicksort: Partitions the list into two halves where one half is smaller than the first element and the other half is greater than the first element, then puts the first element in between these two partitions and repeats the same process for the two partitioned lists (efficiency is O(nlog(n)))
We also talked briefly about python's built in sorting system list.sort(). This is the fastest of all sorting algorithms, but it is still of order O(nlog(n)) as this is the most efficient that it is possible for a sorting algorithm to be.

Recursion

This is my week 7 SLOG entry, on the topic of recursion. In computer science, recursion is essentially writing methods/functions that complete a task by calling on themselves a finite number of times. Whenever you write a recursive function it is essential to have what is called a "base case . A base case is essentially an iteration of a recursive function that does not involve calling itself, and if you do not have a base case your program will crash when you call the function because it will call itself an infinite number of times and you will get an error saying "Maximum recursion depth exceeded". Recursion is useful because it can help you do complicated tasks by relating them to their most simple cases. For example, consider the Towers of Hanoi problem with three stools, where you have to move rings from one stool to another stool but you cannot place a large . Though this problem seems complicated, it can be coded very simply using recursion. Your recursive method could use the following logic:

If there is only one cheese on the stool, move it to the destination

Else: Recursively call this function to move all cheeses except for one to an intermediate stool
Move the bottom cheese to the destination stool
Recursively call your function to move all cheeses from the intermediate stool to the destination stool.

This shows how recursion can solve more complicated problems by reducing them to their simplest cases.