Counting Sort

Counting sort is so clever that it blew my mind, it doesn’t even use if clauses, this sorting algorithm doesn’t use comparisons. This algorithm can sort integer elements in the range 0 - k (k being exclusive)  where k it’s a known number. This is a great sorting algorithm when we have a large set of data in a range (0-k). It uses three arrays and has three for loops:

  1. We fill a helper array of size k where every index in the helper array represents an element of the original array, and the value is the number of times that element is present in the original array. For example, if the number 0 appears 4 times in the original array, the index 0 of the helper array will contain a 4.
  2. Using the information we have in the helper array, for every index of the helper array, we count how many elements are less or equal than that index, and we save that value in the corresponding index of the helper array. For example, if the number 0 appears 2 times, and the number 1 appears 3 times, in the helper array in the index 0 we are going to have the value 2, and in the index 1 we are going to have the value 5.
  3. We fill up the result array by grabbing an element of the original array and placing it in it’s correct position on the result array, and every time we do that, we decrement the counter corresponding to that value in the helper array. 

Pseudocode

let arr be an array of integers of range 0-max
let res be an array of integers of the same length that arr
let max be the largest number of arr + 1
let tmp be an array of length max filled with zeros
for i=0 while i=0 k--
    res[tmp[arr[k]]-1] = arr[k]
    tmp[arr[k]] = tmp[arr[k]]-1

Implementations

C (Apple LLVM version 5.1 (clang-503.0.40), compiled with gcc -ansi)

#include <stdio.h>

int main()
{
	int arr[] = {5,2,4,6,1,3,0,5,0,4,2};
	int arrlength = sizeof(arr)/sizeof(arr[0]);
	int res[arrlength];
	int max = 7;
	int tmp[max];
	for(int h = 0; h<max; h++)
	{
		tmp[h] = 0;
	}
	for(int i=0; i<arrlength; i++)
    {
        tmp[arr[i]] = tmp[arr[i]]+1;
	}
   	for(int j=1; j<max; j++)
	{
        tmp[j] = tmp[j] + tmp[j-1];
	}
    for(int k=arrlength-1; k>=0; k--)
	{
		res[tmp[arr[k]]-1] = arr[k];
		tmp[arr[k]] = tmp[arr[k]]-1;
	}
	
	for(int l=0; l<arrlength; l++)
	{
		printf("%d ",res[l]);
	}
	printf("\n");
}

Java 1.7

public class CountingSort{

    public static void countingSort(int arr[], int res[], int max){
        int tmp[] = new int[max];

        for(int i=0; i<arr.length; i++){
            tmp[arr[i]] = tmp[arr[i]]+1;
        }
        for(int j=1; j<max; j++){
            tmp[j] = tmp[j] + tmp[j-1];
        }
        for(int k=arr.length-1; k>=0; k--){
            res[tmp[arr[k]]-1] = arr[k];
            tmp[arr[k]] = tmp[arr[k]]-1;
        }
    }

    public static void main(String []args){
        int array[] = {5,2,4,6,1,3,0,5,0,4,2};
        int result[] = new int[array.length];
        int max = 7;

        CountingSort.countingSort(array,result,max);

        for(int i : result){
            System.out.print(i+" ");
        }
        System.out.println();
    }

}

Python 2.7.5

def counting_sort(arr,res,max):
    tmp = [0]*max
    for i in range(0,len(arr)):
        tmp[arr[i]] = tmp[arr[i]]+1
    for j in range(1,max):
        tmp[j] = tmp[j] + tmp[j-1]
    for k in range(len(arr)-1,-1,-1):
	res[tmp[arr[k]]-1] = arr[k]
	tmp[arr[k]] = tmp[arr[k]]-1

array = [5,2,4,6,1,3,0,5,0,4,2]
result = [0]*len(array)

counting_sort(array,result,7)
print result

Quicksort

This algorithm is often the best choice for sorting, because it’s remarkably efficient on average. It is a divide and conquer algorithm.

  • Divide: We partition the array in two subarrays.
  • Conquer: We sort the two subarrays by making recursive calls to the algorithm.

Example gif from wikipedia

Quicksort example from wikipedia

Quicksort example from wikipedia

Pseudocode (from wikipedia)

