Selection sort in C++

One family of internal sorting algorithms is selection sort. The basic idea of selection sort is to repeatedly select the smallest key in the remaining unsorted array. Simply put, an element is taken as the smallest key element
and then it is compared with the other elements to sort the array.  It is implemented in the form of exchange selection sort that requires a single array to work with. In this technique, computer keeps on finding the next smallest element and brings it at its appropriate positions.
Selection sort can be used to sort an array in both ascending as well as descending order. The following program demonstrates
the implementation of selection sort in ascending order :

// Program to implement selection sort in C++ ( ascending order )

#include <iostream>

void selectionSort(int AR[],int size)
{
     int i,j,temp;
     for (i=0; i<size; i++)
     {
          for (j=i+1; j<=size; j++)
          {
               if ( AR[i] > AR[j] ) // sorts in ascending order
               {
                    temp = AR[j];
                    AR[j] = AR[i];
                    AR[i] = temp;
               }
          } // end of sub loop
     } // end of main loop

} // end of function selectionSort

int main()
{
     int arr[20],size;
     // prompts the user to enter the elements in the array
     std::cout<<" Enter the no. of elements that you want to enter (max 20 ) : ";
     std::cin>>size;
     std::cout<<" Now enter the elements in the array ";
     for (int i=0; i<size; i++)
     {
          std::cout<<" \n Element "<<i<<" : ";
          std::cin>>arr[i];
     }
     selectionSort(arr,size); // calls the function to sort the array
     std::cout<<" \n The sorted array is as follows ";
     for (int i=0; i<size; i++)
     {
          std::cout<<" \n Element "<<i<<" : "<<arr[i];
     }
     return 0;
} // end of main



------ OUTPUT ------

Please do comment if you don't understand any part or want to know more or just want to say thanks. I love programming and love to teach my friends. Your suggestions and appreciation will make this blog much better.

------ Related Posts ------
Bubble Sort in C++ : http://programsplusplus.blogspot.in/2012/02/bubble-sort-in-c.html
Insertion Sort in C++ : http://programsplusplus.blogspot.in/2012/02/insertion-sort-in-c.html

Insertion sort in C++

