Sinking sort - Better than quick sort (in some cases)

BUBBLE SORT :             

                       

                  Bubble sort is a simple sorting algorithm also called Sinking sort which just goes through a set of data ( list of numbers or characters) and compares each member with its right neighbour . The pass through the list is repeated until no more swaps are needed , which indicates that the list is sorted . Although the algorithm is simple , It is too slow and impractical for a large set of data.

Read More

'using namespace std ' - what does it mean ?

                Suppose In u r class, if there are two persons with same name vinod, and if u want to call one person, how will u call him ?? Whenever we need to differentiate them (in case of more members ) definitely we would have to use some additional information along with their name, like surname or the area (if they live in different area) or their mother or father name, etc.

 

                          Same situation arises here. Suppose in u r code , If u had declare the function with name say abc(), and there is some other library available with the same function name and if u include that library in u r code , Then the compiler has no way of thinking which xyz() function u r referring in the code. In order to overcome this difficulty Namespace is introduced.

Namespace:

                    Namespace is a container for a set of identifiers (names of variables, functions , classes) . It puts the names of its members in a distinct space so that they don't conflict with the names in other namespaces or global namespace.

For example :

1.

namespace myname { int a, b; }

                   
                  In this case, the variables a and b are normal variables declared within a namespace called myname.
                  These variables can be accessed from within their namespace normally, with their identifier (either a or b), but if accessed from outside the myname namespace they have to be properly qualified with the scope operator ::. For example, to access the previous variables from outside myname namespace they should be qualified like this:

myname::a myname::b

Example 2.

output :

Inside first_space 

Inside second_space

The concept can be depicted using the following diagram:

                       Generally most of them will use the standard namespace with the following declaration :

 

                  using namespace std;

• We can access functions and variables with the scope operator in the same way.
  

• Namespaces can be split :
  • Two segments of a code can be declared in the same namespace i.e. We can have more than one namespace of the same name. This gives the advantage of defining the same namespace in more than one file (although they can be created in the same file as well).
    
    
    

                     It tells that in the same namespace two variables are declared seperately. Ofcouse u might think why declaring seperately in same file, this will help a lot while declaring the same namespace in different files.

• We can have anonymous namespaces (namespace with no name). They are directly usable in the same program and are used for declaring unique identifiers.

Take a look with an example :

             Here , as there is no name for namespace , we won't be using the scope operator

It also avoids making global static variable. 

Take a look with an example :

• Namespace aliasing :

                It is also possible to declare an alternate name for an existing namespace.

We can use the following format:

  
             namespace new_name = current_name;

For example:

Output:

           1

           1

 

• C++ has a default namespace named std, which contains all the default library of the C++

 

USING A NAMESPACE

                   There are 3 ways to use a namespace in program.

•     Scope resolution
•     with “ Using” directive
•     with “ Using” declaration

1. SCOPE RESOLUTION :

 

                 From the name itself u have got some idea ..

                             Any name (identifier) declared in a namespace can be explicitly specified using the namespace's name and the scope resolution :: operator with the identifier.

Take a look with an example :

2.WITH “USING” DECLARATION :

 

                   The keyword using introduces a name into the current declarative region (such as a block) .With this using declaration we can import a specific name in that block .

 

Take a look with an example :

                        #include <iostream>

using namespace std;

namespace first

{

    int x = 5;

    int y = 10;

}

namespace second

{

    double x = 3.1416;

    double y = 2.7183;

}

int main ()

{

    using first::x; // using declaration

    using second::y; // using declaration

    cout << x << '\n';

    cout << y << '\n';

    cout << first::y << '\n';

    cout << second::x << '\n';

    return 0;

}

• Suppose if u put using declaration in a block, then it will be visible only in that block.
• U can access the namespace from other files also.

Try yourself this one and check the output.

int main ()

{

      {

          using first::x;

           using second::y;

      }

       cout << x << '\n';

      cout << y << '\n';

      return 0;

}

3.WITH USING DIRECTIVE :

                         With using keyword u can import only one variable at a time.But with using derivative , allows you to import an entire namespace into the program with global scope . It can be used to import a namespace into another namespace or any program.

      #include <iostream>

using namespace std;

namespace first

{

          int x = 5;

          int y = 10;

}

namespace second

{

        double x = 3.1416;

        double y = 2.7183;

}

int main ()

{

        using namespace first; // using directive

        cout << x << '\n';

        cout << y << '\n';

        cout << second::x << '\n';

        cout << second::y << '\n';

        return 0;

}

           

              using and using namespace have validity only in the same block in which they are stated or in the entire source code file if they are used directly in the global scope. For example, it would be possible to first use the objects of one namespace and then those of another one by splitting the code in different blocks.

   Name imported with using declaration can override the name imported with using derivative

Nested Namespaces :

            Namespaces can be nested where you can define one namespace inside another name space as follows:

namespace name1

{ 

  namespace name2

 {

             fun();

   }

}

One can access members of nested namespace by using scope operators as follows:

using namespace name1::name2;  // to access members of name2

using namespace name1;   // to access members of name1

Take a look with an example :



The result of this program should be  ???

Read More

Global and Local variables

Name Visibility :

                    Named entities, such as variables, functions, and compound types need to be declared before being used in programs. The point in the program where this declaration happens influences its visibility.

               An entity declared outside any block has global scope called “Global variables” , meaning that its name is valid anywhere in the code. While an entity declared within a block, in a function or as a function parameters has block scope, and is only visible within the specific block in which it is declared, but not outside it. Variables with block scope are known as “Local variables”.

