1 of 15

PROBLEM SOLVING TECHNIQUES

​

​

Dept. of CSE

PVPSIT, Kanuru.

​

​

PRASAD V. POTLURI SIDDHARTHA INSTITUTE OF TECHNOLOGY

2 of 15

  • Problem: Given a randomly ordered set of n integers, sort them into non-descending order using an insertion method.

​

  • Algorithm development: Sorting by insertion is one of the more obvious and natural ways to sort information. It quite closely the procedure that card players often use.
  • Central idea of the algorithm for building the solution is by inserting an element from the unordered part into the currently partially ordered solution, extending it by one element.
  • This mechanism is suggestive of a selection sort where we selected the smallest element in the unordered part and placed it on the end of the sorted part.

B. Vinay Kumar

Wednesday, January 25, 2023

SORTING BY INSERTION

PVPSIT (Autonomous)

Problem Solving Techniques

3 of 15

  • We have:

​

​

​

  • A simple, systematic, and alternative way we could choose the next item to be inserted is to always pick the first element in the unordered part (i.e. x in our example).
  • We then need to appropriately insert x into the ordered part and, in the process, extend the ordered section by one element.

B. Vinay Kumar

Wednesday, January 25, 2023

PVPSIT (Autonomous)

Problem Solving Techniques

4 of 15

B. Vinay Kumar

Wednesday, January 25, 2023

PVPSIT (Autonomous)

Problem Solving Techniques

5 of 15

B. Vinay Kumar

Wednesday, January 25, 2023

PVPSIT (Autonomous)

Problem Solving Techniques

6 of 15

  • Initially the whole array is in an unordered state.
  • For this starting condition x will need to be the second element and a[1] the “ordered part”.
  • The ordered part is extended by first inserting the second element, then the third element. and so on.
  • For sentinel value

B. Vinay Kumar

Wednesday, January 25, 2023

PVPSIT (Autonomous)

Problem Solving Techniques

7 of 15

  • To make room for x to be inserted all elements greater than x need to be moved up one place.
  • Starting with j:=i the following steps to be done:

B. Vinay Kumar

Wednesday, January 25, 2023

PVPSIT (Autonomous)

Problem Solving Techniques

8 of 15

  • In our Approach place minimum element x as a sentinel at a[1].
  • Once the minimum is put in place the first two elements must be ordered so we can start by inserting the third element.

B. Vinay Kumar

Wednesday, January 25, 2023

PVPSIT (Autonomous)

Problem Solving Techniques

9 of 15

B. Vinay Kumar

Wednesday, January 25, 2023

PVPSIT (Autonomous)

Problem Solving Techniques

10 of 15

B. Vinay Kumar

Wednesday, January 25, 2023

PVPSIT (Autonomous)

Problem Solving Techniques

11 of 15

Pseudo-code:

begin

first:=a[1]; p:=1;

for i:= 2 to n do

if a[i] < first then

begin

first := a[i];

p := i

end;

a[p] := a[1];

a[1] := first;

​

B. Vinay Kumar

Wednesday, January 25, 2023

PVPSIT (Autonomous)

Problem Solving Techniques

12 of 15

for i:=3 to n do

begin

x := a[i]

j := i

while x < a[j-1] do

begin

a[j]:=a[j-1]

j := j - 1

end

a[j] := x

end

end

B. Vinay Kumar

Wednesday, January 25, 2023

PVPSIT (Autonomous)

Problem Solving Techniques

13 of 15

B. Vinay Kumar

Wednesday, January 25, 2023

PVPSIT (Autonomous)

Problem Solving Techniques

14 of 15

  • The insertion sort is used when: The array is has a small number of elements; There are only a few elements left to be sorted.
  • This is because it has a best case and average time complexity of O(n) and a worst case time complexity of O(n^2), which makes it efficient for small lists.
  • It is a stable sort.
  • Additionally, insertion sort can be easily implemented in-place, which means that it doesn't require additional memory to sort the list.
  • Applications:
  • Where there are relatively small data sets.
  • Supplementary problems (5.4.2)

​

B. Vinay Kumar

Wednesday, January 25, 2023

PVPSIT (Autonomous)

Problem Solving Techniques

15 of 15

B. Vinay Kumar

Wednesday, January 25, 2023

PVPSIT (Autonomous)

Problem Solving Techniques