Selection Sort Algorithm in C++

The Selection Sort Algorithm is one of the popular sorting algorithms that is used to arrange the array of elements in sorted order either in ascending or descending order. 

In the selection sort algorithm (considering ascending order), we repeatedly find the smallest element from the unsorted part of the array and put them at the beginning. In every iteration, we divide the given array into a sorted and unsorted part and we move the smallest element from the unsorted part to the sorted part. 

Working of Selection Sort Algorithm.

Steps for Selection Sort Algorithm:

• Initialize a min_index value with the initial index as 0.
• Traverse the array to find the index of the minimum value of the given array. 
• If any index value is smaller than min_index is found then we will swap both the value. It might be possible that more than one smaller value is present in that case you need to pick the smallest one only.
• In the next iteration increment the min_index so it will point to the next value and then again start traversing the unsorted part (right-hand side of min_index) of the array to get the next smaller value.
• Keep repeating the above steps until the entire array gets sorted. 

Below is the C++ Code Implementation for Selection Sort Algorithm.

//Program for Selection sort algorithm in C++
#include<iostream>
using namespace std;

void selectionSort(int arr[], int n){
    int min_index;

    //First loop keep on descreasing the size 
    //of unsorted array
    for(int i = 0; i < n-1; i++){
        min_index = i;
        //Second loop to find the smalles element
        //from unsorted subarray
        for(int j = i+1; j < n; j++){
            if(arr[j] < arr[min_index])
                min_index = j;
        }
        //swape the minimum element with ith element
        if(min_index != i)
            swap(arr[i], arr[min_index]);
    }
}

int main(){
    int arr[] = {10, 23, 5, 8, 21, 15};
    int n = sizeof(arr)/sizeof(arr[0]);

    selectionSort(arr, n);

    cout<<"Sorted Array:";
    for(int i = 0; i < n; i++){
        cout<<arr[i]<<" ";
    }
}

Output:

Sorted Array:5 8 10 15 21 23

Time Complexity: The Time complexity of the Selection Sort Algorithm is O(n^2) as we are using two nested loops one is for selecting the current minimum element and the next loop is to find the minimum element out of the remaining unsorted array. 

Space Complexity: The Space complexity of the Selection sort is O(1) as we are not using any extra space for storing any kind of value except min_index and two swapping values.

See more:

(getButton) #text=(Insertion Sort Algorithm) #icon=(link) #color=(#2339bd)

(getButton) #text=(Bubble Sort Algorithm) #icon=(link) #color=(#2339bd)

(getButton) #text=(Merge Sort Algorithm) #icon=(link) #color=(#2339bd)

(getButton) #text=(Quick Sort Algorithm) #icon=(link) #color=(#2339bd)

Array Data Structure in C/C++

An Array is a linear Data Structure that contains a number of data values of the same type stored at contiguous memory locations. 

Before you start learning more about Array you must know about Data Structure. Data Structure is a way of organizing and storing data and each data structure is designed to organize data to suit a specific purpose. 

Below is the example of Array Data Structure which we can visualize as a large chunk of memory divided into a smaller block of memory of equal size and each block is capable of storing a data value of same type.

In the above example, you can observe that we can have different kinds of Array Data Structure like Integer Array or Character Array based on the type of value we are storing in it. All the elements of an array are arranged in a sequential manner you can access any element of an array using the index value like a[4] = 21. This is an example of a one-dimensional Array.

Now as you know what a one-dimensional array looks like, let's understand,

How to Declare and Define One-Dimensional Array?

The syntax of declaring a 1D array is like first of all you have to define the data type of the array then the name of the array and the number of elements you want to store in this array.

Syntax: data_type name of the array[no. of elements];

Example: int arr [5];

Here you are not only declaring the array you are also defining the array by providing the detail of the number of elements you want to store because based on this compiler will allocate a contiguous block of memory of size  = 5*sizeof(int) where the size of an integer depends on machines.

Note: The length of an array can be specified by any positive integer constant expression and specifying the length of an array using a macro is considered to be an excellent practice so that if there is any change in array size you don't need to update it everywhere. 

#define N 15

int arr[N];(alert-success)

How to Access the One-Dimensional Array elements?

To access any array element, you just need to specify the array name with the index value of that particular element in the square bracket. Usually, most of the time we use 0-based indexing so if the size of the array is declared as 5 then the last element is going to be present at index 4 (length -1) and the first element is going to be present at index 0.

