1 of 15

PROBLEM SOLVING TECHNIQUES

By

​

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 the selection sort.
  • Algorithm development: The key point in the sorting process is, the next smallest value must be found and placed in order.
  • Consider the unsorted array:

​

​

  • Develop a mechanism that converts the unsorted array to the sorted array:

​

Dept of CSE

2025-26

SORTING BY SELECTION

PVPSIT (Autonomous)

Problem Solving Techniques (20ES1103)

3 of 15

  • The following two steps are required to accomplish the task:
  • Find the smallest element in the unsorted array;
  • Place the smallest element in position a[1].

​

​

  • The following construct can be used to find the smallest element:

Dept of CSE

2025-26

PVPSIT (Autonomous)

Problem Solving Techniques (20ES1103)

4 of 15

Dept of CSE

2025-26

PVPSIT (Autonomous)

Problem Solving Techniques (20ES1103)

5 of 15

  • Then assign it to a[1].

a[1]:=min

  • After performing above two steps we get:

​

​

  • We lost the 20 that was there originally. There are two 3s in the array.
  • To avoid these problems before placing the 3 in position a[1] we will need to save the value (i.e. the 20) that is already there.
  • Then place the 20 at the position of 3.

​

Dept of CSE

2025-26

PVPSIT (Autonomous)

Problem Solving Techniques (20ES1103)

6 of 15

Dept of CSE

2025-26

PVPSIT (Autonomous)

Problem Solving Techniques (20ES1103)

7 of 15

  • To achieve these two changes we need a mechanism that not only finds the minimum but also remembers the array location where the minimum is currently stored.
  • This step can be added.

Dept of CSE

2025-26

PVPSIT (Autonomous)

Problem Solving Techniques (20ES1103)

8 of 15

  • The 20 and the 3 can then be swapped using the following statements:

Dept of CSE

2025-26

PVPSIT (Autonomous)

Problem Solving Techniques (20ES1103)

9 of 15

Dept of CSE

2025-26

PVPSIT (Autonomous)

Problem Solving Techniques (20ES1103)

10 of 15

Dept of CSE

2025-26

PVPSIT (Autonomous)

Problem Solving Techniques (20ES1103)

11 of 15

Dept of CSE

2025-26

PVPSIT (Autonomous)

Problem Solving Techniques (20ES1103)

12 of 15

begin

for i:=1 to n-1 do

begin

min:= a[i];

p:=i;

for j:=i+1 to n do

if a[j]<min then

begin

min:=a[j];

p:=j

end;

a[p]:=a[i];

a[i]:=min

end

end

Dept of CSE

2025-26

Pseudo-code

PVPSIT (Autonomous)

Problem Solving Techniques (20ES1103)

13 of 15

Dept of CSE

2025-26

PVPSIT (Autonomous)

Problem Solving Techniques (20ES1103)

14 of 15

  • Notes on design:
  • In analyzing the selection sort there are three parameters that are important:
  • The number of comparisons made
  • The number of exchanges made
  • The number of times the minimum is updated.
  • The first time through the inner loop n-1 comparisons are made, the second time n-2, the third time n-3, and finally 1 comparison is made.
  • The number of comparisons is therefore always:
  • nc=(n-1)+(n-2)+(n-3)+ … + 1 = n(n-1)/2 (by Gauss’ formula)
  • The number of exchanges is always (n-1) because it is equal to the number of times the outer loop is executed.

​

Dept of CSE

2025-26

PVPSIT (Autonomous)

Problem Solving Techniques (20ES1103)

15 of 15

  • Applications:
  • Sorting only small amount of data – much more efficient methods are used for large data sets.

​

  • Supplementary problems (5.2.1)
  • Sort an array into descending order.

​

Dept of CSE

2025-26

PVPSIT (Autonomous)

Problem Solving Techniques (20ES1103)