quicksort(A, i, k):
    if i < k:
    p := partition(A, i, k)
    quicksort(A, i, p - 1)
    quicksort(A, p + 1, k)

// left is the index of the leftmost element of the subarray
// right is the index of the rightmost element of the subarray (inclusive)
// number of elements in subarray = right-left+1
partition(array, left, right)
    pivotIndex := choose-pivot(array, left, right)
    pivotValue := array[pivotIndex]
    swap array[pivotIndex] and array[right]
    storeIndex := left
    for i from left to right - 1
        if array[i] ≤ pivotValue
            swap array[i] and array[storeIndex]
            storeIndex := storeIndex + 1
    swap array[storeIndex] and array[right]  // Move pivot to its final place
    return storeIndex

let arr be an unsorted array of integers
quicksort(arr,0,arr.length-1)

Implementations

C (Apple LLVM version 5.1 (clang-503.0.40), compiled with gcc -ansi)

#include <stdio.h>

void quicksort(int array[],int left, int right)
{
	if(left < right)
	{
		int q = partition(array,left,right);
		quicksort(array,left,q-1);
		quicksort(array,q+1,right);
	}
}

int partition(int array[],int left, int right)
{
	int x = array[right];
	int i = left - 1;
	for(int j=left; j<right; j++)
	{
		if(array[j] <= x)
		{
			i++;
			int temp = array[i];
			array[i] = array[j];
			array[j] = temp;
		}
	}
	int temp = array[++i];
	array[i] = array[right];
	array[right] = temp;
	return i;
}

int main()
{
	int arr[] = {5,2,4,6,1,3};
	int arrlength = sizeof(arr)/sizeof(arr[0]);
	quicksort(arr,0,arrlength-1);
	for(int i=0; i<arrlength; i++){
		printf("%d ",arr[i]);
	}
	printf("\n");
}

Java 1.7

public class QuickSort{

	public static void quickSort(int []array,int left, int right){
		if(left < right){
			int q = partition(array,left,right);
			quickSort(array,left,q-1);
			quickSort(array,q+1,right);
		}
	}

	public static int partition(int array[],int left,int right){
		int x = array[right];
		int i = left - 1;
		for(int j=left; j<right; j++){
			if(array[j]<=x){
				i++;
				int temp  = array[i];
				array[i] = array[j];
				array[j] = temp;
			}
		}
		int temp = array[++i];
		array[i] = array[right];
		array[right] = temp;
		return i;
	}

	public static void main(String []args){
		int arr[] = {5,2,4,6,1,3};
		QuickSort.quickSort(arr,0,arr.length-1);
		for(int i : arr){
			System.out.print(i+" ");
		}
		System.out.println();
	}
}

Python 2.7.5

def quicksort(array,left,right):
    if left < right:
        q = partition(array,left,right)
        quicksort(array,left,q-1)
        quicksort(array,q+1,right)

def partition(array,left,right):
    x = array[right]
    i = left - 1
    for j in range(left,right):
        if array[j] <= x:
            i = i + 1
	    temp = array[i]
            array[i] = array[j]
            array[j] = temp
    temp = array[i+1]
    array[i+1] = array[right]
    array[right] = temp
    return i + 1

arr = [5,2,4,6,1,3]
quicksort(arr,0,len(arr)-1)
print arr

Selection Sort

In the last post we implemented the Insertion Sort, today’s sorting algorithm is only good for a small number of elements, but it’s slower than the Insertion Sort. 

In Selection Sort we first find the smallest number in the array and exchange it for the first element, then we find the smallest number in the sub array [1,n], an exchange it for the second element, we repeat this until the n – 1 element.

Example gif from wikipedia

Selection sort example from wikipedia

Selection sort example from wikipedia

Pseudocode

let arr be an unsorted array of integers
    for i = 0 while i<arr.length-1 i++
        key = arr[i]
        indexOfSmallest = i;
        for j = i+1 while j<arr.length j++
            if key > arr[j]
                key = arr[j]
                indexOfSmallest = j
        arr[indexOfSmallest] = arr[i]
        arr[i] = key

Implementations

C (Apple LLVM version 5.1 (clang-503.0.40), compiled with gcc -ansi)

