Home Original page

Algorithms : Standard Algorithms

Standard Algorithms

Don't reinvent the wheel!

Introduction

In this section of the Algorithms Tutorial we will investigate a series of standard algorithms. Standard ways to do useful processing that happens regularly. Rather than reinvent the wheel, use and learn from these algorithms and save your self a lot of time and effort.

These algorithms are time tested and used by many people so you can use them with confidence knowing they have been rigourously tested and critiqued.

You don't have to use the algorithms as is. A lot of the time you will be able to as they represent often used, standard processing requirements, however if your needs vary there is nothing stopping you from useing them as a base and modifying to suit.

  • Searching algorithms
  • Sorting algorithms (coming soon)
  • Advanced data structure algorithms (coming soon)

Basic Algorithms

These are simple and regularly used elements of processing.

Switch Two Items

Let's say you have two values and want to switch the variables that hold them :

Switch variables

  1. BEGIN
  2.   Get var1
  3.   Get var2
  4.   temp = var1
  5.   var1 = var2
  6.   var2 = temp
  7. END

Switch variablesThis standard algorithm can easily be expanded to switch up any number of variables.

Array based algorithms

For the following algorithms we will assume an array called elements. We will also use zero indexing.

Load an array of values

A Priming read is when we ask for a value or read a line from a file that is important in the condition of the loop prior to entering the loop.

Load array values

  1. BEGIN
  2.   Set i to 0"
  3.   Get dataValue
  4.   WHILE dataValue != "ZZZ"
  5.     Set elements[i] to dataValue
  6.     Increment i by 1
  7.     Get dataValue
  8.   ENDWHILE
  9.   
  10.   Return elements
  11. END

Print an array of values

Print array values

  1. BEGIN
  2.   Set i to 0"
  3.   WHILE i < length of elements
  4.     Display elements[i]
  5.     Increment i by 1
  6.   ENDWHILE
  7. END

Sum an array of values

Sum array values

  1. BEGIN
  2.   Set i to 0"
  3.   Set total to 0"
  4.   WHILE i < length of elements
  5.     total = total + elements[i]
  6.     Increment i by 1
  7.   ENDWHILE
  8.   
  9.   Return total
  10. END

String based alorithms

We will look at three basic algorithms for manipulating strings. Think of these as the building blocks from which most other string manipulation functions can be created. These are :

  • Substring
  • Deleting
  • Inserting

When working with manipulating strings we can effectively treat them like arrays of characters. Because of this, these standard algorithms can also be easily adapted to perform various array manipulation actions as well.

We will assume zero indexing for the following algorithms.

Substring

The original string remains untouched and we copy out or extract a portion of the string. There are two methods we can use in terms of specifying what to extract :

  • Specify the start position in the string and how many charactesr to extract.
  • Specify the start position and the end position to extract from.

Substing length

  1. BEGIN SubString(startCharacter, amount, baseString)
  2.   Set extracted to ""
  3.   Get pointer to startCharacter
  4.   WHILE pointer < startCharacter + amount
  5.     extracted = extracted + baseString[pointer]
  6.     Increment pointer by 1
  7.   ENDWHILE
  8.   
  9.   Return extracted
  10. END

subString

Substring by position

  1. BEGIN SubString(startCharacter, endCharacter, baseString)
  2.   Set extracted to ""
  3.   Get pointer to startCharacter
  4.   WHILE pointer < endCharacter
  5.     extracted = extracted + baseString[pointer]
  6.     Increment pointer by 1
  7.   ENDWHILE
  8.   
  9.   Return extracted
  10. END SubString

These algorithms (and the ones below) assume that the input parameters are valid (eg. the endCharacter is not a value beyond the length of the baseString). If you require validation you will need to add that in yourself.

The next two standard algorithms will make use of the algorithms we just defined.

Deleting Strings

Removing a part of the string can be achieved by thinking of this process as cutting the original string into three sections :

  • The part of the string before the deleted section.
  • The part of the string to be deleted.
  • The part of the string after the deleted section.

In this regard. if we get the substring before and the substring after and join them together then we have effectively deleted the required section.

Delete Substring

  1. BEGIN DeleteSubString(startCharacter, endCharacter, baseString)
  2.   before = SubString(0, startCharacter, baseString)
  3.   after = SubString(endCharacter + 1, length of baseString, baseString)
  4.   finalString = before + after
  5.   
  6.   Return finalString
  7. END DeleteSubString

deleteSubString

Again, this algorithm can be written with startCharacter and endCharacter as well.

Inserting Strings

Inserting a string into another is similar to the delete algorithm in that we split the original string into parts and then rejoin in the right way.

Insert String

  1. BEGIN InsertString(startCharacter, insertString, baseString)
  2.   before = SubString(0, startCharacter, baseString)
  3.   after = SubString(startCharacter + 1, length of baseString, baseString)
  4.   finalString = before + insertString + after
  5.   
  6.   Return finalString
  7. END InsertString

Random number based algorithms

We will look at two things here :

  • Generating a single random number.
  • Generating a set of random numbers with no repeated numbers.