Syntax: array_name[index];

Example: 
Accessing the last element of the array: arr[4];
Accessing the first element of the array: arr[0];

How to initialize One Dimensional Array?

There are multiple methods of initializing a 1D array here we are going to see four different methods. 

Method 1: In this, you have declared the data type and size of the array and you can initialize the array element inside curly brackets and the number of elements present inside the bracket should be equal to the size of the array.

int arr[5] = {3, 5, 6, 9, 12};

Method 2: In this, you don't need to declare the array size in advance you can directly initialize the array elements inside curly brackets, and based on the number of elements present you can calculate the size of the array.

int arr[] = {3, 5, 6, 9, 12};

Method 3: In this, you first declare the array with the number of elements you want to store in that array, and then using the index value you can initialize the element one by one.

int arr[5];

arr[0] = 3;

arr[1] = 5;

arr[2] = 6;

arr[3] = 9;

arr[4] = 12;

Method 4: In this, you first declare the array with the number of elements you want to store, and then you run a for-loop and take the element as input from the user and which will then initialize inside the array one by one.

int arr[5];

for(int i = 0; i < 5; i++){

   cin >> arr[i];

}

Note: If the number of elements you initialize is lesser than the length of the array then in that case the remaining locations of the array are filled by value 0. But make sure that must have to specify at least 1 element for this. It cannot be completely empty and it is also not allowed to add more elements than the length of an array.

int arr[10] = {5, 7, 9, 11, 5, 21};

All the remaining elements of array will automatically fill by 0

int arr[10] = {5, 7, 9, 11, 5, 21, 0, 0, 0, 0};

You can use the sizeof() operator to find the number of elements present in an Array. Below is the syntax for calculating this. 

int num = sizeof(name_of_array)/sizeof(name_of_array[0])

C++ Program to Print One-Dimensional Array

#include<iostream>
using namespace std;

int main(){
    //Initialising 1D Array
    int arr[] = {3, 5, 9, 11, 2, -1, 20};
    //No. of elements present in the array
    int n = sizeof(arr)/sizeof(arr[0]);

    //Printing all array elememts
    for(int i = 0; i < n; i++){
        cout<<arr[i]<<" ";
    }
}

Output:

3 5 9 11 2 -1 20

Multidimensional Arrays in C/C++.

A Multidimensional Array can be defined as an Array of Arrays that store data values of the same type in a tabular form. The size (number of elements it can store) of a multidimensional array can be calculated by multiplying the size of all the dimensions. 

The general form of declaring an N-dimensional Array is as  follows:

syntax: data_type name_of_array[size1][size2]...[sizeN];

For example:

int arr[4][5]     //Two Dimensional Array

size of arr[4][5] = 4x5 = 20 elements we can store in this array

int arr[4][5][6]  //Three Dimensional Array

size of arr[4][5][6] = 4x5x6 = 120 elements we can store in this array

Two-Dimensional Array.

A two-Dimensional Array can be visualized as a matrix (or table) which can be represented with n number of rows and m number of columns. The elements which are going to be present in a 2D Array must be of the same data type. Below is the syntax for the declaration of a 2D Array.

syntax: data_type name_of_array[no. of rows][no. of columns];

Example: int arr[4][3];

How To Initialize a Two-Dimensional Array?

There are multiple ways of initializing a 2D Array and we are going to see two different methods out of all:

Method 1: int arr[4][3] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};

Method 2: int arr[4][3] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}, {10, 11, 12}};

We can access elements stored in a 2D Array by using the row index and column index of that particular element in the matrix.

C++ Program to Print Two-Dimensional Array.

#include<iostream>
using namespace std;

int main(){
    //Initialising 1D Array
    int arr[4][3] = {{3, 15, 9}, {2, 11, -1}, {7, 10, 4},{0, 1, 21}};    

    //Printing all array elements
    for(int i = 0; i < 4; i++){
        for(int j = 0; j < 3; j++){
            cout<< arr[i][j]<<" ";
        }
        cout<<"\n";
    }
}

Output:

3 15 9 
2 11 -1
7 10 4
0 1 21

I hope you have understood the basic and fundamental building blocks of Array Data Structure. If you have any questions regarding this topic please write them in the comment section below. 

(getButton) #text=(Arrays Data Structure in Java) #icon=(link) #color=(#2339bd)

