0
What is the number of swaps required to sort n elements using selection sort in worst case?
Wiki User
∙ 12y ago
O(n2)
Wiki User
∙ 12y ago
Add your answer:
Earn +20 pts
What is mean by selection sort?
Selection sort works by looking for the largest value in a set and swapping it with the last value. The last value can now be ignored since it is now in place. The process repeats with the remainder of the set. After repeated passes, the remainder of the set will have only one item, the smallest value, at which point all the values will be in sorted order. The algorithm is similar to that of bubblesort, but is generally more efficient because there can only be one swap at most for each iteration of the algorithm. With bubble sort, there may be multiple swaps per iteration. However, while the number of comparisons is the same for both algorithms, bubblesort can be optimised to minimise the number of iterations required and thus minimise the number of comparisons. Nevertheless, swapping is a more expensive operation than comparing, thus selection sort is generally faster. Neither algorithm is suitable for sorting large sets of data.
Differences between Quicksort and selection sort?
Bubble sort is easy to program, slower, iterative. Compares neighboring numbers swaps it if required and continues this procedure until there are no more swaps Quick Sort is little difficult to program, Fastest, Recursive. Pivot number is selected, other numbers are compared with it and shifted to the right of number or left depending upon criteria again this method is applied to the left and right list generated to the pivot point number. Select pivot point among that list.
Difference between insertion sort and bubble sort?
Bubble sort and insertion sort both have the same time complexity (and space complexity) in the best, worst, and average cases. However, these are purely theoretical comparisons. In practical real-world scenarios, insertion sort (or any other sort, for that matter) will almost always be the better choice over a bubble sort.
What is the purpose of the flag variable in a bubble sort?
to eliminate unnecessary swaps to eliminate unnecessary comparisons to stop as soon as the list is sorted to sort an array of unknown size
Difference between insertion and selection sort?
Before we examine the differences, let us examine the implementations. The code that follows is written in C++, but can be easily adapted to other languages. Firstly, let us assume we have an array of num elements (we'll use integers here, but typically you will use pointers to maintain efficiency): int array[num]; A selection sort has the following nested loop structure: for( int outer=0; outer < num-1; ++outer ) { int min = outer; for( inner=outer+1; inner < num; ++inner ) { if( array[inner] < array[min] ) min = inner; } if( min != outer ) swap( array[min], array[outer] ); } Whereas an insertion sort has the following nested loop structure: for( index=1; index < num; ++index ) { value = array[index]; hole = index; while( hole > 0 && value < array[hole-1] ) array[hole] = array[--hole]; array[hole] = value; } Although both algorithms split an array into two subsets (a sorted subset to the left and an unsorted subset to the right) and both move one element from one set to the other on each iteration of the outer loop, the selection sort begins with an empty sorted subset while the insertion sort begins with a sorted subset of one element (any array with only one element can always be regarded as being sorted). In both cases, the outer loop keeps track of the initial index of the current unsorted subset and both perform a complete traversal of the unsorted subset. However selection sort stops when there is only one unsorted element left, which automatically becomes the largest value in the sorted set and therefore doesn't need to move, whereas insertion sort traverses the entire unsorted subset. The key difference is in the inner loops. With selection sort, the inner loop skips the first unsorted element and traverses the remainder of the unsorted subset locating the index of the lowest value (recorded by min). At the end of the inner traversal, if min is not the same as the outer loop index then the values are swapped. Thus the sorted subset gains a new element containing the next largest value on each iteration, beginning with the lowest value. With insertion sort, the outer loop extracts the first unsorted element's value and stores its index (hole). There isn't really a hole in the array, it's simply a marker to determine where the extracted value will be inserted. The inner while loop then traverses the sorted subset. On each iteration, if the hole marker is non-zero and the value is less than the value of the element to the left of the hole marker, then that element's value is copied into the hole to its right and the hole marker moves left. When the inner loop ends, the hole marker denotes where the extracted value should be placed. Thus if the extracted value is greater than or equal to the largest sorted value, then the value doesn't move (it was already sorted), otherwise it is inserted into its correct position within the sorted subset. It can be proved that although selection sort only requires one swap at most for every iteration of the outer loop, it must perform (num-1)! comparisons in total (that is, for num=6 there are 5+4+3+2+1 comparisons in total). It should be noted that every swap incurs three copy processes, however a single copy takes less time than a single comparison. By contrast, insertion sort stops comparing when the insert point is located, thus, on average, there will be fewer comparisons than (num-1)!. However, while every iteration of the outer loop incurs two copy processes even if the current element doesn't need to move, and additional copy processes for each movement of the hole marker, it's wrong to assume selection sort is always faster. On average, it is actually slower. Looking at the worst case example, let us suppose the array is in reverse order. Selection sort requires (num-1)! comparisons no matter what and will also incur n-1 swaps in total (which is 3(num-1) copies in total). By contrast, insertion sort also requires (num-1)! comparisons but requires 2(num-1)+(num-1)! copy processes. The end result is that selection sort performs slightly better, and will improve as the array size increases. Another worst case example is the already-sorted array. Again, selection sort requires (num-1)! comparisons but no swaps at all. However, insertion sort only requires num-1 comparisons and 2(num-1) copies. In this case, insertion sort performs slightly better, and will improve as the array size increases. While both algorithms are fairly efficient when dealing with small arrays (typically up to 20 elements), with insertion sort performing better on average, they are highly inefficient when dealing with larger arrays. For this you need recursive, logarithmic, divide-and-conquer algorithms, such as quicksort, which are capable of sorting num elements with only (log num) comparisons. However, these algorithms don't perform well with smaller subsets, so it pays to combine the two into a hybrid algorithm. That is, when a logarithmic algorithm reduces a subset to 20 elements or less, then that subset can be sorted far more efficiently with an insertion sort.
When did Swaps die?
Swaps was born on March 1, 1952, in California, USA.
What's the determinant of a matrix?
A determinant is defined for square matrices only.To find the determinant of the matrix you need to:find all n-tuples of elements of the matrix such that each row and each column of the matrix is represented.calculate the product of the elements.calculate the sign for that term. To see how this is done, see below.calculate the sum of the signed products: that is the determinant.To calculate the sign for the product of the n-tuple, arrange the elements in row order. Swap the elements, two at a time, to get them in column order. If the number of swaps required is even then the product is assigned a positive sign, and if odd then a negative sign.
What is the determinant of a matrix?
A determinant is defined for square matrices only.To find the determinant of the matrix you need to:find all n-tuples of elements of the matrix such that each row and each column of the matrix is represented.calculate the product of the elements.calculate the sign for that term. To see how this is done, see below.calculate the sum of the signed products: that is the determinant.To calculate the sign for the product of the n-tuple, arrange the elements in row order. Swap the elements, two at a time, to get them in column order. If the number of swaps required is even then the product is assigned a positive sign, and if odd then a negative sign.
What is the difference between currency swaps and cross currency swaps?
http://en.wikipedia.org/wiki/Currency_swap
What are the habitats about crocodile?
they live in swaps
What is mean by selection sort?
Selection sort works by looking for the largest value in a set and swapping it with the last value. The last value can now be ignored since it is now in place. The process repeats with the remainder of the set. After repeated passes, the remainder of the set will have only one item, the smallest value, at which point all the values will be in sorted order. The algorithm is similar to that of bubblesort, but is generally more efficient because there can only be one swap at most for each iteration of the algorithm. With bubble sort, there may be multiple swaps per iteration. However, while the number of comparisons is the same for both algorithms, bubblesort can be optimised to minimise the number of iterations required and thus minimise the number of comparisons. Nevertheless, swapping is a more expensive operation than comparing, thus selection sort is generally faster. Neither algorithm is suitable for sorting large sets of data.
How are journal entries made for credit default swaps?
Everything has to be entered. You can write down the number with a little notation to show that a swap has been made.
Where did Jacob kind?
he was dead in swaps of leaux
What is the difference between swaps and marshes?
ftrgftrrtswssdrfdssdcgtygh
What are the release dates for The Way It Was - 1974 Swaps vs- Nashua?
The Way It Was - 1974 Swaps vs- Nashua was released on: USA: 18 March 1976
What has the author Stefan J Jentzsch written?
Stefan J. Jentzsch has written: 'Kapitalmarkt-Swaps' -- subject(s): Capital market, Swaps (Finance)
What does it look like where crocodiles live?
They live in swaps.