A single random number

Most modern programming languages have built in functions that can generate random numbers. They are generally very well written and although they are pseudo-random numbers, for all intents and purposes they are fairly random. A lot of languages have a built in function that will return a random value between 0 and 1.

0 ≤ x < 1

Note that the value could be equal to 0 but will be less than 1.

With this function we can easily transform the value into random integers in any range we want. Let's say this base function is called RND

Random number

  1. BEGIN randomInteger(min, max)
  2.   randomBase = RND()
  3.   range = max - min
  4.   randomRange = randomBase * range
  5.   randominteger = integer value of randomRange + min
  6.   
  7.   Return randomInteger
  8. END
  • Line 2 - obtain a random number as a fraction between 0 and 1
  • Line 3 - determine the range of numbers we need to expand it into
  • Line 4 - by multiplying the number by the range we expand it into numbers between zero and range
  • Line 5 - by adding min we shift the number to be between min and max

A set of unique random numbers

We often need a set of unique random numbers within a given range. That is there are no repeated numbers within the set. We will look at two algorithms to achieve this. A simple yet inefficient means and a more complex but rather effiecient means.

First off, the simple yet inefficient means :

Unique Random Numbers - Simple

  1. BEGIN UniqueRandom(min, max, amount)
  2.   Set numbers to blank array
  3.   Set i to 0
  4.   
  5.   WHILE length of numbers < amount
  6.     number = randomInteger(min, max)
  7.     IF number is not in numbers THEN
  8.       numbers[i] = number
  9.       Increment i by 1
  10.     ENDIF
  11.   ENDWHILE
  12.   
  13.   Return numbers
  14. END UniqueRandom

For the part is not in numbers (line 7) you would probably use a linear search.

This algorithm is quite simple however you can end up wasting a lot of time if you keep generating random numbers that have already been generated previously.

Improving from this there are a few options we could take. We could for instance :

  • Create an array with all the numbers between max and min then shuffle that array (like you would a deck of cards). Then take in order from the beginning of the array the amount you need. This method seems reasonable but what degree of shuffling is required as acceptable to bring in randomness. It is also a lot of work if you have a large range and only need a small amount of numbers.
  • Create a shadow array with the same number of items as the numbers to choose from and set them all to False. As you use them you can set them to True. This method is nice, and simple but still has the problem of repeatedly selecting a used number (it is just a bit quicker now to determine that it has in fact already been used).

There are also more complex solutions such as the Floyd algorithm and the Knuth algorithm. These methods involve a bit of mathematics but if you are up to it they are well worth investigating.

We will consider a method that is sort of a middle ground. It is fairly efficient and not too complex. It does have the down side of requireing a shadow array of numbesr however so there is a hit to memory requirements. For smallish ranges of numbers on modern computers this won't be an issue but if your range of numbers is quite large it could become an issue.

Unique Random Numbers - More Efficient

  1. BEGIN UniqueRandom(min, max, amount)
  2.   Set availableNumbers to blank array
  3.   Set i to 0
  4.   Set range to max - min
  5.   
  6.   WHILE i < range
  7.     availableNumbers[i] = min + i
  8.     Increment i by 1
  9.   ENDWHILE
  10.   
  11.   i = 0
  12.   Set numbers to blank array
  13.   
  14.   WHILE length of numbers < amount
  15.     number = randomInteger(i, range)
  16.     numbers[i] = availableNumbers[number]
  17.     availableNumbers[number] = availableNumbers[i]
  18.     Increment i by 1
  19.   ENDWHILE
  20.   
  21.   Return numbers
  22. END UniqueRandom

This might seem a little confusing so let's break it down :

  • Lines 2 - 9 : Create a base array with all the possible numbers to choose from. That is, each number between min and max.
  • Line 15 : Select a random index from that base array. It's important to note that we are selecting a random index as opposed to a random number.
  • Line 16 : Copy the number stored at that random index into our array of random numbers.
  • Line 17 : Move the number stored at index i to that of the random index we generated. This overwrites the number so we don't have to worry about it being selected again.
  • Line 18 : Increment i, which actually serves two purposes. i represents the current point in the numbers array to place the next item. It also represents the point to start selecting the next random number from.

A simple example will help to illustrate the operation of this algorithm.

Let's say we want to generate 3 random numbers between 3 and 10.

Set up the availableNumbers array :

unique random numbers 1

The first random number we generate is 2. This means that the value at index 2 is copied into the numbers array :

unique random numbers 2

i is currently 0 so we copy the number at index 0 over the number at index 2 :

unique random numbers 3

i is now incremented to 1 meaning that we will only select numbers between index 1 and 7. We start the process again and generate a random number of 5.

unique random numbers 4

Again we move the item at index i (1) to the random index we generated (5).

unique random numbers 5

We increment i again to 2 and generate another random number, this time between 2 and 7, which happens to be 5 again. This is ok as the number at index 5 is no longer 8 but 4. We have now generated our 3 unique random numbers.

unique random numbers 6