#include <stdio.h>
int main()
{
	int arr[] = {5,2,4,6,1,3};
	int arrlength = sizeof(arr)/sizeof(arr[0]);

	for(int i=0; i<arrlength-1; i++)
	{
		int key = arr[i];
		int indexOfSmallest = i;
		for(int j=i+1; j<arrlength; j++)
		{
			if(key>arr[j])
			{
				key = arr[j];
				indexOfSmallest = j;
			}
		}
		arr[indexOfSmallest] = arr[i];
		arr[i] = key;
	}

	for(int k=0; k<arrlength; k++){
		printf("%d ",arr[k]);
	}
	printf("\n");
}

Java 1.7

public class SelectionSort{
	
	public static void main(String []args){
		int arr[] = {5,2,4,6,1,3};

		for(int i=0; i<arr.length-1; i++){
			int key = arr[i];
			int indexOfSmallest = i;
			for(int j=i+1; j<arr.length; j++){
				if(key>arr[j]){
					key = arr[j];
					indexOfSmallest = j;
				}
			}
			arr[indexOfSmallest] = arr[i];
			arr[i] = key;
		}

		for(int i : arr){
			System.out.print(i+" ");
		}
		System.out.println();
	}	

}

Python 2.7.5

arr = [5,2,4,6,1,3]

for i in range(0,len(arr)-1):
    key = arr[i]
    indexOfSmallest = i
    for j in range(i+1,len(arr)):
        if key > arr[j]:
            key = arr[j]
            indexOfSmallest = j
    arr[indexOfSmallest] = arr[i]
    arr[i] = key

print arr

See you on the next post!

Insertion Sort

In this post, I feel like talking about the insertion sort.

In the aforementioned sort, we take an element, we are going to call this element the key. We take the key and compare it to the element in the left, if the element of the left is greater than the key, they exchange places, if they exchanged places then we compare the key to the element in the left (if there is one), if the element on the left is not greater than the key (or if there are no more elements in the left) we take the next element as the key. Rinse and repeat until we run out of elements. The first element we take as the key is the second element.

This algorithm is efficient for sorting a small number of elements.

Example gif from wikipedia

Insertion sort example from wikipedia

Insertion sort example from wikipedia

Pseudocode

let arr be an unsorted array of integers
    for i = 1 while i<arr.length i++
        key = arr[i]
        j = i -1
        while j>=0 and arr[j]>key
            arr[j+1] = arr[j]
            j--
        arr[j+1] = key

Implementations

C (Apple LLVM version 5.1 (clang-503.0.40), compiled with gcc -ansi)

#include<stdio.h>

int main()
{
	int arr[] = {5,2,4,6,1,3};
	int arrlength = sizeof(arr)/sizeof(arr[0]);
	for(int i=1; i<arrlength; i++)
	{
		int key = arr[i];
		int j = i - 1;
		while(j>=0 && arr[j]>key)
		{
			arr[j+1] = arr[j];
			j--;
		}
		arr[j+1] = key;
	}

	for(int k=0; k<arrlength; k++){
		printf("%d ",arr[k]);
	}
	printf("\n");
}

Java 1.7

public class InsertionSort{

	public static void main(String []args){
		int arr[] = new int[]{5,2,4,6,1,3};

		for(int i=1; i <  arr.length; i++){
			int key = arr[i];
			int j = i - 1;
			while(j>=0 && arr[j]>key){
				arr[j+1] = arr[j];
				j--;
			}
			arr[j+1] = key;
		}

		//let's print the sorted array

		for(int i : arr){
			System.out.print(i+" ");
		}
		System.out.println();
	}
}

Python 2.7.5

arr = [5,2,4,6,1,3]

for i in range(1,len(arr)):
    key = arr[i]
    j = i - 1
    while j>=0 and arr[j]>key:
        arr[j+1] = arr[j]
        j = j - 1
    arr[j+1] = key

print arr

Im currently reading Introduction to algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.

Tapity Tapper (My iOS Flappy Bird Clone using Sprite Kit): The Last One

You can find an index of this series here.

So we are going to wrap up this series with this post.

If you have tried to run the project on the iPad simulator or in an actual iPad, you may notice that all the objects are tiny, this is because the screen of the iPad is bigger, so we need to use bigger sprites.

