lOMoARcPSD|30232946

Micro project of DSU Complete

Computer Technology (Brahmdevdada Mane

Polytechnic, Belati)

Brahmdevdada Mane Polytechnic

Made by Rohan karkale )

 lOMoARcPSD|30232946

program to sort an array using selection sort

Micro Project

First Year Diploma (SEM-III) in Computer

Engineering By
Under supervision of

Mr. Sourabh Patil

(Lecturer, Department of Computer
Engineering) Mr. Rohan karkale
Mr. Mahesh kasture

Department of Computer Engineering

Brahmdevdada Mane Polytechnic, Belati

2023-2024

Made by Rohan karkale

 lOMoARcPSD|30232946

Made by Rohan karkale

 lOMoARcPSD|30232946

CERTIFICATE

This is to certify that students rahul hirt sisode , Third Semester of Diploma in
Computer Engineering of Brahmdevdada Mane Polytechnic, Belati (Code: 0993) have
submitted the micro-project and defended term work micro-project for the Academic Year
2023-24 as prescribed in the curriculum.

Place: Belati

Date:

Project Guide Head of Department Principal

Made by Rohan karkale

 lOMoARcPSD|30232946

A PROPOSAL FOR MICRO – PROJECT

2.0 Aim/Benefits of the Micro – Project:

• program to sort an array using selection sort

• How selection sorts works?

Made by Rohan karkale

 lOMoARcPSD|30232946

5.0 Actual Resources Used

Sr. Name of Resources

Specifications Quantity Remarks
No. / material
Use computer
With MS Office &
1. Computer 1 available in
Internet
language lab
Use printer
B & W Printer
2. Printer 1 available at
computer lab
3. Printing Papers A4 size 1
4. 1

• Enrolments no of students
• 1] Rohan Karkale.(2209930071) Enrolment No
2] Mahesh Kasture.

Signature of guide

Made by Rohan karkale

 lOMoARcPSD|30232946

Topic: Program to sort an array using selection sort

Algorithm-:
Step 1 − Set MIN to location 0
Step 2 − Search the minimum element in the list
Step 3 − Swap with value at location MIN
Step 4 − Increment MIN to point to next element
Step 5 − Repeat until list is sorted

• How Selection Sort Works?

• Consider the following depicted array as an example.

Made by Rohan karkale

 lOMoARcPSD|30232946

• For the first position in the sorted list, the whole list is scanned sequentially. The first
position where 14 is stored presently, we search the whole list and find that 10 is the
lowest value.

• So we replace 14 with 10. After one iteration 10, which happens to be the minimum
value in the list, appears in the first position of the sorted list.

• For the second position, where 33 is residing, we start scanning the rest of the list in a
linear manner.

• We find that 14 is the second lowest value in the list and it should appear at the second
place. We swap these values.

After two iterations, two least values are positioned at the beginning in a sorted manner.

Made by Rohan karkale

 lOMoARcPSD|30232946

The same process is applied to the rest of the items in the array.
Following is a pictorial depiction of the entire sorting process −

Now, let us learn some programming aspects of selection sort.

Made by Rohan karkale

 lOMoARcPSD|30232946

Made by Rohan karkale

 lOMoARcPSD|30232946

Complexity
1. Number of comparisons:(n-1) + (n-2) + (n-3) +.....+ 1 = n(n-1)/2 nearly equals to
n2 Complexity = O(n2)Also, we can analyze the complexity by simply observing
the number of loops. There are 2 loops so the complexity is n*n = n2.Time
Complexities: 1. Worst Case Complexity: O(n2) If we want to sort in ascending
order and the array is in descending order then, the worst case occurs. 2. Best
Case Complexity: O(n2) 3. Average Case Complexity: O(n2) It occurs when the
elements …

1. Time Complexity
Case Time Complexity
Best Case 2
O(n )
Average Case O(n2)
Worst Case O(n2)
o Best Case Complexity - It occurs when there is no sorting required,
i.e. the array is already sorted. The best-case time complexity of
selection sort is O(n2).
o Average Case Complexity - It occurs when the array elements are in
jumbled order that is not properly ascending and not properly
descending. The average case time complexity of selection sort
is O(n2).
o Worst Case Complexity - It occurs when the array elements are
required to be sorted in reverse order. That means suppose you have
to sort the array elements in ascending order, but its elements are in

