xLeD's Lesson 1

[Zeriab 9]

This is a lesson I wrote for someone called xLeD at a different forum, I'm now sharing it with guys :D

 

Lesson 1

Today's topic: Simple Sorting

 

Hey xLeD

 

First of I will start with a little something I have written about Arrays. Just skip what you know.

Then I will teach you the search algorithm Insertion-Sort.

 

Array

Just skip the parts on theory you don't understand. I will not use pictures.

 

Theory

An array is a list of elements. A vector of elements is also correct. Just a different wording.

Let us assume that the elements are integers (whole numbers).

Try to think of a table with 1 column and a number of rows, let's say 10 rows.

In each cell is an integer. This integer is what is meant as an element. This is how the data is stored

There are 10 integers (elements) in all because there are 10 rows. This is an array with 10 elements.

 

Let's go back to the rows again and say we want 1 of the integers out from a certain cell.

We must have a way of finding the right cell. We have. It is called the index.

Think about us looking on the top row. Think that if you look at the bottom cell it will be farther away than the top cell. You can say that there is a distance between a certain cell and the top cell.

We can use this distance to get the cell we want. We could say that we wanted the cell with distance 5.

The top cell would of course have distance = 0 and the bottom cell would have the amount of elements - 1. Continuing the example the bottom cell would have distance = 9

Wow? amount of elements - 1... What does that mean?

Remember when we said that there were 10 rows? This is the amount of elements. So we have 10 - 1 = 9.

If we now call distance for index you we have solved the question about what index means.

 

I hope it was understandable

 

Ruby

All the above might be very well, but it does not explain how to you it in ruby.

In Ruby everything is build of objects, which are created from classes. So naturally there is an Array-class.

 

Before going further I must point you to Ruby references on the Array-class

The above is just basically the syntax with comments. Therefore you should read there instead of here.

Just a quick example though: (Same elements are allowed)

[6, 2, 4, 9, 2]   #<--- is an array
array = [6, 2, 4, 9, 2]   #<---- for before

# Getting the elements out
p array[0]  #---> 6
p array[4]  #---> 2
p array[5]  #---> nil

# A little trick
p array[-1] #---> 2
p array[-2] #---> 9

# -1 returns the last element in the array
# -2 returns the element before the last element and so on

 

I don't know what else there is to say as most of it is in the references.

Just ask if there is something you can't understand in the references.

 

References

Ruby references

Wikipedia.org

 

Insertion-Sort:

Let A be an array. The pseudo code for the algorithm is:

Insertion-Sort(A)
1  for j = 2 to length[A]
2	  do key = A[j]
3		  i = j - 1
4		  while i > 0 and A[i] > key
5			  do A[i + 1] = A[i] 
6					i = i - 1
7		  A[i + 1] = key

 

Is it difficult to understand?

You should note that pseudo code isn't just pseudo code. This is my version of pseudo code.

Note that how much they are indented tells in which branch they are in.

For example is line 7 not in the while loop, but in the for-loop.

Line 6 is however in the for-loop.

And so on?

 

I know I haven't explained it well, and for that I apologize.

I have saved it for the tasks. You'll see ^_~

 

The tasks:

Reading is good, but alas reading alone is not as giving as tasks to follow up the read text.

Task 1:

A = [7, 12, 30, 12, 6, 29]

Put this array into the algorithm.

Calculate manually what A each time it is at the start of the for-loop.

Also calculate the output. (The sorted array).

 

Task 2:

Implement the algorithm into RMXP. Yup write it in Ruby.

Use the example from above to test.

 

Task 3:

Rewrite the algorithm so it sorts in decreasing order instead of increasing order.

In Ruby I mean.

 

Task 4: (optional)

Make the insertion sort as an extension to the Array class.

That is make a method insertion_sort that can be called like this:

[7, 12, 30, 12, 6, 29].insertion_sort

Good luck with the tasks.

- Zeriab

 

Sources:

Recursion @ Wikipedia - http://en.wikipedia.org/wiki/Insertion_sort

Introduction to Algorithms - http://mitpress.mit.edu/algorithms/