How to write an algorithm

1. First define the problem you want the algorithm to solve.

For example, suppose we want to write an algorithm to find the maximum value from a list of numbers.

2. Break the problem down into smaller, manageable steps.

• Initialize the ‘max’ variable to the first value in the list.
• For each subsequent value in the list, compare with “max”.
• If the value is greater than “max”, set “max” to that value.
• Continue doing this until every value in the list has been compared.
• Returns the final “max” value.

3. Write your algorithm in pseudocode or a programming language.

Algorithm written in pseudo code:

4. Test your algorithm to make sure it is correct and efficient.

You can test the algorithm by entering different lists of numbers and verifying that it returns the maximum correct value. You can also analyze the time complexity of your algorithm to determine how well it scales for larger inputs.

Example:-

Input: [1, 5, 2, 7, 3]

Output: 7.

Explanation: 7 is the maximum value in the list.

5. Optimize the algorithm.

Look for ways to optimize algorithms for making them faster and more efficient. This may involve modifying pseudocode or implementing more efficient data structures or algorithms.

Basic writing of algorithms

Example: – The sum of two integers.

Step 1 – Get started

Step 2 – Declare three integers a, b, c

Step 3 – Define the values of a and b

Step 4 – Add the values of a and b

Step 5 – Save the output of step 4 in c

Step 6 – Print c

Step 7 – Stop

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.

The complexity of an algorithm f(n) gives the running time and/or the storage space required by the algorithm in terms of n as the size of input data.

Space Complexity

Space complexity of an algorithm represents the amount of memory space required by the algorithm in its life cycle. The space required by an algorithm is equal to the sum of the following two components −

• A fixed part that is a space required to store certain data and variables, that are independent of the size of the problem. For example, simple variables and constants used, program size, etc.
• A variable part is a space required by variables, whose size depends on the size of the problem. For example, dynamic memory allocation, recursion stack space, etc.

Space complexity S(P) of any algorithm P is S(P) = C + SP(I), where C is the fixed part and S(I) is the variable part of the algorithm, which depends on instance characteristic I. Following is a simple example that tries to explain the concept −

Algorithm: SUM(A, B)

Step 1 – START

Step 2 – C ← A + B + 10

Step 3 – Stop

Here we have three variables A, B, and C and one constant. Hence S(P) = 1 + 3. Now, space depends on data types of given variables and constant types and it will be multiplied accordingly.

Time Complexity

Time complexity of an algorithm represents the amount of time required by the algorithm to run to completion. Time requirements can be defined as a numerical function T(n), where T(n) can be measured as the number of steps, provided each step consumes constant time.

For example, addition of two n-bit integers takes n steps. Consequently, the total computational time is T(n) = c ∗ n, where c is the time taken for the addition of two bits. Here, we observe that T(n) grows linearly as the input size increases.

Type of algorithms used in C language.

1. Sorting algorithms

C provides a rich set of data types and operators that can be used to implement various sorting algorithms such as bubble sort, insertion sort and quick sort.

These algorithms are useful in many applications because they can be used to sort data of different sizes and types.

There are different sorting algorithms.

they are:-

(i) Bubble sort: An uncomplicated sorting algorithm that compares nearby components repeatedly and switches them out if they are out of order.

The Algorithm for Bubble sort is:-

1. Start with an unsorted list of elements.
2. Compare the first two elements in the list. If the first element is larger than the second element, swap them.
3. Move on to the next pair of elements and repeat step 2 until the end of the list is reached.
4. For each item on the list, repeat steps 2 and 3 once more. that is referred to as passes.
5. Repeat steps 2-4 for the entire list. As you repeat the passes, elements will “bubble up” to their correct position in the sorted list.
6. Once a pass is completed and no swaps are made, the list is sorted, and the algorithm can stop.
7. The final sorted list is returned.

(ii) Insertion sort: a method of sorting that creates a sorted list one individual element at a time by placing each one in the appropriate spot.

The Algorithm for Insertion sort is:-

