Sorting and Efficiency

Sorting is the process of reorganizing a collection of items according to the desired criteria. This desired criteria is usually among ascending, or descending order. In computer science, there exist many types of sorting algorithms that get this job done. From my time in CSC108, the sorting algorithms that I have knowledge about are the bubble sort, insertion sort, and selection sort. However, recently I have learned about quick sort, merge sort, count sort, and python's default built-in sorting algorithm known as tim sort. One might think "why use one type of sorting over the other?" when all types of sorting algorithms can get the job done. Some notable reasons are that depending on the input to be sorted, some algorithms are more efficient than others. What do I mean by more efficient? If the sorting algorithm is given an input that is large in size, either ordered or non-ordered, performance will be quite different. For example, if a sorted list is given to both a program that utilises insertion sort and selection sort, insertion sort would perform better. This is because if the list is ordered, insertion sort just adds each element of the list to the sorted side without having to shift, or insert it into the right position. As a result, this takes at most n iterations. On the other hand, selection sort would still have to go through the whole unsorted side of the list each time to find either the biggest number or smaller number in the group. As a result, at least n^2 iterations are required for selection sort. Now imagine if the size of the input was 10,000. Insertion sort would go through 10,000 iterations while selection sort would go through 100,000, 000 iterations at the least. That would be a big difference in the amount of work the computer has to do. Thus, in this scenario selection sort is less efficient than insertion sort.

Computer scientists like to be able to analyze the run time complexity of algorithms. The notion that is used to represent the upper bound of the run time is known as the Big O. On a side note, the lower bound is known as the big omega and the tight bound (upper and lower bound) is known as big theta. I will be focusing on the Big O notion, but similar arguments can be made to the other two. As an example, the selection sort algorithm is based on a nested loop that depends on the size of n. Thus, selection sort will take at least n^2 iterations. The Big O notation in this case is O(n^2) which means that c*n^2 where c is a constant number is an upper bound for n^2 iterations. This means that the amount of iterations that selection sort takes is either equal to, or less than c*n^2 after a certain size of input. When talking about complexities of algorithms, only the effect at a large size of input is important to us because at a small size input the difference in efficiency is usually ignorable. So, how do we know what is an upper bound for each case? The following hierarchy sets the rules in place: O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(n^3) < O(n!) < O(n^n). The farther the Big O expression is in this inequality, the worst the performance is. Thus, computer scientists would prefer O(1), O(log n), O(n) over the other ones because at large size of input the difference is immense. 

I will now try to use this notion to describe the new sorting algorithms that I learned known as quick sort, merge sort, count sort, and tim sort. Quick sort is a sorting algorithm that depends on finding a pivot point and separating the elements that are larger than the pivot point to the right side and the elements that are smaller to the left side. This process is repeated n times and if the list is divided equally it will be defined by O(n log n). However, if the list is not divided equally each time, it will be defined by O(n^2) in the worst case. Thus, in the best case n log n is the upper bound for quick sort, but in the worst case c*n^2 is the upper bound for quick sort.

Merge sort is similar to quick sort in the aspect that it also divides the list into two sections and repeatedly does this until each list is a single element. Then, each list is compared with another and merged together into the right order. This process is repeated over and over again until the list is in the correct order. The number of times that merge sort divides the list is described by log n and because there are n elements, the process is repeated n times. Therefore, the Big O for merge sort is defined by

O(n log n). For example, if given the list [5,3,4,2,1], the list is divided into the lists [5,3] à [5] and [3] and [4,2,1]à[4] and [2,1]à[2] and [1]. [3] , [5] merges into [3,5], and [2] , [1] merges into [1,2] , and  [1,2] ,[4] merges into [1,2,4] , and [3,5] , [1,2,4] merges into [1,2,3,4,5].

