Scribd
Upload
12 views27 pages

Slide 7.pptx-1

These are the Java algorithm lessons that we're studying them at university.

Uploaded by

farrokhisar
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
12 views27 pages

Slide 7.pptx-1

These are the Java algorithm lessons that we're studying them at university.

Uploaded by

farrokhisar
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 27

Algorithm

Insertion Sort

► Insertion sort is one of the simplest sorting algorithms for the reason that it
sorts a single element at a particular instance. It is not the best sorting
algorithm in terms of performance, but it's slightly more efficient than
selection sort and bubble sort in practical scenarios. It is an intuitive sorting
technique.
► Let's consider the example of cards to have a better understanding of the
logic behind the insertion sort.
► Suppose we have a set of cards in our hand, such that we want to arrange
these cards in ascending order. To sort these cards, we have a number of
intuitive ways.
Continued…

► One such thing we can do is initially we can hold all of the cards in our left
hand, and we can start taking cards one after other from the left hand,
followed by building a sorted arrangement in the right hand.
► Assuming the first card to be already sorted, we will select the next
unsorted card. If the unsorted card is found to be greater than the
selected card, we will simply place it on the right side, else to the left
side. At any stage during this whole process, the left hand will be
unsorted, and the right hand will be sorted.
► In the same way, we will sort the rest of the unsorted cards by placing
them in the correct position. At each iteration, the insertion algorithm
places an unsorted element at its right place.
ALGORITHM: INSERTION SORT (A)

1. 1. for j = 2 to A.length
2. 2. key = A[j]
3. 3. // Insert A[j] into the sorted sequence A[1.. j - 1]
4. 4. i = j - 1
5. 5. while i > 0 and A[i] > key
6. 6. A[i + 1] = A[i]
7. 7. ii = i -1
8. 8. A[i + 1] = key
How Insertion Sort Works

► We will start by assuming the very first element of the array is already
sorted. Inside the key, we will store the second element.
► Next, we will compare our first element with the key, such that if the
key is found to be smaller than the first element, we will interchange
their indexes or place the key at the first index. After doing this, we will
notice that the first two elements are sorted.
Continued…

► Now, we will move on to the third element and compare it with the left-hand
side elements. If it is the smallest element, then we will place the third
element at the first index.
► Else if it is greater than the first element and smaller than the second
element, then we will interchange its position with the third element and
place it after the first element. After doing this, we will have our first three
elements in a sorted manner.
Continued…

► Similarly, we will sort the rest of the elements and place them in their correct
position.
► Consider the following example of an unsorted array that we will sort
with the help of the Insertion Sort algorithm.
► A = (41, 22, 63, 14, 55, 36)
► Initially,
1st Iteration:

► Set key = 22
► Compare a1 with a0
Continued…

► Since a0 > a1, swap both of them.


2nd Iteration:

► Set key = 63
► Compare a2 with a1 and a0
Continued…

► Since a2 > a1 > a0, keep the array as it is.


3rd Iteration:

► Set key = 14
► Compare a3 with a2, a1 and a0
Continued…

► Since a3 is the smallest among all the elements on the left-hand side,
place a3 at the beginning of the array.
4th Iteration:

► Set key = 55
► Compare a4 with a3, a2, a1 and a0.
Continued…

► As a4 < a3, swap both of them.


5th Iteration:

► Set key = 36
► Compare a5 with a4, a3, a2, a1 and a0.
Continued…

► Since a5 < a2, so we will place the elements in their correct positions.
Continued…
Complexity Analysis of Insertion Sort

► Input: Given n input elements.


► Output: Number of steps incurred to sort a list.
► Logic: If we are given n elements, then in the first pass, it will
make n-1 comparisons; in the second pass, it will do n-2; in the third
pass, it will do n-3 and so on. Thus, the total number of comparisons
can be found by;
Continued…
Continued…

► Therefore, the insertion sort algorithm encompasses a time


complexity of O(n2) and a space complexity of O(1) because it
necessitates some extra memory space for a key variable to perform
swaps.
Time Complexities:

• Best Case Complexity: The insertion sort algorithm has a best-case


time complexity of O(n) for the already sorted array because here, only
the outer loop is running n times, and the inner loop is kept still.
• Average Case Complexity: The average-case time complexity for the
insertion sort algorithm is O(n2), which is incurred when the existing
elements are in jumbled order, i.e., neither in the ascending order nor
in the descending order.
• Worst Case Complexity: The worst-case time complexity is also O(n2),
which occurs when we sort the ascending order of an array into the
descending order.
In this algorithm, every individual element is compared with the rest
of the elements, due to which n-1 comparisons are made for every
nth element.
Continued…

► The insertion sort algorithm is highly recommended, especially when a few


elements are left for sorting or in case the array encompasses few elements.
Space Complexity

► The insertion sort encompasses a space complexity of O(1) due to the


usage of an extra variable key.
►
Insertion Sort Applications

► The insertion sort algorithm is used in the following cases:


• When the array contains only a few elements.
• When there exist few elements to sort.
Advantages of Insertion Sort

► It is simple to implement.
► It is efficient on small datasets.
► It is stable (does not change the relative order of elements with equal keys)
► It is in-place (only requires a constant amount O (1) of extra memory space).
► It is an online algorithm, which can sort a list when it is received.
?

You might also like