Sorting a List of Numbers Using Insertion Sort Algorithm in Algol

Insertion sort is a simple sorting algorithm that works by building a final sorted list one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. However, insertion sort provides several advantages such as simplicity, low memory requirement, and adaptability. In this article, we will show you how to implement the insertion sort algorithm in Algol to sort a list of numbers.

Algorithm

The insertion sort algorithm works by iterating through an array of elements, comparing each element with the previous ones until it is placed in its correct position. The algorithm starts by assuming that the first element in the array is already sorted. Then, it moves to the second element and compares it with the first. If the second element is smaller than the first, it is swapped with the first element. The algorithm then moves to the third element and compares it with the second and first elements, swapping if necessary. The process continues until the last element in the array is reached.

Steps

Here are the steps for implementing the insertion sort algorithm in Algol:

1. Read the number of elements in the list n.
2. Read the list of numbers into an array a[1:n].
3. Iterate over the array a[2:n] with the index i from 2 to n.
4. Set j to i-1.
5. While j > 0 and a[j] > a[j+1], swap a[j] with a[j+1] and decrement j.
6. Output the sorted list of numbers.

Code

Here is the Algol program that sorts a list of numbers using the insertion sort algorithm:

begin
write(“Enter the number of elements in the list: “);
read(n);
write(“Enter the list of numbers: “);
for i := 1 step 1 until n do
read(a[i]);

for i := 2 step 1 until n do
begin
j := i – 1;
while j > 0 and a[j] > a[j+1] do
begin
temp := a[j];
a[j] := a[j+1];
a[j+1] := temp;
j := j – 1;
end;
end;

write(“The sorted list of numbers is: “);
for i := 1 step 1 until n do
write(a[i], ” “);
end.

Output

Suppose we have the following input:

Enter the number of elements in the list: 5
Enter the list of numbers: 5 3 1 4 2

The program will output:

The sorted list of numbers is: 1 2 3 4 5

Conclusion

Insertion sort is a simple sorting algorithm that can be easily implemented in Algol. It is suitable for small to medium-sized lists and provides several advantages such as simplicity, low memory requirement, and adaptability. By following the steps outlined in this article and using the sample code provided, you can create your own Algol program to sort a list of numbers using the insertion sort algorithm.

It’s important to note that insertion sort has a time complexity of O(n^2), which means that it can become very slow as the size of the list grows. This makes it unsuitable for sorting very large datasets.

However, insertion sort does have some advantages over other sorting algorithms. For example, it works well on small lists and has very low overhead. It also has the added benefit of sorting the list in place, meaning that it doesn’t require any additional memory to create a new, sorted list.

To improve the efficiency of insertion sort, there are some optimizations that can be made. For example, one optimization involves using binary search to find the correct position to insert each element, rather than iterating over the entire sorted list each time. This reduces the time complexity to O(n log n).

Another optimization is to use a shell sort algorithm, which is a variation of insertion sort. Shell sort improves the performance of insertion sort by comparing elements that are further apart first, rather than comparing adjacent elements. This helps to ensure that the larger elements “bubble up” to their correct position more quickly.

In summary, insertion sort is a simple and effective sorting algorithm that can be easily implemented in Algol. While it may not be the most efficient algorithm for large datasets, it has some advantages such as simplicity and low memory usage. By optimizing the algorithm, it’s possible to improve its performance and make it more suitable for larger datasets.

Share on Facebook

Tweet

Follow us

Save