Insertion sort is another sorting technique used when sorting arrays. Unlike bubble sort, it uses much less number of passes to sort an array. As the name suggests, sorting is done by inserting elements in their proper order by comparing an element with the elements on either side. Hers is how it works. Suppose we want to sort an array A with elements A[1],A[2]....A[N]. Then,
Step 1 : A[1] by itself is trivially sorted.
Step 2 : A[2] is inserted either before or after A[1] so that A[1],A[2] are sorted.
Step 3 : A[3] is inserted into proper place in A[1],A[2],that is, before A[1], between A[1]
and A[2, or after A[2], so that A[1],A[2],A[3] is sorted.
The process keeps repeating until the array is fully sorted.

The following program demonstrates the use of insertion sort by sorting an array of integers in ascending order

// Program to implement insertion sort ( ascending order )
#include <iostream>

void Insertion_sort(int AR[],int n)
{
     int temp,j;
     AR[0] = INT_MIN;
     for (int i=1; i<=n; i++)
     {
          temp = AR[i];
          j = i-1;
          while ( temp < AR[j])
          {
               AR[j+1] = AR[j];
               j--;
          }
          AR[j+1] = temp;
     } // end of for loop
} // end of insertion sort function

int main()
{
     int arr[20];
     int size;
     std::cout<<" Enter the maximum no. of elements you want (max 20) : ";
     std::cin>>size;
     std::cout<<"\n Now enter the elements in the array \n ";
     // loop to prompt the user to enter the elements in the array
     // notice that the elements are inserted fromt he 1st index rather that 0, as 0 index will be assigned 
     // INT_MIN value from which other elements will be compared
     for (int i=1; i<=size; i++)
     {
          std::cout<<"Element "<<i<<" : ";
          std::cin>>arr[i];
     }
     Insertion_sort(arr,size);
     // as arrays are passed with reference, hence any changes will be reflected in the original array as well
     std::cout<<" \n The sorted array is as follows \n ";
     for (int i=1; i<=size; i++)
     {
          std::cout<<" \n Element "<<i<<" : "<<arr[i];
     }
     return 0;
} // end of main
------ OUTPUT ------

------Programming Advice and Tips------

1 - Even though insertion sort uses considerably less number of passes to sort an array, it still is not useful

when sorting arrays that contain large number of elements. Hence it is best advised to use insertion sort

where the no of elements to be sorted are less(i.e having small value of N).

2 - Notice that all the loops start from index location 1 rather than starting from 0 (which is usually done). This is done because, at the 0th index location, INT_MIN value is stored from which other elements are compared and is vital in terminating the while loop.

3 - INT_MIN is the MINIMUM value that an integer can have. It is usually a negative value, and varies from platform to platform.

Please do comment if you don't understand any part or want to know more or just want to say thanks. I love programming and love to teach my friends. Your suggestions and appreciation will make this blog much better.


------ Related Posts ------

Bubble Sort in C++ : http://programsplusplus.blogspot.in/2012/02/bubble-sort-in-c.html
Selection Sort in C++ : http://programsplusplus.blogspot.in/2012/02/selection-sort-in-c.html

Converting an array of string to uppercase

Here is a program to convert an array of string into uppercase. Just like a recent post : "lowercase to uppercase" the following program also uses the standard C++ functions such as toupper() to convert string from lowercase to uppercase.

Now, the process is the same as converting a single string, traversing the entire string  using a loop and converting each
character from lowercase to uppercase(or vice-verse) using toupper() (or tolower() ) and storing the converted characters
into another string.

The only difference that comes in an array of strings is that a loop has to be used to process individual strings sorted in the
array.Consider the string as columns of students in a classroom with each of the student sitting in the front desk as the
starting index of that column.

NOTE : be sure to add a terminating null character ('\0') at the end of each converted string, as this is not done by default by the
toupper() function !!!! :O

Here is an sample program.

// Program to convert an array of string to uppercase

#include <iostream>
#include <cctype>

int main()
{
     char name[5][20];
     char temp[5][20];
     int size;
     // prompts the user to enter the no. of string he/she wants in the array
     std::cout<<" Enter the no. of names you want to insert (max 5 ) : ";
     std::cin>>size;
     std::cin.ignore(); // to clear the memory buffer
     std::cout<<" \n Now enter the names (max 20 characters long ) : \n ";
     for (int i=0; i<size; i++)
     {
          std::cout<<" Name "<<i<<" : ";
          std::cin.getline(name[i],sizeof(name[i]));
     }
     // to convert them into uppercase
     int j=0;

     for (int i=0; i<size; i++) // main loop to traverse the rows
     {
          for (j=0; name[i][j] != '\0'; j++) // sub loop to traverse the individual strings
          {
               temp[i][j] = toupper(name[i][j]); // converts each character to uppercase
          }
          temp[i][j] = '\0'; // adds a terminating null character at the end of each string

     }
     // to show the names in uppercase

     for (int i=0; i<size; i++)
     {
          std::cout<<"\n NAME "<<i<<" : "<<temp[i];
     }
     return 0;
} // end of main

------ OUTPUT ------

Please do comment if you don't understand any part or want to know more or just want to say thanks. I love programming and love to teach my friends. Your suggestions and appreciation will make this blog much better.


------ Related Posts ------ 
Lowercase to Uppercsae : http://programsplusplus.blogspot.in/2012/01/lowercase-to-uppercase.html

Uppercase to Lowercase : http://programsplusplus.blogspot.in/2012/01/uppercase-to-lowercase.html

Bubble sort in C++

Sorting is used in many programming applications and as there are various sorting algorithms, each
having their respective pros and cons. Bubble sort, is one such search algorithm that is very easy to implement.
Bubble sort can be used to sort both in ascending order as well as in descending order. The basic idea of bubble sort
is to compare two adjoining value and exchange them if they are not in proper order. In every pass, the heaviest element
settles as its appropriate position in the bottom(if is to be sorted in ascending order) and the opposite is true for
sorting in descending order. Bubble sort is useful when a small no. of element are to be sorted as it is a simple algorithm.
However, due to comparatively large no of passes(loop counts), as compared to other sorting algorithms, its is advisable
to use other searching algorithms , e.g quick sort.
A program is given below that sorts an integer array in ascending order using bubble sort algorithm

// Program to implement bubble sort in C++\
#include <iostream>

int main()
{
     int arr[20];
     int size, temp,i,j;
     std::cout<<" Enter the no. of elements you want in the array (max 20 ) : ";
     std::cin>>size;
     std::cout<<" \n Now enter the elements in the array ";
     // loop to insert elements in the array, which is initially empty
     for (i=0; i<size; i++)
     {
          std::cout<<" \n Element "<<i<<" : ";
          std::cin>>arr[i];
     } // end of for loop

     // to sort using bubble sort algorithm(ascending order)

     for (i=0; i<size; i++)
     {
          for (j=0; j<=i; j++)
          {
               if( arr[j] > arr[i]) // exchanges heavy elements with lighter ones
               {
                    temp = arr[j];
                    arr[j] = arr[i];
                    arr[i] = temp;
               }

          } // end of sub loop
     } // end of main loop

     std::cout<<" \n The sorted array is as follows : \n";
     for (i=0; i<size; i++)
     {
          std::cout<<" \n Element "<<i<<" : "<<arr[i];
     } // end of main loop
     return 0;
} // end of main

------ OUTPUT ------

Please do comment if you don't understand any part or want to know more or just want to say thanks. I love programming and love to teach my friends. Your suggestions and appreciation will make this blog much better.

------ Related Posts ------

Insertion Sort in C++ : http://programsplusplus.blogspot.in/2012/02/insertion-sort-in-c.html
Selection Sort in C++ : http://programsplusplus.blogspot.in/2012/02/selection-sort-in-c.html
 

Basic password encryption program

Password encryption is basically converting a password in some other format(instead of text) into a format
that is not recognizable,so that i becomes secure. This is essential when we want to write down passwords without
the fear of having to risk the likelihood of revealing our password. Also since encrypted passwords contain special characters
such as %,$ , it becomes very difficult for brute force attacks to crack it. There are many password encrypters  available, that use
sophisticated techniques to encrypt passwords. One simple method is by converting a series of characters into their respective ASCII
values. The program given below encrypts the password as follows :

Step1 : The user enters a password to encrypt
Step2 : The password is checked to see whether it is UPPERCASE OR LOWERCASE
Step3 : If it is lowercase then it is converted into uppercase and vice-verse
Step4 : Then the converted string is converted into ASCII. Vola, the password is encrypted and contains only numeric values

Even though this encryption method is very simple, it is effective especially against a person who little knowledge of ASCII values.

// BASIC PASSWORD ENCRYPTER
// USES ASCII CODES FOR ENCRYPTION
// VERSION 1.0
// CREATED BY : DEEPAK SHARMA

#include <iostream>
#include <cctype>

int main()
{
     char password[20];
     char temp[20];
     int encrypt_password[20];
     int i,length;
     std::cout<<" Enter the password to encrypt (max 20 characters ) : ";
     std::cin.getline(password,sizeof(password));
      // to check whether the password is in UPPERCASE or LOWERCASE
     for (i=0; password[i] != '\0'; i++ )
     {
           if ( islower(password[i]) )
                    temp[i] = toupper(password[i]);
           else if ( isupper(password[i]) )
                    temp[i] = tolower(password[i]);
          else
                    temp[i] = password[i];
      } //end of loop
             temp[i] = '\0';

     // to convert the characters to their respective ASCII values
      for ( i=0; temp[i] != '\0'; i++ )
      {
               encrypt_password[i] = temp[i];
      }
        length = i;
      // to display the encrypted password

      std::cout<<"\n ENTERED PASSWORD : "<<password;

      std::cout<<" \n\n ENCRYPTED PASSWORD : ";
      for (i=0; i<length; i++)
      {
          std::cout<<encrypt_password[i];
      }

     return 0;
} // end of main

Basic password encrypter version 1.0

---

Multiple increment opeartors in C and use of printf

This post is in reference to a problem about which I posted earlier, under the title "multiple increment operators". Now while using multiple increment operators in C , the results are completely different, which also encouraged me to explain a little bit about the printf(); used in C for basic output operations.
Consider the following snippet of code :-
// Multiple increment opearators in C

#include <cstdio>
int main()
{
     int x = 5;
     printf("%d%d%d%d%d",x++,x--,++x,--x,x);
     return 0;
}
The program give the output as 45545.
Now when the statement printf("%d%d%d%d%d",x++,x--,++x,--x,x); is executed, all the variables are processed from right to left , and pushed accordingly in the stack. i.e
x - PUSH --> means x = 5;
--x (per-decrement) - PUSH --> means x = 4;
++x (per-increment) - PUSH --> means x = 5;

x-- (post-decrement) - PUSH --> means x = 5 (but afterwards x = 4 due to post decrement)
x++(post-increment) - PUSH --> means x = 4; (but afterwards x = 5 due to post increment).

Now the printf() statement , prints the values of x , hence the output is 45545(remember stacks follow LIFO,last in first out).
------ OUTPUT ------
 

For more info on using printf(), follow this link : http://stackoverflow.com/questions/2198880/how-does-printf-work

------ Related Posts ------ 
Multiple increment operators in c++ : http://programsplusplus.blogspot.in/2012/01/multiple-increment-operators-in-sinlge.html

Deletion in an integer array

Deletion inside data structures is very common, especially inside arrays as they have static(fixed) memory allocation. To delete an element from the array simply move each element one step above. For example, if the array was initially as follows :

Element 0 : 23
Element 1 : 98
Element 2 : 87
Element 3 : 12
and suppose we want to delete an element at the 1st position(i.e.98), then we simply shift each element one position above. So, the new array after deleting value 98 from the 1st position would be as follows :
Element 0 : 23
Element 1 : 87
Element 2 : 12
Hence we have successfully deleted an element from the array. The process is contrary to the method that we have used to perform insertion operation in the array(see the previous post). Read the given code below, for a better understanding :

// Program to delete element in an array (for GCC compiler package and similar compilers)

#include <iostream>
// function to delete an element from the array
int deletion_array(int array[],int s,int pos)
{
     for (int i=pos; i<=s; i++)
     {
          array[i] = array[i+1];  //shifts each element one position above
     }
     s--;    // decrements the size, as one element is deleted
     return s;  // returns the new size of the new array
}

int main()
{
     int size,value,position;
     int arr[21];
      // prompts the used to enter the maximum no. of elements in the array
     std::cout<<" Enter the no of elements you want in the array (max 20) : ";
     std::cin>>size;
      // to insert the elements in the array
     for (int i=0; i<size; i++)
     {
          std::cout<<" \n Element "<<i<<" : ";
          std::cin>>arr[i];
     }
     std::cout<<"\n Enter the position where you want to delete the value : ";
     std::cin>>position;
     size = deletion_array(arr,size,position);
      // calls the function to delete the specified element
     std::cout<<" \n Deletion successfull !!! , the new array is as follows ";

     // displays the new array
     for (int i=0; i<size; i++)
     {
          std::cout<<"\n Element "<<i<<" : "<<arr[i];
     }
     return 0;
} // end of main
Note : If the console window shuts down immedeaitly, then add std::cin.get(); before return 0; to fix the problem. :) 

