TAILIEUCHUNG - 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 .

• Cơ sở dữ liệu
• Algorithm analysis
• Graph algorithms
• Design techniques
• Data structures
• Lecture Algorithms and data structures
• Algorithm analysis
• Design techniques
• Cấu trúc dữ liệu
• Algorithm analysis in C++
• The disjoint sets class
• Algorithm design techniques
• Amortized analysis
• Advanced data structures
• Advanced Algorithms Analysis and Design
• Lecture Advanced Algorithms Analysis and Design
• Bài giảng Phân tích và thiết kế thuật toán nâng cao
• The Floyd Warshall algorithm
• Johnson’s algorithm
• Bellman Ford algorithm
• Algorithm design
• Lecture Algorithm design
• Computational tractability
• Asymptotic order of growth
• Polynomial running time
• Dynamic programming
• Hirschbergs algorithm
• Greedy Algorithms
• Dijkstras algorithm
• Minimum spanning trees
• Network flow
• Ford Fulkerson algorithm
• Max flow min cut theorem
• Analysis in C++
• A general overview
• Extendible hashing
• Hash tables in the standard library
• Performance analysis of a sugar plant using genetic algorithm
• Optimization of crystallization system of a sugar plant using genetic algorithm
• A sugar plant using genetic algorithm
• Refining system fails
• The crystallization system includes crystallization units
• Local search
• Gradient descent
• Metropolis algorithm
• Analysis of Algorithm
• Incorrect algorithms
• Analyzing an algorithm
• nalyzing an algorithm
• The correct output
• Communication bandwidth
• Computational time
• A practical introduction
• Mathematical preliminaries
• Binary trees
• Non binary trees
• Internal sorting
• Graph search
• Graph connectivity
• Graph traversal
• Coin changing
• Optimal caching
• Counting inversions
• Closest pair of points
• Randomized quicksort
• Master theorem
• Integer multiplication
• Matrix multiplication
• Weighted interval scheduling
• Knapsack problem
• Bipartite matching
• Disjoint paths
• Assignment problem
• Input queued switching
• Poly time reductions
• Constraint satisfaction problems
• Graph coloring
• Decision problems
• NP complete
• Nondeterministic polynomial
• PSPACE complexity class
• Quantified satisfiability
• PSPACE complete
• Vertex covers
• Bipartite graphs
• Limits of tractability
• Approximation Algorithms
• Vertex cover
• Randomized Algorithms
• Contention resolution
• Linearity of expectation
• Performance analysis of a real time adaptive prediction algorithm
• Real time adaptive prediction algorithm for traffic congestion
• Lower Mean Square Error
• The actual traffic congestion states