0
I-beam
Wiki User
∙ 11y ago
Add your answer:
Earn +20 pts
How do you explain and illustrate the insertion sort algorithm to sort a list of n numbers?
The insertion sort algorithm works by dividing a set into two subsets, where the left set is the sorted set and the right set is the unsorted set. Initially, the sorted set has just one element because a set of one can always be regarded as being sorted. The idea is that we take the first element of the unsorted set and place it at the end of the sorted set. We then repeatedly swap it with the value to its immediate left every time that value is larger than the one we're inserting. When it is not larger, the new value has found its place and we move onto the next value. We repeat the process until the unsorted set is empty.The algorithm can be implemented most efficiently using the following pseudocode:procedure insertion_sort (A, n) is input: an array reference, A, and the count of its elements, nfor i ← 1 to n-1 inclusive j ← it ← A[i]while j > 0 and A[j-1] > tA[j] ← A[j-1]j ← j - 1end whileA[j] ← tend forThe outer for loop (i) traverses forwards through the unsorted set. On each iteration of i, the first element of the unsorted set, A[j], is moved to a temporary variable, t. A[j] now marks the insertion point which is initially at the end of the sorted set. The inner while loop (j) then traverses backwards through the sorted set to find the correct insertion point. The inner loop exits when the insertion point is at the start of the array (index 0) or the value to the left of the insertion point is not greater than the temporary value. If it is greater, we move that value into the insertion point and move the insertion point one place to the left. We then begin another iteration of the inner loop. When we exit the inner loop, we move our temporary value into the insertion point and begin another iteration of the outer loop, repeating until there are no more elements in the unsorted set.You will note that we never actually perform any swaps during the inner loop. This is because a swap incurs three separate move operations. By copying the value to a temporary and moving it back when the insertion point is found, we only need one move operation in the inner loop. If the insertion point only moves one position to the left then it's effectively the same as a swap, but each subsequent move will save us two move operations which improves efficiency overall.If the insertion point happens to be at the end of the sorted set then we incur two move operations that were never actually needed (we didn't need the temporary), however this is a relatively rare case and it would actually cost more to test for that one case than it would to simply move the value twice.
Using doublelinked list insertion sort in c language?
using doublelinked list insertion sort in c language
Explain and illustrate insertion sort algorithm to short a list of n numburs?
Explain and illustrate insertion sort algorithm to short a list of n numburs
What is a double ended queue?
A double ended queue, or deque, is a queue in which you can access or modify both the head and the tail. The front pointer can be used for insertion (apart from its usual operation i.e. deletion) and rear pointer can be used for deletion (apart from its usual operation i.e. insertion)
Different type of weft insertion methods?
4
What is a Point of Insertion?
A point of insertion is also called the insertion point. The point of insertion is the place, or point, in a graphics program where the next character that you type will show on the screen. The point is typically shown with a vertical line that is blinking.
What is the difference between insertion point and cursor?
What is the deference between Insertion Point and Pointers?
What do you insert to move the insertion point?
an insertion point is where the cursor blinks and u start typing
What position the insertion point at the last editing location?
The insertion point is directly after the last character you inserted.
What happens to the insertion point when you press the backspace key and the delete key on a type document?
If you hit the Backspace key, the insertion point will move to the left. If you press the Delete key, the insertion point will stay where it is.
What indicates where the text will be inserted?
cursor's insertion point -- usually looks like a small I-beam
When you place your cursor over the insertion point to what shape does it change?
When you place your cursor over the insertion point it changes to the I bar.
Is the Insertion point shaped like a block arrow?
In most Command-line_interfaceor Text_editor, the cursor is an Underscore, a solid rectangle, or a vertical line, which may be flashing or steady, indicating where text will be placed when entered (the insertion point).
Name the two points of attachment for the skeletal muscle?
The two attachment points are the origin and insertion. The origin is the immovable (or slightly moveable point. The insertion is the movable point. The insertion always moves towards the origin.
What is a blinking vertical?
insertion point
What is a vertical bar?
insertion point
What is the flashing vertical line that indicates where text will be inserted when you start typing called?
insertion point
