CPU 1142 DATA STRUCTURES AND ALGORITHMS Day School 6 M. K. A. Ariyaratne B [email protected] T 0112 881225 Department of Mathematics and Computer Science Faculty of Natural Sciences The Open University of Sri Lanka Sri Lanka Sept 19, 2014 M. K. A. Ariyaratne Day School 6 Sept 19, 2014 1 / 45 Summary Summary We have seen the meaning of the term Data Structures and we have learned few Data Structures; Array, Singly Linked List, Circular Linked List, Doubly Linked List, Stack, Queue, Tree, Binary Tree and Graphs. Then we started learning Algorithms. We discussed features of algorithms and few problem solving techniques that are useful when designing algorithms. 1 2 3 4 Divide and Conquer method Dynamic Programming Greedy Method Linear Programming We also studied the importance of analyzing algorithms. We have seen how to analyze algorithms in terms of space complexity and time complexity. M. K. A. Ariyaratne Day School 6 Sept 19, 2014 2 / 45 Introduction Introduction Now we know few Data Structures and importance of analyzing algorithms. Today Let’s try to learn a new programming technique and few Sorting Algorithms. M. K. A. Ariyaratne Day School 6 Sept 19, 2014 3 / 45 Introduction How is the Evaluation CPU 1142 DATE NBT 1 21 - 08 - 2014 NBT 2 25 - 09 - 2014 PT 15 - 09 - 2014 Final Examination ..... Contact Details: B : [email protected] T : 0112 881225 m: : http://www.mkaariyaratne.com http://ousl.nodes.lk/ M. K. A. Ariyaratne Day School 6 Sept 19, 2014 4 / 45 Recursion LESSON 17 Recursion M. K. A. Ariyaratne Day School 6 Sept 19, 2014 5 / 45 Recursion Introduction In computer science, recursion is a way of solving problems and is one of the main programming techniques. We have seen that repetition can be achieved by writing loops, such as for loops and while loops. Another way to achieve repetition is through recursion, which occurs when a function calls itself. Recursion is a method where the solution to a problem depends on solutions to smaller instances of the same problem. Most computer programming languages support recursion by allowing a function to call itself within the program text. In this lesson we will be studying basic recursive procedures, types of recursion, pros and cons of using recursion and so on. M. K. A. Ariyaratne Day School 6 Sept 19, 2014 6 / 45 Recursion Types of Recursion There are two types of recursion 1 2 Direct Recursion Indirect Recursion Direct Recursion is where a function calls itself. Indirect recursion is where a function A calls another function B, Fuction B calls function C and so on until eventually the function A is called. int abc() int abc() { { ----------xyz(); ----------} abc(); int xyz() ----------{ end abc(); } } M. K. A. Ariyaratne Day School 6 Sept 19, 2014 7 / 45 Recursion Properties of Recursive Algorithms In order to develop successful recursive programs, there are few requirements to be fulfilled. 1 2 3 4 Recursive function should not infinity call to itself. For at least one argument, the recursive function f must be defined in terms without f . There must be a way to get out from the sequence of recursive calls. Recursive algorithm must eventually reduce to one or more simple, non recursive cases. M. K. A. Ariyaratne Day School 6 Sept 19, 2014 8 / 45 Recursion Simple recursive programs Let’s look at a mathematical definition of a recursive function. 1, if n = 0. f act(n) = (1) n × f act(n − 1), otherwise. This can be written in C as follows int fact (int n) { if (n == 0) return 1; else return n * fact(n-1); } M. K. A. Ariyaratne Day School 6 Sept 19, 2014 9 / 45 Recursion Simple recursive programs Another well known recursive functions are Fibonacci number series and Triangular numbers. ( 1, if n = 1. nth tri number = (2) th n + (n − 1) tri number, otherwise. if n = 0. 0, nth f ib number = 1, if n = 1. (n − 1)th f ib num + (n − 2)th f ib num, otherwise. (3) We can use recursion when implementing data structures too. That is where you implement Linked lists, Binary tress using pointers. M. K. A. Ariyaratne Day School 6 Sept 19, 2014 10 / 45 Recursion Recursion Vs. Iteration Recursion is a good programming technique, but not always the best. Here we will give some reasons for why recursion is not good always. 1 2 3 Recursive algorithms need more stack space than iterative algorithms. It makes inefficient utilization of memory. It slows down execution speed. M. K. A. Ariyaratne Day School 6 Sept 19, 2014 11 / 45 Internal Sorting LESSON 18 Internal Sorting M. K. A. Ariyaratne Day School 6 Sept 19, 2014 12 / 45 Internal Sorting Introduction The process of sorting a list of items in a specific way such as in ascending or in descending order is a very fundamental process, done very frequently. The evolution of computer sorting algorithms parallels the evolution of computers. To sort items, computers need a considerable amount of running time. Therefore selecting the most appropriate sorting algorithm for the situation, is important. There are many computer sorting algorithms in the world and they are classified in to two main categories. 1 2 Internal Sorting : Sorting is take place in the main memory of the computer External Sorting : When the set of items to be sorted too large to be fit in to main memory, data to be sorted use secondary storage devices. M. K. A. Ariyaratne Day School 6 Sept 19, 2014 13 / 45 Internal Sorting Introduction(2) Main memory: The main memory of the computer is also known as RAM, standing for Random Access Memory.The computer can manipulate only data that is in main memory. Therefore, every program you execute and every file you access must be copied from a storage device into main memory. This has volatile memory. Secondary Memory: This is a non-volatile memory (does not lose the data when the device is powered down) that it is not directly accessible by the CPU. E.g.Flash memory, Hard Drive. M. K. A. Ariyaratne Day School 6 Sept 19, 2014 14 / 45 Internal Sorting Introduction(3) Internal sorting algorithms are of 7 types. 1 2 3 4 5 6 7 Bubble Sort Insertion Sort Quick Sort Heap Sort Merge Sort Radix Sort Selection sort One example for the external sorting is external Merge sort. M. K. A. Ariyaratne Day School 6 Sept 19, 2014 15 / 45 Internal Sorting Internal Sorting Algorithms As stated before, these algorithms are used to sort data when the size of the data set fits to the main memory of the computer. These algorithms are also known as in-place algorithms. That is because when we do sorting using these algorithms, the rearrangement process occur entirely within the sequence of the data set with one or two additional locations to store elements temporarily. It is difficult to decide what is the best algorithm and it is based on the circumstances. M. K. A. Ariyaratne Day School 6 Sept 19, 2014 16 / 45 Internal Sorting Sorting by Exchange - Bubble Sort We will first understand the nature of each sorting algorithm using an understandable example. Assume we have set of people in a line. We need to sort them according to their height; smallest to tallest. M. K. A. Ariyaratne Day School 6 Sept 19, 2014 17 / 45 Internal Sorting Sorting by Exchange - Bubble Sort(2) The bubble sort is notoriously slow, but it is conceptually the simplest of the sorting algorithms and for that reason, is a good beginning for our exploration of sorting techniques. In bubble sort, each element is compared with its adjacent element. If the first element is larger than the second element, then the positions are interchanged. Then you go one step front and repeat the process. The algorithm gets its name from the way smaller elements “bubbles” to the top of the list. Let’s apply Bubble Sort on the Set of unsorted people in the line that we saw earlier. M. K. A. Ariyaratne Day School 6 Sept 19, 2014 18 / 45 Internal Sorting Sorting by Exchange - Bubble Sort(3) 1 Compare two players 2 If the one in the left is taller, swap them 3 Move one position right M. K. A. Ariyaratne Day School 6 Sept 19, 2014 19 / 45 Internal Sorting Bubble Sort on Set of Integers Let’s see how bubble sort works on a set of Integers M. K. A. Ariyaratne Day School 6 Sept 19, 2014 20 / 45 Internal Sorting Bubble Sort - C code void bubbleSort(int a[], int n) { int i,j,tmp; for (i=0; i<n-1; i++) { for (j=0; j<n-1; j++) { if (a[j] > a[j+1]) /* compare the two neighbors */ { tmp = a[j]; /* swap a[j] and a[j+1] */ a[j] = a[j+1]; a[j+1] = tmp; } } } } M. K. A. Ariyaratne Day School 6 Sept 19, 2014 21 / 45 Internal Sorting Quick Sort Quick sort is undoubtedly the most popular sorting algorithm and is the most efficient algorithm in internal sorting. Basically, the quick sort algorithm operates by partitioning an array into two sub arrays and then calling itself recursively to quick sort each of these sub arrays. This is another divide-and-conquer algorithm. M. K. A. Ariyaratne Day School 6 Sept 19, 2014 22 / 45 Internal Sorting Quick Sort(2) Following are the basic steps of the quick sort algorithm. Pick an element, say P (the pivot) from the data set. Re-arrange the elements into 3 sub-blocks, 1 2 3 those less than or equal to (<=)P(the left-block S1) P(the only element in the middle-block) those greater than or equal to (>=)P(the right-block S2) Repeat the process recursively for the left and right sub blocks. M. K. A. Ariyaratne Day School 6 Sept 19, 2014 23 / 45 Internal Sorting Quick Sort(3) M. K. A. Ariyaratne Day School 6 Sept 19, 2014 24 / 45 Internal Sorting Quick Sort(4) The main idea is to find the “right” position for the pivot element P. After each “pass”, the pivot element, P, should be “in place”. Eventually, the elements are sorted since each pass puts at least one element (i.e., P) into its final position. Issue : How to choose the pivot P? M. K. A. Ariyaratne Day School 6 Sept 19, 2014 25 / 45 Internal Sorting Quick Sort(5) Now let’s see how to carry out a quick sort on set of integers. First we select a pivot value from the data set. Then we do the comparison as follows. The process should repeat to the partitions as well. M. K. A. Ariyaratne Day School 6 Sept 19, 2014 26 / 45 Internal Sorting Quick Sort - Start Start with all data in an array, and consider it unsorted M. K. A. Ariyaratne Day School 6 Sept 19, 2014 27 / 45 Internal Sorting Quick Sort - Step 1 Step 1 Select a pivot (it is arbitrary) We will select the first element, as presented in the original algorithm by C.A.R. Hoare in 1962. M. K. A. Ariyaratne Day School 6 Sept 19, 2014 28 / 45 Internal Sorting Quick Sort - Step 2 Step 2 Start process of dividing data into LEFT and RIGHT groups: The LEFT group will have elements less than the pivot. The RIGHT group will have elements greater than the pivot. Use markers left & right M. K. A. Ariyaratne Day School 6 Sept 19, 2014 29 / 45 Internal Sorting Quick Sort - Step 3 Step 3 If left element belongs to LEFT, then increment left index. If right element belongs to RIGHT, then decrement right index. Exchange when you find elements that belong to the other group. M. K. A. Ariyaratne Day School 6 Sept 19, 2014 30 / 45 Internal Sorting Quick Sort - Step 4 Element 33 belongs to RIGHT group Step 4 Element 22 belongs to LEFT group Exchange the two elements. M. K. A. Ariyaratne Day School 6 Sept 19, 2014 31 / 45 Internal Sorting Quick Sort - Step 5 Step 5 After the exchange, increment left marker, decrement right marker M. K. A. Ariyaratne Day School 6 Sept 19, 2014 32 / 45 Internal Sorting Quick Sort - Step 6 Step 6 Element 35 belongs to RIGHT group Element 12 belongs to LEFT group Exchange the two elements Increment left and decrement right. M. K. A. Ariyaratne Day School 6 Sept 19, 2014 33 / 45 Internal Sorting Quick Sort - Step 7 Step 7 Element 29 belongs to RIGHT group Element 19 belongs to LEFT group Exchange the two elements Increment left and decrement right. M. K. A. Ariyaratne Day School 6 Sept 19, 2014 34 / 45 Internal Sorting Quick Sort - Step 8 Step 8 When the left and right markers pass each other, we are done with the partition task. Swap the right with pivot. M. K. A. Ariyaratne Day School 6 Sept 19, 2014 35 / 45 Internal Sorting Quick Sort - Step 9 Apply Quicksort to the LEFT and RIGHT groups, Step 9 recursively. Assemble parts when done M. K. A. Ariyaratne Day School 6 Sept 19, 2014 36 / 45 Internal Sorting Quick Sort - Selecting the Pivot Use the first element as pivot 1 2 if the input is random, then this is ok if the input is presorted (or in reverse order) all the elements go into LEFT (or RIGHT) Choose the pivot randomly 1 2 generally safe random number generation can be expensive Therefore, Randomly choosing a pivot point, rather than using the left most element is recommended, if the data to be sorted is not random. A compromise solution is to find the median of the first, last, and middle elements of the array, and use this for the pivot. This is called the median-of-three approach. M. K. A. Ariyaratne Day School 6 Sept 19, 2014 37 / 45 Internal Sorting by Selection LESSON 20 Internal Sorting by Selection M. K. A. Ariyaratne Day School 6 Sept 19, 2014 38 / 45 Internal Sorting by Selection Sorting by Selection - Selection Sort The selection sort improves the bubble sort by reducing the number of swaps necessary. Algorithm starts from the first element of the array and scans through the array for a smaller element than the first element. If found a smaller element, it will be swapped with the first element. Then algorithm goes to the second element and scan the array to find a smaller element than the second element. (Now we have nothing to do with the first element). If found we swap the second element with that smaller element. This process is repeated until the whole array is sorted. Let’s apply Selection Sort on the Set of unsorted people in the line that we saw earlier. M. K. A. Ariyaratne Day School 6 Sept 19, 2014 39 / 45 Internal Sorting by Selection Selection Sort Algorithm(2) 1 Making a pass through all the people and selecting the shortest one. 2 This shortest player is then swapped with the first player at position 0. Now the leftmost player is sorted and won’t need to be moved again. 3 The next time you pass down the row of players, you start at player 2 (position 1), and, find the minimum, swap it with player 2. This process continues until all the players are sorted. M. K. A. Ariyaratne Day School 6 Sept 19, 2014 40 / 45 Internal Sorting by Selection Selection Sort on Set of Integers Let’s see how selection sort works on a set of Integers M. K. A. Ariyaratne Day School 6 Sept 19, 2014 41 / 45 Internal Sorting by Selection Selection Sort C code void selectionSort(int numbers[], int array size) { int i, j; int min, temp; for (i = 0; i < array size-1; i++) { min = i; for (j = i+1; j < array size-1; j++) { if (numbers[j] < numbers[min]) min = j; } temp = numbers[i]; numbers[i] = numbers[min]; numbers[min] = temp; } } M. K. A. Ariyaratne Day School 6 Sept 19, 2014 42 / 45 Summary Summary We have completed 19 Lessons. To day we learned Recursion and few internal sorting algorithms M. K. A. Ariyaratne Day School 6 Sept 19, 2014 43 / 45 References References If you are interested in Data Structures, visit the following resources. 1 2 3 Data Structures and Algorithms in java by Robert Lafore. http://www.programmingsimplified.com/c-program-examples http://www.cse.ust.hk/~horner/comp104/ M. K. A. Ariyaratne Day School 6 Sept 19, 2014 44 / 45 Thank You M. K. A. Ariyaratne Day School 6 Sept 19, 2014 45 / 45
© Copyright 2024 ExpyDoc