1. Initialize an empty sorted list and an unsorted list of the elements to be sorted.
2. The first member from the unsorted list should be taken and placed in the appropriate position in the sorted list.
3. Repeat step 2 for each subsequent element in the unsorted list.
4. Compare the current element with the elements in the sorted list, starting with the element immediately to the left.
5. Swap the two elements if the current element is smaller than the element to its left.
6. If the current element is larger than the element to its left, insert it at its correct position in the sorted list.
7. Repeat steps 4-6 for each subsequent element in the unsorted list.
8. Once all elements have been processed, the sorted list will contain all elements in the correct order.
9. The sorting process is complete.

(iii) Selection sort: a method of sorting that consistently starts the sorted listing with the smallest detail from the unordered listing.

The Algorithm for Selection sort is:-

1. Begin by setting the primary element of list as the min element.
2. Repeat through the remaining items in the list, comparing each one to the current minimum.
3. Set a new minimum if an element is found to be smaller than the existing one.
4. Change the current minimum to the first element of the list whenever it reaches its conclusion.
5. For the remaining unsorted portion of the listing, repeat steps 2-4, but begin with the second item on the list (as the first element is already sorted).
6. Continue sorting the list in this manner until it is all sorted.

(iv) Quick sort: A divide-and-conquer sorting algorithm that chooses a pivot element and splits the list into sublists depending on whether the elements are fewer than or more than the pivot. After that, the sublists are sorted repeatedly until the full list is sorted.

The Algorithm for Quick sort is:-

1. Choose a pivot element from the list. This is typically the first element, but it can also be a random element or the median of the list.
2. Divide the list into two sublists: one containing elements less than the pivot and one containing elements greater than the pivot.
3. Recursively sort the sublist containing elements less than the pivot using the same process.
4. Use the same procedure to recursively sort the sublist of entries larger than the pivot.
5. Concatenate the sorted sublists with the pivot element in between to form a fully sorted list.
6. Return the fully sorted list.

(v) Merge sort: The divide-and-conquer sort algorithm divides the list into two halves, sorts each half, and then merges the two halves in sorted order.

Merge-sort Algorithm:

1. Make two sublists out of the list: one with elements below the pivot and one with elements above the pivot.
2. Produces a new sorted sublist by iteratively merging sublists until only one sublist exists. This will be your sorted list.
3. Steps to merge two sub-directories:-
4. Create an empty list to hold the sorted elements.
5. Compares the first element of each sublist.
6. Adds the smaller element to the new list and removes it from the parent sublist.
7. Repeat the steps 2 and 3 until a list is completly empty.
8. Adds the remaining elements from other sublists to a new list.
9. Replaces the merged sublist with the new sorted list.
10. Repeat this process until all sublists are merged into one sorted list.

(vi) Heapsort: A sorting algorithm that sorts elements using a data structure called heap.

This is the classification algorithm:

1. Build max heap: Starting with the first non-leaf node, compare each node with its child nodes and replace the nodes with the largest of its children to satisfy the max heap property.
2. Swap root with last element: Swap the root (largest element) with the last element in the stack.
3. Stack the rest of the elements. Starting from the root, each node is compared with its children, swapping nodes with their older children until the max heap property is satisfied.
4. Repeat steps 2 and 3 with the newly stacked elements, except for the last element in the correct position.
5. Repeat this process until only one element remains in the stack. This is now sorted.
6. Heapify Down: Starting from the root node, it compares elements with its children and swaps with the larger of the two until the max heap property is satisfied.
7. Heapify Up: Start with the last element in the heap, compare it to its parent, and swap it with the parent to satisfy the max heap property.

(vii) Radix sort: A sorting algorithm that sorts elements based on the digits or digits of their binary representation.

The Algorithm for Radix sort is:-

1. determine how many digits are contained in the input listing’s largest element.
2. Initialize a variable, say digit place, to 1, which represents the current digit place.
3. Create an empty list for each possible digit value from 0 to 9.
4. Iterate through the input list and add each element to the appropriate list based on the value of the current digit place.
5. Concatenate all the lists together to form the new list in the order of the digit lists.
6. Multiply digitPlace by 10 to move to the next digit place.
7. Repeat steps 4-6 for each digit place until all digits in the largest element have been considered.
8. The final list will be sorted in ascending order by the digits of the elements.
9. Return the final sorted list.

Example

Let’s try to learn another algorithm-writing by using an example.