In this section, we will explore how to implement various algorithms in ALGOL. This will include understanding the algorithm, writing the code, and testing it. We will cover sorting algorithms, searching algorithms, and some basic graph algorithms.
Key Concepts
- Understanding Algorithms: Learn the theory behind common algorithms.
- Writing Code: Translate the algorithm into ALGOL code.
- Testing: Ensure the algorithm works correctly with various inputs.
Sorting Algorithms
Bubble Sort
Bubble Sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted.
Bubble Sort Algorithm
- Compare each pair of adjacent elements.
- Swap them if they are in the wrong order.
- Repeat the process for each element in the list.
Bubble Sort Code in ALGOL
begin
integer array[1:10];
integer i, j, temp, n;
n := 10;
array := (10, 9, 8, 7, 6, 5, 4, 3, 2, 1);
for i := 1 step 1 until n - 1 do
for j := 1 step 1 until n - i do
if array[j] > array[j + 1] then
temp := array[j];
array[j] := array[j + 1];
array[j + 1] := temp;
end if;
end for;
end for;
for i := 1 step 1 until n do
print(array[i]);
end for;
end;Explanation
- Initialization: We initialize an array with 10 elements in reverse order.
- Outer Loop: Runs from the first element to the second last element.
- Inner Loop: Runs from the first element to the last unsorted element.
- Swap: If the current element is greater than the next element, they are swapped.
- Print: Finally, the sorted array is printed.
Exercise: Implement Selection Sort
Task: Write an ALGOL program to implement the Selection Sort algorithm.
Selection Sort Algorithm:
- Find the minimum element in the unsorted part of the array.
- Swap it with the first unsorted element.
- Move the boundary of the sorted part one step to the right.
- Repeat until the array is sorted.
Solution:
begin
integer array[1:10];
integer i, j, minIndex, temp, n;
n := 10;
array := (10, 9, 8, 7, 6, 5, 4, 3, 2, 1);
for i := 1 step 1 until n - 1 do
minIndex := i;
for j := i + 1 step 1 until n do
if array[j] < array[minIndex] then
minIndex := j;
end if;
end for;
temp := array[i];
array[i] := array[minIndex];
array[minIndex] := temp;
end for;
for i := 1 step 1 until n do
print(array[i]);
end for;
end;Searching Algorithms
Linear Search
Linear Search is a simple search algorithm that checks every element in the list until the desired element is found or the list ends.
Linear Search Algorithm
- Start from the first element.
- Compare each element with the target value.
- If the target value is found, return the index.
- If the end of the list is reached, return -1.
Linear Search Code in ALGOL
begin
integer array[1:10];
integer i, target, n, found;
n := 10;
array := (1, 2, 3, 4, 5, 6, 7, 8, 9, 10);
target := 7;
found := -1;
for i := 1 step 1 until n do
if array[i] = target then
found := i;
exit;
end if;
end for;
if found = -1 then
print("Element not found");
else
print("Element found at index: ", found);
end if;
end;Explanation
- Initialization: We initialize an array and set the target value.
- Loop: Runs through each element in the array.
- Comparison: If the current element matches the target, the index is stored and the loop exits.
- Output: Prints the index if found, otherwise prints "Element not found".
Exercise: Implement Binary Search
Task: Write an ALGOL program to implement the Binary Search algorithm. Assume the array is sorted.
Binary Search Algorithm:
- Find the middle element of the array.
- If the middle element is the target, return the index.
- If the target is less than the middle element, repeat the search on the left half.
- If the target is greater, repeat the search on the right half.
- If the subarray is empty, return -1.
Solution:
begin
integer array[1:10];
integer left, right, mid, target, n, found;
n := 10;
array := (1, 2, 3, 4, 5, 6, 7, 8, 9, 10);
target := 7;
left := 1;
right := n;
found := -1;
while left <= right do
mid := (left + right) div 2;
if array[mid] = target then
found := mid;
exit;
else if array[mid] < target then
left := mid + 1;
else
right := mid - 1;
end if;
end while;
if found = -1 then
print("Element not found");
else
print("Element found at index: ", found);
end if;
end;Conclusion
In this section, we have covered the implementation of basic sorting and searching algorithms in ALGOL. We started with Bubble Sort and Linear Search, and provided exercises for Selection Sort and Binary Search. Understanding these fundamental algorithms is crucial for solving more complex problems and optimizing code performance. In the next section, we will delve into more advanced topics and practical applications of ALGOL.