Tim sort(known as the built-in sort function that python uses) is a sorting algorithm that uses a combination of insertion sort and merge sort to achieve its goal. Thus, the best case scenario is achieved when the list is ordered and insertion sort will only have to insert the items n times. The Big O notation would be defined as O(n) for the best case. However, in the worst case merge sort would be called n times and tim sort would take on the complexity for merge sort instead.  Therefore, tim sort has an order of n log n in the worst case.

In general, computer scientists only care about the efficiency of an algorithm when the size of the input is very large because the difference between small sized input results is usually dismissible. Imagine given a database with millions of entries and it is required to find one element in that database. Of course with our knowledge of the Big O, a searching and sorting algorithm for this problem is preferred to be on the left side of the hierarchy. By comparing the amount of resources used for a log n algorithm versus a n^3 algorithm, one can see the amount of time, resources, and money saved by efficiency. Therefore, sorting and efficiency is a very important topic for future years of computer science.

Binary Search Trees

Firstly, let us make the distinction between binary trees and binary search trees. Both tree structures branch off from a root with maximum 2 children per root, but the difference is that binary search trees sort the data with a condition asserted. This is the condition that all values less than root must go on the left sub-tree of the root while all values greater than the root belongs in the right sub-tree of the root. In the basic sense, binary search trees are the sorted version of binary trees. Due to the structure of binary search trees, searching for a value in them for many of the operations such as inserting, deleting, and returning are effectively more efficient than in a simple binary tree. Because of the condition of the binary search tree, each time we look for a value in the tree, one half of the values can be ignored. For example, if we had 1,000,000 elements in the tree to search from, 500,000 would remain after the first step. This is because if the value we're looking for is larger than the one at the root, the left side is ignored because all of them is smaller than the root which means they are also smaller than the value desired. A similar argument can be said for the other case where the value is smaller than the value at the root.

Binary search trees have similar operations to binary trees, but the way they are implemented is slightly different due to the condition. When implementing methods such as adding, deleting, inserting, or returning, the first condition to check is if it is smaller, equal, or larger than the root value. Then, afterwards depending on what the method is the children are checked for the same cases recursively until the base case for the method is reached. For example, the deleting method for binary search trees have a couple of cases. They are deleting from an empty tree, deleting from a tree with either only the left child, or only the right child, and lastly deleting from the tree with both the left and right child existing. Each case effectively ignores half of tree each time recursively until the base case is reached and the objective of method is reached. The way I see it is that binary search trees are more efficient than binary trees like how binary search is more effective than linear search for large number of searches.

LinkedLists

A linked list is a recursive data structure that is a collection of nodes. A linked list has the option of either being an empty list, or a node that stores data and refers to another linked list. The empty list case is represented with None while the other case splits the node into two parts: the head and the tail. The head is where the value of the node is stored while the tail is where the node references to another linked list. This means that the node may refer to an empty list, or another node like itself. As one can see, recursion plays a big part in linked list structures due to multiple referencing to other linked lists.

Linked lists are similar to lists in the aspect that information can be stored and modified. Some of the operations that they share are adding an element, deleting an element, reversing the list, and finding the element according to the index of the element. However, there is a slight difference because linked lists depend on referencing to another object instead of being one whole object like lists. In linked lists, the operations require the changing of the head's value and the tail's reference. For example, to prepend a value to the front of the linked list, the head of the list must be equal to the new value, but the tail must refer to the previous head of the linked list. Because linked lists use this referencing, infinite loops can cause issues for most of these methods and operations, which end up crashing the program.

As with many computer science structures, there is more than one way to implement linked lists. The first one is the one I've been talking about so far with the use of a head and a tail. The other way to implement linked list is to use linked list as a wrapper class for a class that defines a single node. The node class saves the value and the referenced node while the linked list wrapper class manipulates the nodes with operations. Both implementations essentially do the same thing, but in some cases the other one is more preferable due to the conditions of the problem. Linked list is another way for computer scientists to store and manipulate information, but in a slightly different approach than storing in one object such as list.