Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item
at a time. It is
much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort.
However, insertion sort provides several advantages:
Simple implementation
Efficient for (quite) small data sets
Adaptive (i.e., efficient) for data sets that are already substantially sorted: the time complexity is O(n + d), where
d is the number of inversions
More efficient in practice than most other simple quadratic (i.e., O(n2)) algorithms such as selection sort or
bubble sort; the best case (nearly sorted input) is O(n)
Stable; i.e., does not change the relative order of elements with equal keys
In-place; i.e., only requires a constant amount O(1) of additional memory space
Online; i.e., can sort a list as it receives it
Algorithm
for i = 2:n,
for (k = i; k > 1 and a[k] < a[k-1]; k--)
swap a[k,k-1]
→ invariant: a[1..i] is sorted
End
By Deependra 1
Properties
Stable
O(1) extra space
O(n2) comparisons and swaps
Adaptive: O(n) time when nearly sorted
Very low overhead
Discussion
Although it is one of the elementary sorting algorithms with O(n2) worst-case time, insertion sort is the algorithm of
choice either when the data is nearly sorted (because it is adaptive) or when the problem size is small (because it has
low overhead).
For these reasons, and because it is also stable, insertion sort is often used as the recursive base case (when the problem
size is small) for higher overhead divide-and-conquer sorting algorithms, such as merge sort or quick sort.
Bubble Sort
Step-by-step example
Let us take the array of numbers "5 1 4 2 8", and sort the array from lowest number to greatest number using bubble
sort. In each step, elements written in bold are being compared. Three passes will be required.
First Pass:
( 5 1 4 2 8 ) ( 1 5 4 2 8 ), Here, algorithm compares the first two elements, and swaps since 5 > 1.
( 1 5 4 2 8 ) ( 1 4 5 2 8 ), Swap since 5 > 4
( 1 4 5 2 8 ) ( 1 4 2 5 8 ), Swap since 5 > 2
( 1 4 2 5 8 ) ( 1 4 2 5 8 ), Now, since these elements are already in order (8 > 5), algorithm does not swap them.
Second Pass:
(14258) (14258)
( 1 4 2 5 8 ) ( 1 2 4 5 8 ), Swap since 4 > 2
(12458) (12458)
(12458) (12458)
Now, the array is already sorted, but our algorithm does not know if it is completed. The algorithm needs one whole
pass without any swap to know it is sorted.
Third Pass:
(12458) (12458)
(12458) (12458)
(12458) (12458)
(12458) (12458)
By Deependra 2
Implementation
Pseudocode implementation
The algorithm can be expressed as (0-based array):
procedure bubbleSort( A : list of sortable items )
n = length(A)
repeat
swapped = false
for i = 1 to n-1 inclusive do
/* if this pair is out of order */
if A[i-1] > A[i] then
/* swap them and remember something changed */
swap( A[i-1], A[i] )
swapped = true
end if
end for
until not swapped
end procedure
Optimizing bubble sort
The bubble sort algorithm can be easily optimized by observing that the n-th pass finds the n-th largest element and
puts it into its final place. So, the inner loop can avoid looking at the last n-1 items when running for the n-th time:
procedure bubbleSort( A : list of sortable items )
n = length(A)
repeat
swapped = false
for i = 1 to n-1 inclusive do
if A[i-1] > A[i] then
swap(A[i-1], A[i])
swapped = true
end if
end for
n = n - 1
until not swapped
end procedure
More generally, it can happen that more than one element is placed in their final position on a single pass. In particular,
after every pass, all elements after the last swap are sorted, and do not need to be checked again. This allows us to skip
By Deependra 3
over a lot of the elements, resulting in about a worst case 50% improvement in comparison count (though no
improvement in swap counts), and adds very little complexity because the new code subsumes the "swapped" variable:
To accomplish this in pseudocode we write the following:
procedure bubbleSort( A : list of sortable items )
n = length(A)
repeat
newn = 0
for i = 1 to n-1 inclusive do
if A[i-1] > A[i] then
swap(A[i-1], A[i])
newn = i
end if
end for
n = newn
until n = 0
end procedure
10.2.1 Insertion Sort
This is a naturally occurring sorting method exemplified by a card player arranging the cards dealt to him. He picks up
the cards as they are dealt and inserts them into the required position. Thus at every step, we insert an item into its
proper place in an already ordered list. We will illustrate insertion sort with an example (refer to Figure 10.1) before
presenting the formal algorithm.
Example : Sort the following list using the insertion sort method:
Figure 10.1: Insertion sort
By Deependra 4
Thus to find the correct position search the list till an item just greater than the target is found. Shift all the items from
this point one down the list. Insert the target in the vacated slot. Repeat this process for all the elements in the list. This
results in sorted list.
10.2.2 Bubble Sort
In this sorting algorithm, multiple swappings take place in one pass. Smaller elements move or ‘bubble’ up to the top of
the list, hence the name given to the algorithm.
In this method, adjacent members of the list to be sorted are compared.If the item on top is greater than the item
immediately below it, then they are swapped. This process is carried on till the list is sorted.
The detailed algorithm follows:
Algorithm: BUBBLE SORT
1. Begin
2. Read the n elements Sorting
3. for i=1 to n
for j=n downto i+1
if a[j] <= a[j-1]
swap(a[j],a[j-1])
4. End // of Bubble Sort
Total number of comparisons in Bubble sort :
= (N-1) +(N-2) . . . + 2 + 1
= (N-1)*N / 2 =O(N2)
This inefficiency is due to the fact that an item moves only to the next position in each pass.
By Deependra 5
LINKED LISTS – IMPLEMENTATION
The Linked list is a chain of structures in which each structure consists of data as well as pointer, which stores the address
(link) of the next logical structure in the list.
A linked list is a data structure used to maintain a dynamic series of data. Think of a linked list as a line of bogies of train
where each bogie is connected on to the next bogie. If you know where the first bogie is, you can follow its link to the
next one. By following links, you can find any bogie of the train. When you get to a bogie that isn’t holding (linked) on to
another bogie, you know you are at the end.
Linked lists work in the same way, except programmers usually refer to nodes instead of bogies. A single node is defined
in the same way as any other user defined type or object, except that it also contains a pointer to a variable of the same
type as itself.
We will be seeing how the linked list is stored in the memory of the computer. In the following Figure 3.1, we can see that
start is a pointer which is pointing to the node which contains data as madan and the node madan is pointing to the node
mohan and the last node babu is not pointing to any node. 1000,1050,1200 are memory addresses.
ALGORITHM (Insertion of element into a linked list)
Step 1 Begin
Step 2 if the list is empty or a new element comes before the start (head) element, then insert the new element as start
element.
Step 3 else, if the new element comes after the last element, then insert the new element as the end element.
Step 4 else, insert the new element in the list by using the find function, find function returns the address of the found
element to the insert_list function.
Step 5 End.
By Deependra 6
ALGORITHM (Deletion of an element from the linked list)
Step 1 Begin
Step 2 if the list is empty, then element cannot be deleted
Step 3 else, if element to be deleted is first node, then make the start (head) to point to the second element.
Step 4 else, delete the element from the list by calling find function and returning the found address of the element.
Step 5 End
Linked Lists - Insertion
Consider Fig. 3.4.h.1 which shows a linked list and a free list. The linked list is created by removing cells from the front
of the free list and inserting them in the correct position in the linked list.
Head Data Data Data Data
Free Data Data Data
Fig. 3.4.h.1
Now suppose we wish to insert an element between the second and third cells in the linked list. The pointers have to be
changed to those in Fig. 3.4.h.2.
HEAD Data Data Data Data
FREE Data Data Data
Fig. 3.4.h.2
The algorithm must check for an empty free list as there is then no way of adding new data. It must also check to see if
the new data is to be inserted at the front of the list. If neither of these are needed, the algorithm must search the list
to find the position for the new data. The algorithm is given below.
1. Check that the free list is not empty.
2. If it is empty report an error and stop.
3. Set NEW to equal FREE.
4. Remove the node from the stack by setting FREE to pointer in cell pointed to by FREE.
5. Copy data into cell pointed to by NEW.
6. Check for an empty list by seeing if HEAD is NULL
7. If HEAD is NULL then
a. Pointer in cell pointed to by NEW is set to NULL
b. Set HEAD to NEW and stop.
By Deependra 7
8. If data is less than data in first cell THEN
a. Set pointer in cell pointed to by NEW to HEAD.
b. Set HEAD to NEW and stop
9. Search list sequentially until the cell found is the one immediately before the new cell that is to be inserted. Call
this cell PREVIOUS.
10. Copy the pointer in PREVIOUS into TEMP.
11. Make the pointer in PREVIOUS equal to NEW
12. Make the pointer in the cell pointed to by NEW equal to TEMP and stop.
Linked Lists - Deletion
Suppose we wish to delete the third cell in the linked list shown in Fig. 3.4.h.1. The result is shown in Fig. 3.4.h.3.
Head Data Data Data Data
Free Data Data Data
Fig. 3.4.h.3
In this case, the algorithm must make sure that there is something in the list to delete.
1. Check that the list is not empty.
2. If the list is empty report an error and stop.
3. Search list to find the cell immediately before the cell to be deleted and call it PREVIOUS.
4. If the cell is not in the list, report an error and stop.
5. Set TEMP to pointer in PREVIOUS.
6. Set pointer in PREVIOUS equal to pointer in cell to be deleted.
7. Set pointer in cell to be deleted equal to FREE.
8. Set FREE equal to TEMP and stop.
Linked Lists - Amendment
Amendments can be done by searching the list to find the cell to be amended.
The algorithm is
1. Check that the list is not empty.
2. If the list is empty report an error and stop.
3. Search the list to find the cell to be amended.
4. Amend the data but do not change the key.
5. Stop.
Linked Lists - Searching
Assuming that the data in a linked list is in ascending order of some key value, the following algorithm explains how to
find where to insert a cell containing new data and keep the list in ascending order. It assumes that the list is not empty
and the data is not to be inserted at the head of the list.
By Deependra 8
Set POINTER equal to HEAD
REPEAT
Set NEXT equal to pointer in cell pointed to by POINTER
If new data is less than data in cell pointed to by POINTER then set POINTER equal to NEXT
UNTIL
Note: A number of methods have been shown here to describe algorithms associated with linked lists. Any method is
acceptable provided it explains the method. An algorithm does not have to be in pseudo code, indeed, the sensible way
of explaining these types of algorithm is often by diagram.
By Deependra 9
By Deependra 10
