This topic gives an overview of the mathematical technique of a proof by induction: We will describe the inductive principle, look at ten different examples, four examples where the technique is incorrectly applied, well-ordering of the natural numbers, strong induction, geometric problems. | Review 1 Introduction to Recursion Recursive Definition Recursive Algorithms Finding a Recursive Solution Example Recursive Function Recursive Programming Rules for Recursive Function Example Tower of Hanoi Other examples Bubble Sort 2 Bubble Sort Bubble Sort Algorithm Time Complexity Best case Average case Worst case Examples Bubble Sort In bubble sort, each element is compared with its adjacent element If the first element is larger than the second one, then the positions of the elements are interchanged otherwise it is not changed Then next element is compared with its adjacent element and the same process is repeated for all the elements in the array until we get a sorted array 3 Let A be a linear array of n numbers Suppose the list of numbers A[1], A[2], A[n] is an element of array A Sorting of A means rearranging the elements of A so that they are in order Here we are dealing with ascending order. ., A[1] < A[2] < A[3]< A[n] The bubble sort algorithm works as follows: 4 Step 1: Compare A[1] and A[2] and arrange them in the ascending order so that A[1] < A[2] If A[1] is greater than A[2] then interchange the position of data by swap = A[1]; A[1] = A[2]; A[2] = swap Then compare A[2] and A[3] and arrange them so that A[2] < A[3] Continue the process until we compare A[N – 1] with A[N] Step1 contains n – 1 comparisons ., the largest element is “bubbled up” to the nth position When step 1 is completed A[N] will contain the largest element 5 Step 2: Repeat step 1 with one less comparisons that is, now stop comparison at A [n – 1] and possibly rearrange A[N – 2] and A[N – 1] and so on In the first pass, step 2 involves n–2 comparisons and the second largest element will occupy A[n-1] And in the second pass, step 2 involves n – 3 comparisons and the 3rd largest element will occupy A[n – 2] and so on After n – 1 steps, the array will be a sorted array in increasing (or ascending) order 6 Algorithm Let A be a linear array of n numbers. Swap is a . | Review 1 Introduction to Recursion Recursive Definition Recursive Algorithms Finding a Recursive Solution Example Recursive Function Recursive Programming Rules for Recursive Function Example Tower of Hanoi Other examples Bubble Sort 2 Bubble Sort Bubble Sort Algorithm Time Complexity Best case Average case Worst case Examples Bubble Sort In bubble sort, each element is compared with its adjacent element If the first element is larger than the second one, then the positions of the elements are interchanged otherwise it is not changed Then next element is compared with its adjacent element and the same process is repeated for all the elements in the array until we get a sorted array 3 Let A be a linear array of n numbers Suppose the list of numbers A[1], A[2], A[n] is an element of array A Sorting of A means rearranging the elements of A so that they are in order Here we are dealing with ascending order. ., A[1] < A[2] < A[3]< A[n] The bubble sort algorithm works as .
