Sorting algorithm analysis | datastructure and algorithm
Credit: sorting visualizations created using visualgo.net
Transcript:
#Sorting #algorithms give us an opportunity to apply what we've learned about the #analysis of algorithms together with the writing of template functions, as well as an opportunity to review recursion as well as STL footnote:[STL=_Standard Template Library_] abstractions like iterators. That's a lot of ground to cover! We will look at:
the venerable but terrible bubble sort,
the somewhat better insertion sort,
the simple but performant merge sort,
the ubiquitous quicksort as well as
some special-purpose sorting algorithms.
First, some ground rules. We're going to start by looking at arrays of integers that need to be sorted into a non-decreasing order. In class we'll work more generally with templates that accept any moveable or copyable data type (i.e., something with a move or copy constructor). Our templates will also accept comparator functions as parameters so that we can sort by whatever criteria we like: increasing value, decreasing value, increasing length of a student's name, etc. Finally, we will use iterators rather than arrays to be as general as possible. To get the basic idea of these sorting algorithms, however, this video will show arrays of integers.
The first sorting algorithm you saw in Engineering One was the bubble sort. This algorithm takes multiple linear passes through an array, comparing consecutive elements and swapping them if they're out of order. This has the effect of causing the largest number to "bubble" up through the array until it reaches the end. The algorithm then repeats, causing the second-largest element to "bubble" up and so on. For an n-element array, up to n-1 passes may be required (though the algorithm can exit early if a pass doesn't do any swaps — this indicates that the array is sorted). The i'th pass through the array will perform n-i-1 comparisons and up to the same number of swaps. So, the overall number of operations (in the worst case) is n times a constant times (n-i-1), which simplifies to n^2. Thus, the bubble sort is a quadratic algorithm: sorting twice as much data will cost you something like four times as much computation.
Question: if the worst case of the bubble sort's run time is quadratic, what is the best-case run time?
Insertion sort is another simple algorithm that guarantees progressively larger subsets of a sequence have been sorted. Like the bubble sort, it propagates elements to the place they belong within the already-sorted portion of the sequence. Unlike the bubble sort, however, it does this more directly with an insert-like operation instead of a series of swaps. Still, as an algorithm with order-n passes, each of which performs order-n operations, this is another quadratic sort. The constant value c may be lower, but it's still a big-O n^2 algorithm.
The merge sort is more sophisticated: it's an example of a recursive sorting algorithm. At first glance it appears to perform more work than the simple bubble or insertion sort algorithms, but its asymptotic performance is categorically superior.
The merge sort takes two already-sorted sequences and merges them together into a larger sorted sequence. It is defined recursively: we can sort a sequence of size N if we are given two sorted sub-sequences of length N/2. The base case is when N=1: such a "sequence" is trivially already sorted. The process of merging two sub-sequences together is _linear_: the algorithm needs to track the next element in each sorted sub-sequence and choose the smaller one to add to the larger sequence — this takes order-N operations.
We will analyze the overall run-time complexity of the merge sort in class, as it's a really neat example of recursion in both the algorithm and the analysis.
In practice, owing to high constant factors in the mergesort, some implementations use an insertion sort on small initial arrays and then use the merge sort to combine them.
More videos related to algorithms
Class templates: • C++ class template | Datastructure and alg...
Time complexity: • Time complexity to analysis algorithms | d...
Sorting techniques: • Sorting algorithm analysis | datastructure...
In questa pagina del sito puoi guardare il video online Sorting algorithm analysis | datastructure and algorithm della durata di ore minuti seconda in buona qualità , che l'utente ha caricato code house 08 novembre 2020, condividi il link con amici e conoscenti, su youtube questo video è già stato visto 16 volte e gli è piaciuto 3 spettatori. Buona visione!