Made by Rohan karkale

 lOMoARcPSD|30232946

descending order. The worst-case time complexity of selection sort

is O(n2).

2. Space Complexity
Space Complexity o(1)
Stable yes
o The space complexity of selection sort is O(1). It is because, in
selection sort, an extra variable is required for swapping.

Implementation of selection sort

Now, let's see the programs of selection sort in different programming
languages.

Program: Write a program to implement selection sort in C language.

1. #include <stdio.h>
2.
3. void selection(int arr[], int n)
4. {
5. int i, j, small;
6.
7. for (i = 0; i < n-1; i++) // One by one move boundary of unsorted
subarray
8. {
9. small = i; //minimum element in unsorted array
10.
11. for (j = i+1; j < n; j++)
12. if (arr[j] < arr[small])
13. small = j;
14. // Swap the minimum element with the first element
15. int temp = arr[small];
16. arr[small] = arr[i];
17. arr[i] = temp;

Made by Rohan karkale

 lOMoARcPSD|30232946

18. }
19. }
20.
21. void printArr(int a[], int n) /* function to print the array */
22.{
23. int i;
24. for (i = 0; i < n; i++)
25. printf("%d ", a[i]);
26.}
27.
28.int main()
29. {
30. int a[] = { 12, 31, 25, 8, 32, 17 };
31. int n = sizeof(a) / sizeof(a[0]);
32. printf("Before sorting array elements are - \n");
33. printArr(a, n);
34. selection(a, n);
35. printf("\nAfter sorting array elements are - \n");
36. printArr(a, n);
37. return 0;
38.}

Output:

After the execution of above code, the output will be -

Program: Write a program to implement selection sort in C++ language.

1. #include <iostream>
2.
3. using namespace std;
4.

Made by Rohan karkale

 lOMoARcPSD|30232946

5. void selection(int arr[], int n)

6. {
7. int i, j, small;
8.
9. for (i = 0; i < n-1; i++) // One by one move boundary of unsorted
subarray
10. {
11. small = i; //minimum element in unsorted array
12.
13. for (j = i+1; j < n; j++)
14. if (arr[j] < arr[small])
15. small = j;
16. // Swap the minimum element with the first element
17. int temp = arr[small];
18. arr[small] = arr[i];
19. arr[i] = temp;
20. }
21. }
22.
23. void printArr(int a[], int n) /* function to print the array */
24.{
25. int i;
26. for (i = 0; i < n; i++)
27. cout<< a[i] <<" ";
28.}
29.
30.int main()
31. {
32. int a[] = { 80, 10, 29, 11, 8, 30, 15 };
33. int n = sizeof(a) / sizeof(a[0]);
34. cout<< "Before sorting array elements are - "<<endl;
35. printArr(a, n);
36. selection(a, n);
37. cout<< "\nAfter sorting array elements are - "<<endl;

Made by Rohan karkale

 lOMoARcPSD|30232946

38. printArr(a, n);

39.
40. return 0;
41. }

Output:

After the execution of above code, the output will be -

• Algorithm for selection sort

SELECTION SORT(arr, n)

Step 1: Repeat Steps 2 and 3 for i = 0 to n-1

Step 2: CALL SMALLEST(arr, i, n, pos)

Step 3: SWAP arr[i] with arr[pos]

[END OF LOOP]

Step 4: EXIT

SMALLEST (arr, i, n, pos)

Step 1: [INITIALIZE] SET SMALL =

arr[i] Step 2: [INITIALIZE] SET pos = i

Step 3: Repeat for j = i+1 to n

if (SMALL > arr[j])

Made by Rohan karkale

 lOMoARcPSD|30232946

SET SMALL = arr[j]

SET pos = j

[END OF if]

[END OF LOOP]

Step 4: RETURN pos

Made by Rohan karkale