(getButton) #text=(Static Array and Dynamic Arrays) #icon=(link) #color=(#2339bd)

👉Support Us by Sharing our post with others if you really found this useful and also share your valuable feedback in the comment section below so we can work on them and provide you best 😊.(alert-success) 

Program to Find the K-Beauty of a Number.

Given an integer num and K, we have to count the number of K-beauty substrings possible for the given integer num. There are two conditions that need to be satisfied by the substring to become K-beauty.

• The substring must be of length K.
• The integer form of substring is a divisor of given integer num.

 Note: Leading zeros are allowed in the substrings and 0 is not a divisor of any integer value.

Example 1:

Input: num = 360, K = 2
Output: 2

Explanation: Consider the given integer as a string.

"36" is a substring of  "360" and 36 is a divisor of 360.
"60" is a substring of  "360" and 60 is a divisor of 360.

Count of K-beauty possible = 2

Example 2:

Input: num = 540540, K = 3
Output: 3

Explanation: Consider the given integer as a string.

"540" is a substring of  "540540" and 540 is a divisor of 540540.
"405" is a substring of  "540540" and 405 is not a divisor of 540540.
"054" is a substring of  "540540" and 054 is a divisor of 540540.
"540" is a substring of  "540540" and 540 is a divisor of 540540.

Count of K-beauty possible = 3

Approach 1: Fixed-Sized Sliding Window.

This question can be easily solved using the fixed-sized sliding window technique as our window size K is already given in the question.

• Convert the given num integer to a string using the to_string(num) property in C++.
• Initialize the i and j pointers with 0 to calculate the size of our sliding window and one count variable to get the count of K-beauty.
• Run a while loop for our string size and keep on increasing our window size until our window size become equal to K. (j-i+1 == K)
• Extract the string using the substring function and convert that string to an integer n.
• Check whether the converted number n is a divisor of given integer num. If Yes, then increase the count.
• Return the count as an output.

C++ Code for finding the K-beauty of a number:

#include<iostream>
#include <string>
using namespace std;

int KBeautyCount(int num, int K){
    //convert the given num to string
    string str = to_string(num);
    //initialize i and j for window size
    int i = 0, j = 0, count = 0;

    while(j < str.size()){
        if(j-i+1 < K){
            //increment the j to get window size
            j++;
        }
        else if(j-i+1 == K){
            //get the substring and convert it to integer
            string s = str.substr(i, K);
            int n = stoi(s);
            //check if n is divisor of num 
            if(n != 0 && num % n == 0){
                count++;
            }
            i++;
            j++;
        }
    }
    return count;
}
int main(){
    int num = 540540;
    int K = 3;
    cout<<KBeautyCount(num, K);
}

Output:

3

• Time Complexity: O(n)
• Space Complexity: O(1)

Approach 2: Using a single for loop and substring property.

In this very easy and brute force approach, we just need to run a for loop and extra the substring of size K and then convert that substring into an integer and check whether the given condition is satisfied by that integer or not. Similarly, check the condition for all possible substrings of size K.

C++ Code for finding the K-beauty of a number:

#include<iostream>
#include <string>
using namespace std;

int KBeautyCount(int num, int K){
    //convert the given num to string
    string str = to_string(num);
    //Size of String
    int n = str.size();
    int count = 0;

    for(int i = 0; i < n-K+1; i++){
        //extract the substring of size K
        string s = str.substr(i,K);
        //convert the string to integer
        int snum = stoi(s);
        if(snum != 0 && num % snum == 0){
            count++;
        }
    }
    return count;
}
int main(){
    int num = 540540;
    int K = 3;
    cout<<KBeautyCount(num, K);
}

Output:

3

• Time Complexity: O(n)
• Space Complexity: O(1)

👉Support Us by Sharing our post with others if you really found this useful and also share your valuable feedback in the comment section below so we can work on them and provide you best 😊.(alert-success) 

Introduction to Data Structure

Before we start understanding what is the use of Data Structure and why it is necessary to learn this topic we first need to know the term Data. 

What is Data?

If we go with the basic dictionary definition, the quantities, characters, or symbols on which operations are performed by a computer, may be stored and transmitted in the form of electrical signals and recorded on magnetic, optical, or mechanical recording media.

Now often people get confused between two terms that are Data and Information and people think that both words have similar meanings but it is not correct for this we need to understand when Data become Information. 

Data is an unordered and unrefined collection of facts and if the data is arranged in a systematic way then it gets a structure and becomes meaningful. This meaningful or processed data is called Information.