------ OUTPUT ------

------ Related Posts ------
Insertion in array : http://programsplusplus.blogspot.in/2012/02/insertion-in-integer-array.html

Insertion in an integer array

Insertion in an array is a widely used practice used when programming with C/C++. Simply , it involves inserting a value from a user and inserting in an array. Now, how this is done is interesting and simple :-). First we create the array (simple!!! ), then we prompt the user to enter the position where he/she wants to insert and finally, the user is prompted to enter the value to insert in the array. Consider an example, 

Suppose the array initially contains the following values, along with their positions :-

Element 0 : 3
Element 1 : 7
Element 2 : 89

Element 3 : 8

Then inserting any value(say 145) at position '1', then the new array would be like this :-

Element 0 : 3

Element 1 : 145

Element 2 : 7

Element 3 : 89
Element 4 : 8
Who la, the value 145 has been inserted at the 1st position in the array.

Note : Notice, that the size of the array has increased(obviyo!!!) , so always take the size of the array one greater than the no of elements you want to have. This will prevent overwrite problems in the array.
Consider the following snippet of code for a better understanding.

// Program to insert element in an array (for GCC compliler package and similar compilers)

#include <iostream>
// function to insert elements in the array
int insertion_array(int array[],int s,int pos,int val)
{
     for (int i=s; i>=pos; i--) // shifts every element one step below
     {
          array[i+1] = array[i];
     }
     array[pos] = val; // inserts the given value at the specified position
     s++;                  // increments the size, as one extra element is now inserted
     return s;
}