The fix that I used for this, is quick and dirty.

Also now the “pipes” are randomized:

-(void)addObstacles{
float obstacleWidth = self.size.height/10.0;
float gap = (self.size.height/10.0)*4;
float minHeight = self.size.height/10.0;
float changeableSpace = self.size.height - gap - minHeight*2;
float pieceOfChangeableSpace = changeableSpace / 8 ;
float randomValue = arc4random()%(9);
float upperObstacleHeight =minHeight + randomValue*pieceOfChangeableSpace;
float lowerObstacleHeight =minHeight + (8-randomValue)*pieceOfChangeableSpace;

SKSpriteNode *upperObstacle = [SKSpriteNode spriteNodeWithColor:[UIColor greenColor] size:CGSizeMake(obstacleWidth, upperObstacleHeight)];

SKSpriteNode *lowerObstacle = [SKSpriteNode spriteNodeWithColor:[UIColor greenColor] size:CGSizeMake(obstacleWidth, lowerObstacleHeight)];

upperObstacle.position = CGPointMake(self.size.width+obstacleWidth/2, self.size.height-upperObstacle.size.height/2);

lowerObstacle.position = CGPointMake(self.size.width+obstacleWidth/2, lowerObstacle.size.height/2);

SKAction *moveObstacle = [SKAction moveToX:-obstacleWidth/2 duration:2.0];

[upperObstacle runAction:moveObstacle completion:^(void){
self.scoreLabel.text =[NSString stringWithFormat:@"%d", [self.scoreLabel.text integerValue]+1];
[upperObstacle removeFromParent];
}];
[lowerObstacle runAction:moveObstacle completion:^(void){
[lowerObstacle removeFromParent];
}];

//collision detection
upperObstacle.physicsBody = [SKPhysicsBody bodyWithRectangleOfSize:upperObstacle.size];
//we don't want this object to be animated by the physics engine
upperObstacle.physicsBody.dynamic = NO;
upperObstacle.physicsBody.categoryBitMask = JCColliderTypeObstacle;
//same with the lower obstacle
lowerObstacle.physicsBody = [SKPhysicsBody bodyWithRectangleOfSize:lowerObstacle.size];
lowerObstacle.physicsBody.dynamic = NO;
lowerObstacle.physicsBody.categoryBitMask = JCColliderTypeObstacle;
[self addChild:upperObstacle];
[self addChild:lowerObstacle];
}

And also in the snippet above you can see that we added a label to keep the score.

score

As always, you can find the complete code on Github.

Just so you know. . .

I will post the next and final post of Tapity Tapper over the next weekend (I promise) this week (June 16-22, I am so sorry for the delay ).

I also will update the JCInput later that week this month.

In order to prevent this post from being totally useless, I will leave a list of fun things to do:

Also if you happen to be one of the very few readers of this blog, tell me in the comments or in a tweet what do you want to see next. See you soon.

 

Tapity Tapper (My iOS Flappy Bird Clone using Sprite Kit): Game Over

You can find an index of this series here.

We added collision detection in the last post, but now we are going to add a message to let the player know that it’s game over, and a way to start again. We are also going to move some things around.

tap to play

First we add more properties to our interface of the scene:

@property SKAction *obstacleLoop;
@property BOOL gameOver;
@property UIAlertView *gameOverAlert;
@property SKLabelNode *startGameLabel;
  • obstacleLoop: The action that adds the moving obstacle every given time.
  • gameOver: A flag that will let us know if the game has finished.
  • gameOverAlert: This will be a pop up.
  • startGameLabel: A text label to tell the player to start the game.

Since the player can restart the game every time it finishes, we need a way to set the red rectangle to its original position.

-(void)setRectanglePositionAndAddToScene{
    self.rectangle.position = CGPointMake(60, self.size.height/2);
    [self addChild:self.rectangle];
}

We are going to move the initialization of the red rectangle and the obstacle loop to the initWithSize method. We also are going to add the initialization of the game over alert and the start game alert.

