TAILIEUCHUNG - Lecture Algorithms and data structures (CSC112) - Chapter 4

Lecture Algorithms and data structures: Chapter 4 - Bubble Sort. 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 .

• Kỹ thuật lập trình
• Data structures
• Lecture Algorithms and data structures
• Thiết kế thuật toán
• Cấu trúc dữ liệu
• Algorithm analysis
• Graph algorithms
• Design techniques
• Ebook Data structures and algorithms made easy
• Data structures and algorithms made easy
• Data structures and algorithmic puzzles
• Data structures for storing strings
• Algorithms design techniques
• algorithms
• data structure lectures
• structured document data
• teaching data structures
• algorithms in data structures
• Lecture Data Structures
• Bài giảng Cấu trúc dữ liệu
• Programming assignments
• Data structures organize data
• Resource constraints
• Lecture Data structures and algorithms
• Data structures and algorithms
• Cấu trúc dữ liệu và giải thuật
• Abstract data type
• Lecture ECE 250
• Memory allocation
• Computer science
• Design of data structures
• Algorithms in Java
• AVL trees
• Binary search trees
• Red black trees
• Splay trees
• Dynamic programming