int main()
{
     int size,value,position;
     int arr[21];
     std::cout<<" Enter the no of elements you want in the array (max 20) : ";
     std::cin>>size;

     // prompts the user to enter elements in the array
     for (int i=0; i<size; i++)
     {
          std::cout<<" \n Element "<<i<<" : ";
          std::cin>>arr[i];
     }
     std::cout<<"\n Enter the position where you want to insert the value : ";
     std::cin>>position;
     std::cout<<"\n Enter the value to insert at the "<<position<<" : ";
     std::cin>>value;
     // calls the above function to insert values in the array
     size = insertion_array(arr,size,position,value);
     std::cout<<" \Insertion successfull !!! , the new array is as follows ";
      // displays the new array
     for (int i=0; i<size; i++)
     {
          std::cout<<"\n Element "<<i<<" : "<<arr[i];
     }
     return 0;
} // end of main
------ OUTPUT ------

Note : If the console window shuts down immedeaitly, then add std::cin.get(); before return 0; to fix the problem. :)
------ Related Posts ------

Deletion in an array : http://programsplusplus.blogspot.in/2012/02/deletion-in-integer-array.html

Binary Search in array

Binary search is also a widely used searching technique used to find elements in an array. As the name suggests, binary search involves splitting the entire array into two pieces again and again until we find that we have searched for.Note: the array needs to be sorted first in order for this method to work.  In binary search, the starting, ending and middle positions are found out first. Then , the array is broken down into smaller and smaller pieces of two and the middle position is found out. The advantage of binary search is that it requires less no of passes through the array, making it a simple and efficient searching technique in an array compared to other searching techniques such as linear search.

 Consider the following code snippet :