Before learning about different types of data structures let us first understand the basic difference between Data Type and Abstract Data Type.

What is Data Type?

In programming, a data type is used to define a certain type of value a variable can store and what kind of mathematical, relational, or logical operations are allowed on those values. Let's understand this with two different examples.

For example, the int data type can take only integer values, and all kinds of operations like addition, subtraction, multiplication, bitwise operations, etc are allowed. (alert-passed)

For example, the float data type can take only floating point values and bitwise and % (modulo operations) are not allowed. (alert-passed)

The data types like boolean, byte, short, int, long, float, double, and char are known as primitive data types, and apart from this, there is a concept of user-defined data type in which operations and values of the user-defined data type are not specified by the programming language but user have to specify by themselves. Example of user-defined data type is Structure, union, and enumeration.

What is Abstract Data Type (ADT)?

ADTs are like user-defined data types which define operations on values using functions without specifying what is there inside the function and how the operations are performed. ADT hides the inner structure and design of the data type from the user.

Example: Stack ADT

A stack consists of elements of the same type arranged in sequential order and it can be implemented using arrays or linked lists.

The list of operations that we can perform on the stack are:

• initialize() - Initializing it to be empty.
• push() - Insert an element into the stack.
• pop() - Delete an element from the stack.
• isEmpty() - Checks if stack is empty.
• isFull() - Checks if stack is full.

Note: Stack itself is a data structure that is implemented using other data structures like arrays or linked lists. (alert-success) 

What is Data Structure?

A data structure (DS) is a way of organizing data so that it can be used effectively. It is a way of organizing data in some fashion so that later on it can be accessed reread or updated the data quickly and easily. 

From the above explanation of ADT, we can say that data structure is used to implement an ADT.

In reality, different implementations of ADT are compared for time and space efficiency. The one best suited according to the current requirement of the user will be selected. (alert-passed)

Advantages of Data Structure:

• Efficiency: Proper choice of data structures make the program efficient in terms of space and time.
• Reusability: One implementation can be used by multiple client programs.
• Abstraction: Data structure is specified by an ADT which provides a level of abstraction. The client program doesn't have to worry about the implementation details.  

Why do we need Data Structure?

A Data Structure is a systematic way to organize data so that it can be used efficiently in terms of time and space com. We need Data Structure to provide an appropriate way to structure the data in such a way that it can produce some meaningful information that we can use in a more efficient way.

There are multiple different kinds of Data Structures available to store and manage our data but here we are going to take the example of one of the very popular data structures named Arrays. An array is a linear data structure that can store the elements of the same data type in a contiguous manner so instead of creating multiple variables of the same type we can create an array to store all the values. Like Array, we also use the String data structure to store the sequence of characters. 

Real Life Example of some popular Data Structure.

• Stack Data Structure is used in implementing redoing and undoing features in any application.
• Graph Data Structure stores friendship information on a social networking site.

Type of Data Structure.

There are basically two types of data structure, one a linear data structure and the other a non-linear data structure.

When all the elements are arranged in a linear (sequential) order then that data structure is known as a Linear data structure. Examples, are Arrays, Stack, Queue, and Linked List.

When all the elements are not arranged in a linear (sequential) order then that data structure is known as a non-linear data structure. Examples are trees and Graphs.

Static and Dynamic Data structure.

Static data structure: Memory allocation is done at compile time in a static data structure. The maximum size of the static data structure is fixed and it cannot be changed at run time. It provides faster access to elements but insertion and deletion are quite expensive. Example: Array

Dynamic Data structure: Memory is allocated at run time in a dynamic data structure. The size of the dynamic data structure is not fixed, they are flexible in size. It allows faster insertion and deletion but access to elements is quite expensive. Example: Linked List

👉Support Us by Sharing our post with others if you really found this useful and also share your valuable feedback in the comment section below so we can work on them and provide you best 😊.(alert-success) 

ASCII Table Chart

ASCII stands for Americal Standard Code for Information Interchange designed in 1963 as a standard character set for computers and electronic devices. It is a 7-bit character set that contains a total of 128 characters which includes numbers from 0-9, the upper case and lower case English alphabets A to Z, and many unique characters. 

This is a list of  ASCII (Americal Standard Code for Information Interchange) character codes with Hexa decimal, Octa decimal, and Binary Conversion. 

ASCII Table