kids encyclopedia robot

Algorithm facts for kids

Kids Encyclopedia Facts

An algorithm is like a set of step-by-step instructions to solve a problem or finish a task. Think of it as a recipe! Just like a recipe tells you what to do with ingredients to make a dish, an algorithm tells a computer what to do with information to get a result.

The word 'algorithm' comes from the name of a Persian mathematician named Al-Khwārizmī, who lived a long time ago (around 780–850 AD).

In everyday life, an algorithm can be a simple list of steps. For computers, an algorithm is a very exact list of operations. These operations can be written in special ways like pseudocode, flow charts, or programming languages.

Comparing Algorithms

There is usually more than one way to solve a problem. For example, there might be many different recipes to make the same dish. The same is true for algorithms. However, some ways are better than others.

When we look at algorithms, we often want to know how fast a computer can solve a problem using a certain algorithm. We want our algorithms to be as quick as possible.

Some recipes are harder to follow because they take more time or have many steps. Algorithms are similar. An algorithm is better if it's easier and faster for a computer to do. The way we measure how difficult or time-consuming an algorithm is, is called its complexity.

Sorting Things

Let's look at an example of an algorithm. Imagine you have a pile of cards with different colors. This algorithm tells you how to sort them into piles of the same color:

  • Pick up all of the cards.
  • Take one card from your hand and look at its color.
  • If there is already a pile of cards of that color, put your card on that pile.
  • If there is no pile of cards of that color yet, make a new pile with just this card.
  • If you still have cards in your hand, go back to the second step.
  • If your hand is empty, all the cards are sorted. You are done!

Sorting by Numbers

Here are examples of algorithms for sorting a stack of cards with numbers on them, so the numbers are in order (from smallest to biggest).

Players start with a stack of cards that are not sorted.

First Sorting Method: Bubble Sort

This method goes through the stack of cards, one card at a time. It compares a card to the next one. This algorithm is called bubble sort. It can be slow for many cards.

  • If the stack of cards is empty, or it only has one card, it is already sorted. You are done.
  • Look at the first card (the top) of the stack. Let's call this card A.
  • If there are no more cards after card A, go to step 8.
  • The next card in the stack is card B.
  • If card B has a lower number than card A, swap their places. Remember that you swapped them.
  • Now, look at the next pair of cards in the stack. Go back to step 3.
  • If you did not swap any cards during this entire run through the stack, then the cards are sorted. You are done.
  • Otherwise, go back to step 2 and start another run.

Step-by-step Example

Bubble sort animation
Animation that shows how a bubble sort works

Let's sort the numbers "5 1 4 2 8" from smallest to biggest using this method. The top of the stack is on the left. We will compare cards that are in bold.

First time through the stack:

  • ( 5 1 4 2 8 ) → ( 1 5 4 2 8 ) — The algorithm compares 5 and 1, then swaps them.
  • ( 1 5 4 2 8 ) → ( 1 4 5 2 8 ) — Compares 5 and 4, then swaps them.
  • ( 1 4 5 2 8 ) → ( 1 4 2 5 8 ) — Compares 5 and 2, then swaps them.
  • ( 1 4 2 5 8 ) → ( 1 4 2 5 8 ) — Compares 5 and 8. They are already in order, so no swap.

Second time through the stack:

  • ( 1 4 2 5 8 ) → ( 1 4 2 5 8 ) — Compares 1 and 4. No swap.
  • ( 1 4 2 5 8 ) → ( 1 2 4 5 8 ) — Compares 4 and 2, then swaps them.
  • ( 1 2 4 5 8 ) → ( 1 2 4 5 8 ) — Compares 4 and 5. No swap.
  • ( 1 2 4 5 8 ) → ( 1 2 4 5 8 ) — Compares 5 and 8. No swap.

The cards are now sorted, but the algorithm doesn't know it yet. It needs one full run where no swaps happen to confirm it's sorted.

Third time through the stack:

  • ( 1 2 4 5 8 ) → ( 1 2 4 5 8 ) — No swap.
  • ( 1 2 4 5 8 ) → ( 1 2 4 5 8 ) — No swap.
  • ( 1 2 4 5 8 ) → ( 1 2 4 5 8 ) — No swap.
  • ( 1 2 4 5 8 ) → ( 1 2 4 5 8 ) — No swap.

Finally, no cards were swapped in this last run. The algorithm knows the stack is sorted and stops.

History

This algorithm is called Bubble sort because smaller numbers "bubble up" to the top of the stack. It's easy to understand, but it's not very efficient because it takes many runs to sort a stack of cards.

Second Sorting Method: Mergesort

Mergesort algorithm diagram
Sorting 7 numbers using the Mergesort algorithm

This algorithm uses a different idea. Sometimes, a big problem can be solved by breaking it into smaller, easier problems. This is called recursion. This method is a bit harder to understand than Bubble Sort, but it's much faster.

How it Works

  • If the stack has no cards or only one card, it's already sorted. You are done.
  • Split the stack of cards into two halves that are about the same size.
  • Sort each of these two smaller stacks using this same algorithm (start again from step 1 for each half).
  • Once both halves are sorted, combine them back together into one sorted stack.
  • The result is a fully sorted stack of cards. You are done!

Merging Two Stacks

Imagine you have two sorted stacks of cards, let's call them Stack A and Stack B. You want to combine them into one new sorted stack, Stack C (which starts empty).

  • If either Stack A or Stack B is empty, just take all the cards from the stack that isn't empty and put them on top of Stack C. You are done merging.
  • Look at the top card of Stack A and the top card of Stack B. Take the card with the lower number and put it on top of Stack C.
  • If there are still cards left in Stack A or Stack B, go back to step 1 to keep merging.

History

John von Neumann created this algorithm in 1945. He called it Mergesort. It is a very good and efficient way to sort things.

Third Sorting Method: Quicksort

Sorting quicksort anim
The Quicksort algorithm. The element with the red bar is chosen as the pivot.

The first algorithm (Bubble Sort) is slow. This third method is an improvement. Instead of comparing cards that are next to each other, it picks a "special" card first.

How it Works

  • You start with a stack of cards, let's call it Stack A. You will create two other empty stacks, B and C.
  • If Stack A has no cards or only one card, it's sorted. You are done.
  • Pick one card from Stack A. This card is called the pivot. It's best if you pick it randomly.
  • Compare all the other cards in Stack A to this pivot card.
    • Cards with a smaller number than the pivot go into Stack B.
    • Cards with a number equal to or bigger than the pivot go into Stack C.
  • If there are any cards in Stack B or Stack C, these stacks need to be sorted using this same algorithm (start again from step 1 for both Stack B and Stack C).
  • Once Stack B and Stack C are sorted, the final sorted stack is made by putting the sorted Stack B first, then the pivot card, and then the sorted Stack C.

History

C. A. R. Hoare developed this algorithm in 1960. It is called Quicksort and is one of the most widely used sorting algorithms today because it's very fast.

Putting Algorithms Together

If you have cards with both colors and numbers, you can sort them by color first, then sort each colored stack by number. After that, you just put the sorted colored stacks together.

The algorithms for sorting by numbers are usually more complex than sorting by colors. This is because they might need to repeat steps many times.

See Also

Images for kids

See also

Kids robot.svg In Spanish: Algoritmo para niños

kids search engine
Algorithm Facts for Kids. Kiddle Encyclopedia.