This week, we learnt about algorithms in Java, including sorting and searching method.
Sequential Search
Sequential search is also called linear search. The way it works is very simple: compare each item in the array with the target to see if there is any matches. It is commonly used when searching items from an unsorted array or text/csv files. The good thing is that it does not require sorting, but the searching process is relatively slower.
Pseudocode explanation:
Java explanation:
Binary Search
Binary search is an advantageous way of searching items in a sorted array. If we want to execute binary search, we need to define three location variables: first, which is the smallest in the array, and last which is the biggest in the array, and middle, which is the average of first and last. The first step is to compare the target that we are looking for with the number at the middle location. If the target is equal to the middle value, then we find it; if the target is larger than the middl value, then we assign the original value of middle to variable first in the next loop, so the middle value changed again, then it is compared with the target again. It is much faster that sequential search, but it can be only applied to sorted array.
Pseudocode explanation:
Java explanation:
Bubble Sorting
Sorting are method to arrange numbers in an array to an ascending or descending sequence. The first sorting method is bubble sort. It consider numbers in pair, from the first two numbers. For ascending sequence, in a loop, we swap the order of the numbers if the second one is smaller. Then the comparison move to the second and third number. After one round, it repeat from the beginning and swap another round. The algorithm stops when there are no numbers to swap. It is best used for almost sorted set.
Pseudocode explanation:
Java explanation:
Selection Sort
Selection sort is inefficient on large lists. Unlike the bubble sort, it only swap at the end of the loop. The algorithm divide the array into two parts: unsorted on the left and sorted on the right. It assign a smallest variable and first unsorted variable. It compare each two adjacent numbers from the first unsorted and hold the so far smallest number, and swap it to the end of the sorted.
Pseudocode explanation:
Java explanation:
Other In-class Activities
This is a homework concerning fruit searching. When we input an ID number, the program can output the related fruit name.
Abstract Data Types
For HL topic, we talked about abstract data type and structure. Each data type has a properties to execute certain implementations.
The first abstract data type is stack (Last In First Out), which means data are stores in a particular order. User can only access to the last item inserted. It’s like a badminton barrel. Data can be pushed (input) and popped (taken) from the top of the stack. Elements can be all kinds of data type.
The second abstract data type is queue (First In First Out). Elements are queued at the back and dequeued from the front.
The third abstract data type is list. It’s a set of data arranged in a certain order. User can change the data in at location without concerning the order. It can be shuffled or sorted.
The last abstract data type is rooted tree, means that all data are derived from one data. One typical example is binary tree, which means each data has two branches. The first one in the tree is called the root, while the others are called leaf.
Reflection
Things we learnt this week is basically some advanced application of previous commands. With this bases, we can process more complex data and solve more problems. I believe that it can be very powerful with what we will learn in the next week.
JIHONG ZHAO 