-(id)initWithSize:(CGSize)size {
    if (self = [super initWithSize:size]) {
        /* Setup your scene here */
        self.backgroundColor = [SKColor colorWithRed:0.15 green:0.15 blue:0.3 alpha:1.0];

        self.physicsBody = [SKPhysicsBody bodyWithEdgeLoopFromRect:CGRectMake(0, 0, self.size.width, self.size.height)];

        self.physicsWorld.contactDelegate = self;

        SKAction *callAddObstacles = [SKAction performSelector:@selector(addObstacles) onTarget:self];
        SKAction *wait = [SKAction waitForDuration:1.5];
        SKAction *waitThenAdd = [SKAction sequence:@[callAddObstacles,wait]];
        self.obstacleLoop = [SKAction repeatActionForever:waitThenAdd];

        self.gameOverAlert = [[UIAlertView alloc] initWithTitle:@"Game Over"
                                                   message:nil
                                                  delegate:nil
                                         cancelButtonTitle:@"OK"
                                         otherButtonTitles:nil];

        self.startGameLabel = [SKLabelNode labelNodeWithFontNamed:@"Chalkduster"];
        self.startGameLabel.text = @"Tap to play";
        self.startGameLabel.fontSize = 15;
        self.startGameLabel.position = CGPointMake(size.width/2, size.height/2);

        self.gameOver = NO;

        self.rectangle = [SKSpriteNode spriteNodeWithColor:[UIColor redColor] size:CGSizeMake(50, 50)];
        [self setRectanglePositionAndAddToScene];
        [self addChild:self.startGameLabel];
    }
    return self;
}

They make more sense there than in the touchesBegan method. Now we are going to modify the touchesBegan method.

-(void)touchesBegan:(NSSet *)touches withEvent:(UIEvent *)event {
    /* Called when a touch begins */
    if (!self.rectangle.physicsBody||self.gameOver) {
        if (!self.rectangle.physicsBody) {
            [self.startGameLabel removeFromParent];
            //initialize the physicsBody with the size of the rectangle
            self.rectangle.physicsBody = [SKPhysicsBody bodyWithRectangleOfSize:self.rectangle.size];
            //gravity is going to be simulated on this node
            self.rectangle.physicsBody.affectedByGravity = YES;
            self.rectangle.physicsBody.allowsRotation = NO;
            self.rectangle.physicsBody.mass = 0.5f;
            //collision detection
            self.rectangle.physicsBody.categoryBitMask = JCColliderTypeRectangle;
            self.rectangle.physicsBody.collisionBitMask = JCColliderTypeObstacle | JCColliderTypeRectangle;
            self.rectangle.physicsBody.contactTestBitMask = JCColliderTypeObstacle;
        }
        if (self.gameOver) {
            [self removeAllChildren];
            self.paused = NO;
            self.gameOver = NO;
            [self setRectanglePositionAndAddToScene];
        }
        [self.rectangle runAction:self.obstacleLoop withKey:@"obstacles"];
    }
    else{
        [self.rectangle.physicsBody applyImpulse:CGVectorMake(0.0f, 250.0f)];
    }

}
  • If we have set the physics body of the red rectangle, and it’s not game over, then we add impulse to the rectangle to make it jump.
  • If we haven’t set the physics body, then we remove the “Tap to play” label, and initialize the physics body of the red rectangle and set everything we need.
  • If the game is over, we remove every node from the scene (in this case, obstacles and rectangle), resume the scene (self.pause = NO), set gameOver to NO, and add the red rectangle to the scene again in its original position.
  • In both of the last two points, we also begin running the obstacle loop, with a key, so we can later stop the action.

Everything you may not understand of the logic of this, will be clarified in the didBeginContact method. We are adding this code:

        self.paused = YES;
        [self.rectangle removeActionForKey:@"obstacles"];
        self.gameOver = YES;
        [self.gameOverAlert show];
        [self addChild:self.startGameLabel];

First we pause the scene, then we remove the obstacle loop, set game over to YES,  display the game over alert and finally we show the “tap to play” label.

game over

The pop up, we are displaying which is an UIAlertView, it’s not part of Sprite Kit, but we can use  standard UIKit with Sprite Kit.

Run the project, when we dismiss the UIAlertView by tapping OK, we are going to see this:

start again

And if we tap, we start over.

As always, you can download the complete code from GitHub, see you next time.