Algorithm (C++)

Algorithm (C++) is a step-by-step procedure, which defines a set of instructions to be executed in a certain order to get the desired output. Algorithms are generally created independent of underlying languages, i.e. an algorithm can be implemented in more than one programming language.

From the data structure point of view, following are some important categories of algorithms −

• Search − Algorithm to search an item in a data structure.
• Sort − Algorithm to sort items in a certain order.
• Insert − Algorithm to insert item in a data structure.
• Update − Algorithm to update an existing item in a data structure.
• Delete − Algorithm to delete an existing item from a data structure.

Characteristics of an Algorithm

Not all procedures can be called an algorithm. An algorithm should have the following characteristics −

• Unambiguous − Algorithm should be clear and unambiguous. Each of its steps (or phases), and their inputs/outputs should be clear and must lead to only one meaning.
• Input − An algorithm should have 0 or more well-defined inputs.
• Output − An algorithm should have 1 or more well-defined outputs, and should match the desired output.
• Finiteness − Algorithms must terminate after a finite time.
• Feasibility − Should be simple, generic and practical. An algorithm must be feasible with the available resources.
• Independent − An algorithm should have step-by-step directions, which should be independent of any programming code.

How to Write an Algorithm?

There are no well-defined standards for writing algorithms. Rather, it is problem and resource dependent. Algorithms are usually written in pseudocode, or a combination of your speaking language and programming language.

Algorithm Analysis

Efficiency of an algorithm can be analyzed at two different stages, before implementation and after implementation. They are the following −

• Priori Analysis − This is a theoretical analysis of an algorithm. Efficiency of an algorithm is measured by assuming that all other factors, for example, processor speed, are constant and do not affect the implementation.
• Posterior Analysis − This is an empirical analysis of an algorithm. The selected algorithm is implemented using programming language. This is then executed on target computer machine. In this analysis, actual statistics like running time and space required, are collected.

Algorithm Complexity

Suppose X is an algorithm and n is the size of input data, the time and space used by the algorithm X are the two main factors, which decide the efficiency of X.

• Time Factor − Time is measured by counting the number of key operations such as comparisons in the sorting algorithm.
• Space Factor − Space is measured by counting the maximum memory space required by the algorithm.

Algorithm Space Complexity

Space complexity of an algorithm quantifies the amount of space or memory taken by an algorithm to run as a function of the length of the input. Similar to time complexity, space complexity is often expressed in Big O notation, such as O(n), O(nlogn), O(n^2), etc.

Algorithm Time Complexity

Time complexity of an algorithm quantifies the amount of time taken by an algorithm to run, as a function of the length of the input. Time complexity is usually expressed in Big O notation, which describes the upper bound of the time complexity in the worst case scenario.

Pseudocode

Pseudocode is a method of planning which enables the programmer to plan without worrying about syntax.

Algorithm Examples

Here are some examples of algorithms in C++:

• Bubble Sort Algorithm
• Insertion Sort Algorithm
• Selection Sort Algorithm
• Merge Sort Algorithm
• Quick Sort Algorithm

See Also

• Data Structures
• Programming Languages
• C++ Programming