Scribd
Upload
122 views6 pages

Insertion Sort Guide for CS Students

The document summarizes the insertion sort algorithm. It describes how insertion sort works by iterating through the array and inserting each element into the sorted position by shifting other elements over. It provides pseudocode and a Python implementation of insertion sort. The time complexity of insertion sort is O(n^2) as in the worst case each element may need to shift n-1 positions.

Uploaded by

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

Insertion Sort Guide for CS Students

The document summarizes the insertion sort algorithm. It describes how insertion sort works by iterating through the array and inserting each element into the sorted position by shifting other elements over. It provides pseudocode and a Python implementation of insertion sort. The time complexity of insertion sort is O(n^2) as in the worst case each element may need to shift n-1 positions.

Uploaded by

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

Al-Balqa Applied University

‫جامعة البلقاء التطبيقية‬

Prof. Oqeili Saleh Lectures

Prince Abdullah bin Ghazi Faculty


Of Communication and Information Technology
Department of Computer Science

Algorithms Design & Analysis


Insertion Sort
Insertion Sort

The basic idea of insertion sort is that one element from the
input elements is consumed in each iteration to find its correct
position i.e., the position to which it belongs in a sorted array.

It iterates the next element in the array (It compares the current element with the
largest value in the sorted array):

 If the current element is greater than the largest value in the sorted array, then it
leaves the element in its place and moves on to the next element.

Else

 It finds its correct position in the sorted array and moves it to that position. This is
done by shifting all the elements, which are larger than the current element, in the
sorted array to one position ahead.
Insertion Sort Steps

 The first step involves the comparison of the element in question


with its adjacent element.

 If the element in question can be inserted at a particular


position, then space is created for it by shifting the other
elements one position to the right and inserting the element at
the suitable position.

 The above procedure is repeated until all the element in the


array are sorted.
Insertion Sort Pseudocode

INSERTION-SORT(A)
for i = 1 to n
key ← A [i]
j←i–1
while j > = 0 and A[j] > key
A[j+1] ← A[j]
j←j–1
End while
A[j+1] ← key
End for
# Insertion Sort-Python
def insertionSort(arr):
# Traverse through 1 to len(arr)
    for i in range(1, len(arr)):
          key = arr[i]
# Shift array elements greater than the key to the right
#These elements are: arr[0..i-1.
        j = i-1
        while j >= 0 and key < arr[j] :
                arr[j + 1] = arr[j]
                j -= 1
        arr[j + 1] = key
  
 # test the program
 
arr = [5, 6, 1, 9, 3, 4]
insertionSort(arr)
for i in range (len(arr)):
    print ("% d" % arr[i])
  
Complexity of Insertion Sort

You might also like