Data Structure and Algorithms based on the Object-oriented programming (OOP) where some are the base of OOP for instant inheritance, polymorphism, Encapsulation and Abstraction etc. Now we will start learning data structures in Programming languages such as Linked list, arrays, Structs, Classes, Queues, Stacks etc.
Today’s Concept:
Selection Sort Data Structure
Prerequisite of
this Lab is all those students who have basic concepts on C++ Programming such
as Syntax of Language, concept of functions, pointers, datatypes etc. Visual
Studio 2012 and onward version will be used for implementation and programming
tasks assigned in the Lab.
Selection sort algorithm works on unsorted arrays after
completion array entries will be sorted in order such as ascending or descending.
Selection Sort repeatedly finds the minimum value from the unsorted arrays and
place the sorted part or minimum value (ascending order) at the beginning of the
array and keeps on performing until the array is sorted. For this selection sort
maintains two subarrays for sorting array’s elements properly. It maintained
the subarrays in such a way that one part is sorted part and the other part in
to be sorted after or unsorted part.
In every iteration of selection sort Algorithm, the minimum
element (ascending order) from the unsorted subarray (first part) is
picked and moved to the sorted subarray (second part).
Example:
Solving using Selection sort:
11 25 12 22 64
11 12 25 22 64
11 12 22 25 64
11 12 22 25 64
Time Complexity: O(n2) as there are two nested loops.
Auxiliary Space: O(1)
Advantage of using Selection sort:
Selection sort is it never makes more than O(n) swaps
(value changing operations) and can be useful when memory write is a
costly operation.
Implementation of Selection Sort using C++:
#include <iostream>
using namespace std;
void selectionSortAlgo(int arr[], int n)
{
int
min_index=0;
for
(int i = 0; i < n-1; i++)
{
min_index = i;
for (int j = i+1; j < n; j++)
{
if (arr[j] > arr[min_index ]) //accending order sorting
min_index = j;
int temp = arr[min_index ];
arr[min_index ] = arr[j];
arr[j] = temp;
}
}
}
void print(int *arr, int size)
{
int
i;
for
(i=0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}
int main()
{
int
arr[] = {10,5,6,7,8};
int
n = sizeof(arr)/sizeof(arr[0]);
selectionSortAlgo(arr, n);
cout << "Sorted array:"<<endl;
print(arr, n);
system("pause");
return 0;
}
Lab Activity Tasks:
- read the manual and just write what you understand don't try to copy and past from other sources.
- Create C++ program to run same code given as Example and take screenshot for submission.
- You have implemented Selection sort on an unsorted array of integer values to sort that array's values in descending order.
- Write a C++ program to sort arrays of strings using Selection sort for example strings can be {"rana,"marwat","hussain"} after sorting ascending order string will be {"hussain","marwat","rana"}.
Tasks Submission:
Post a Comment