For example :

• we can also call a variable as Local variable ,If we can also declare it in the block or constructor.
  
  
  

                 
                    Here b can be accessed inside the block also but c  can’t be accessed in function d.

• If the global variable value is changed anywhere in the program (i.e. with out declaring it ) ,it's value will be changed.

              Without compiling it directly in the compiler,once u check the output by u r self. Then u will get the clear idea how the values of variables will change.

• Suppose if u want two values for the same variable in the same function, then a new concept namespace is to be used.
  

Here is a set of programs for u for practice.

1.
 

 2.



3.





4.

5.





The answers for this programs are available in the below link :

 CLICK HERE

Read More

General structure of a c++ program

General structure of a c++ program :

#include <iostream>

using namespace std;

int main() {

cout << "This is a simple C++ program!" << endl;

}

1. #include <iostream>
     

                       This line is a preprocessing directive. All preprocessing directives within C ++ source code begin with a # symbol. This one directs the preprocessor to add some predefined source code to our existing source code before the compiler begins to process it. This process is done automatically.

IOSTREAM :

               IOSTREAM library, a collection of precompiled C ++ code that C ++ programs (like ours) can use. The iostream library contains routines that handle input and output (I/O) that include functions such as printing to the display, getting user input from the keyboard. These items, along with many other things related to input and output, were developed in C ++ , compiled and stored in the iostream library.

               

             The #include directive specifies a file, called a header that contains the specifications for the library code. The compiler checks how we use cout and endl within our code against the specifications in the <iostream> header to ensure that we are using the library code correctly.

2. Using namespace std ;
        

                  This using namespace directive will allow us to omit , from writing the longer name std::cout and std::endl instead we can write directly as cout and endl.It's not mandatory to use this statement in every program.It makes simple and easy to use the shorter names(cout,endl..etc).

            std::cout << "This is a simple C++ program!" << std::endl;

3. int main() {
           

              This specifies the real beginning of our program. Here we are declaring a function named main. All C ++ programs must contain this function to be executable.

            Most of them are thinking why we have to use int as return for main function..? Here is answer for u r doubt.

           The return value from the main function is used by the run time library as the exit code for the process. Both Unix and Windows support a concept of a integer returned from a process after it has finished. 

           The body of the main function does not need to contain the return statement , if control reaches the end of main without encountering a return statement , the effect is that of executing the return 0 ; Execution of the return ( or the implicit return upon reaching the end of main) is equivalent to first leaving the function normally (which destroys the objects with automatic storage duration) and then calling std::exit with the same argument as the argument of the return ( std::exit then destroys static objects and terminates the program). 

 

            The opening curly brace represents the begining of the body of the function.

4. cout << "This is a simple C++ program!"<< endl;

           

            The body of our main function contains only one statement. This statement directs the executing program to print the message “This is a simple C++ program!” on the screen. A statement is the fundamental unit of execution in a C ++ program.All statements in C ++ end with a semicolon ;

5. }

             The closing curly brace marks the end of the body of a function. Both the open curly brace and close curly brace are required for every function definition.

Read More

Selection Sort -- an inplace sort

Selection Sort:

               Sort...from the word itself , It tells that arranging the elements in some order. Selection...taking some integer or any element that we will be taken as our wish. Totally we can say that picking up one integer and doing sorting by that number(for that iteration).

Working:

 

            Let us take an array of integers. 

                 

                  Lets select the first integer i.e. 1^st element of array (A[0] ) and compare it with the rest of the elements.If it is greater swap those two elements.Likewise for 2^nd iteration select the next element of array (A[1]) with the next succeding elements of the array.Similiarly we have to perform it ,for 3^rd ,4^th ....up to the last element.Any way for the last element there will be no successor to compare it with d next one .

                  For the first iteration the first element is selected. Here the first element is 19. It is compared with the rest of the elements in the array.

For 1^st iteration:

                        After this we will get the smallest element at the index 0. i.e. 6

           

                        Now we will take the second integer A[1]=19

For 2^nd iteration :

  

For 3^rd iteration:

For 4^rd iteration:

For 5^rd iteration:

                      
                 If the array has N elements ,Selection sort requires N-1 iterations.

Algorithm :

       Selection(int a[],int n)

·                                                           for i=0:n-2                            // A[] is length of 0 to n-1

◦                                                                for j=i+1 : n-1

▪                                                                        if A[i] >A[j]

·                                                           Swap(A[i], A[j])

·                   end

Analysis :

           

• By analysing the run time ,one might conclude that this sort should never be used in u programs as it takes more time for a larger numbers (for greater than 1000 numbers ).

                               O(n^2) comparisions

• The running time is also a quadratic equation in all cases.

                Best case : O(n^2)

               Average case : O(n^2)

               Wrost case : O(n^2)

• It is specifically an In-place comparison sort. It takes O(1) extra space (for swaping one extra interger is used)
  
  
• The difference between the Bubble sort and Selection sort is that Bubble sort selects the maximum element from the unsorted array and selection sort gets the minimum element from the array.
  
  
• However, Selection Sort has the property of minimizing the number of swaps. In applications where the cost of swapping items is high, Selection Sort very well may be the algorithm of choice.

                                    O(n) swaps

Code :
                TO DOWNLOAD THE CODE 

           

                                 CLICK HERE

           

                       

                       

Read More