This week I learned different sorting and searching algorithms. Sorting means arranging the elements in an array in ascending or descending order. Searching means finding an element in an array.
Sorting algorithms
- Bubble sort
- Selection sort
- Insertion sort
- Quick sort
Searching algorithms
- Binary search
Bubble sort
Imagine you have a list of numbers, from left to right, unsorted. One of the ways to sort it is bubble sort. Compare the first two elements, if the first element is bigger than the second, switch the first and second element’s position, so the bigger one can move to the right, then compare the second and third element, after you gone through the list once, the numbers are getting better because the bigger number starts to “bubble up”, continue this operation from the start of the list until the list is sorted.
There are many sorting algorithms, you can check cs50’s study website https://study.cs50.net/ for details and animations. Alternatively, you can check this website http://www.sorting-algorithms.com/. MIT bubble sort demo http://web.mit.edu/6.mitx/www/6.00-sortingDemo/sortingDemoBubble.html, click on the play button of graph visualization.
Binary search
Binary search is similar to the bisection search in week 2 of MIT 6.001x course. It eliminates half of the search possibilities on each iteration. The difference between them is binary search deals with distinct element (0, 1, 2, 3,…), while bisection search deals with continuous numbers (numbers between 0 to 100). Both binary search and bisection search requires the array to be sorted before they are performed, because we need to know if our guess is bigger or smaller than the answer.
Big O, Omega, and Big Theta
Different sorting and searching algorithms has different efficiency, the most efficient algorithm performs the task fastest and the least efficient performs the task slowest. How do we measure the efficiency of an algorithm? We learned something called big O, 
Bubble sort, insertion sort, and selection sort has Big O of 
GDB debug and importance of pseudocode
Always write pseudocode before writing your code. Pseudocode lets you organize your logic without having to worry about syntax yet. If you do not write pseudocode, you may get confused when an error occurs, and you do not know if its logic problem or the syntax problem.
Example of pseudocode for binary search:
|
1 2 3 4 5 6 7 8 9 |
define lower and upper bounds halve the array until bounds overlaps define middle if the value lies in the middle, return true if the value is less than middle, make middle the new upper bound if the value is more than middle, make middle the new lower bound return false |
Implementation of code:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
/** * implement a binary searching algorithm * Returns true if value is in array of n values, else false. */ bool search(int value, int array[], int n) { // define lower and upper bounds int lower = 0; int upper = n - 1; int middle = (lower + upper) / 2; // halve the array until bounds overlaps while (lower <= upper) { // if the value lies in the middle, return true if (array[middle] == value) { return true; } // if the value is more than middle, make middle the new lower bound else if (array[middle] < value) { lower = middle + 1; } // if the value is less than middle, make middle the new upper bound else if (array[middle] > value) { upper = middle - 1; } // define middle middle = (lower + upper) / 2; } // return false return false; } |
GDB debug is a very useful tool to debug your program. It lets you go through step by step of your program execution, and let you view each variable at each step, also, you can modify variable in gdb to test your program.
Problem sets
There are two sections for this week’s problem set, the first deals with sorting and searching, the second implements a game called 15 puzzle.
Searching and sorting
First problem is to make a program that generates a list of pseudorandom numbers. Then, we have to program a file called find to sort the numbers and search for a value chosen by user.
1. Standard edition: Program bubble sort, then linear search.
2. Hacker edition: Program counting sort, then binary search.
Game of Fifteen
- Standard edition: tiles are generated at a specified configuration.
- Hacker edition: tiles are generated at random (but must be solvable – http://www.cs.bham.ac.uk/~mdr/teaching/modules04/java2/TilesSolvability.html) + GOD mode is added.
I am unable to implement the GOD mode of hacker edition of game of fifteen, it has something to do with divide and conquer and greedy algorithm http://larc.unt.edu/ian/pubs/saml.pdf.
|
1 2 3 4 5 6 7 8 9 10 |
If n = 3 solve by brute force else use greedy algorithm to put the first row and column in place move blank space to the right of target tile move diagonally (Fig. 3) until it reaches the correct row/ column move the tile vertically/ horizontally (refer Fig. 4, Fig. 5) call puzzle (n-1) to solve the remaining rows and columns |
My codes: https://github.com/shaunlgs/CS50x
Other posts in the series: Harvard CS50x 2014