// Program to search using binary search
#include <iostream.>

int main()
{
    int arr[20],position,value;
    int size,flag = 0;
    int beg,mid,end;
    mid = 0;
    // prompts the user to enter the maximum no of elements in the array
    std::cout<<" Enter the max no of elements you want in the array (max 20) : ";
    std::cin>>size;
    for (int i=0; i<size; i++)
    {
        std::cout<<"\n Element : "<<i<<" : ";
        std::cin>>arr[i];
    }
    std::cout<<"\n Enter the value that you want to search : ";
    std::cin>>value; // takes the value that is to be searched
    std::cin.ignore();
    beg = 0;
    end = size-1;
    mid = (beg+end)/2; // finds the middle index

    while ( beg <= end )
    {
          if ( arr[mid] == value ) // breaks loop if the element is found
          {
             position = mid;
             flag = 1;
             break;
             }
            
          else if ( arr[mid] > value )
               end = mid -1;
          else
              beg = mid + 1;
                     
        mid = (beg+end)/2; // finds the middle index at each pass
    } // end of while
   
     if ( flag == 1 ) // displays the found element
        std::cout<<"\n Value "<<value<<" found at position "<<position;
                         // displays an error if the element is not found
     else
         std::cout<<" \nVALUE NOT FOUND !!! ";
   
    std::cin.get();
    return 0;
} // end of main

Binary Search in array

Note : The array must be sorted beforehand for this technique to work.

------ Related Posts ------ 

Linear Search : http://programsplusplus.blogspot.in/2012/02/linear-search-in-array.html

 

Linear Search in array

Linear search is one of the most basic techniques used while programming in C, C++ or any other programming language for that matter. It is also taught in school and college and is one of the fundamental techniques used to search in an array. Linear search is implemented by searching each element in the array with the value that is to be searched.

In this method, the user is prompted to insert the value which has to be searched and the position where the element is stored is given as output. In simple words, the user enters the value which has to be searched, the program searches the array to find that value and if the value is found then the position where the element is found is displayed.

Consider the following code snippet :

// Program to implement linear search (by value)
#include <iostream>

int main()
{
    int arr[20],n;
    int position,value,flag = 0;
    // prompts the user to enter the no of elements in the array
    std::cout<<" Enter the no of elements you want to insert (max 20) ? ";
    std::cin>>n;
    for (int i=0; i<n; i++) // loop to enter the elements in the array
    {
        std::cout<<" \n Element "<<i<<" : ";
        std::cin>>arr[i];
    }
    // asks the user to enter the value that is to be searched
    std::cout<<"\n Enter the value to find in the array : ";
    std::cin>>value;
    std::cin.ignore();
    // searches the position by checking each value in the array
    for(int i=0; i<n; i++)
    {
            if ( arr[i] == value )
            {
                 position = i;
                 flag = 1;
                 break; //breaks the loop if value is found
            }
            else
                flag = -1; // assigns -1 to flag variable if value is not found
    }
   
    if ( flag == -1 ) // displays error message if value is not found
       std::cout<<" \n Element NOT FOUND !!! ";
    else             // displays the searched value along with its position
       std::cout<<" Value "<<value<<" found at postiton : "<<position;
   
    std::cin.get();
    return 0;
} // end of main

 

Linear search using value to find position

NOTE : Since linear search involves processing the entire array, it takes considerable time and resources if the size of the array is quite large. Hence, more efficient searching techniques are used such as binary search etc.

------ Related Posts ------ 

Binary Search : http://programsplusplus.blogspot.in/2012/02/binary-search-in-array.html