Bubble Sort Algorithm Visualization in Cocoa, Objective C

In the tutorial we will create a sample application that creates a visualization for each step of a sorting algorithm, The sorting algorithm chosen here for visualization is bubblesort as the focus is primarily on creating a visualization

In each iteration we will take a snapshot of the data and render it using a Column Chart.

The visualization depiction suggests, when two numbers are being compared, they will be highlighted in red, if the condition is satisfied (greater or less) the number is swapped and a successful swap is highlighted as a green column. All other numbers are highlighted in red.

Click on the below video to see the BubbleSort Algorithm Visualization before proceeding to the code

Step 1: Create a new cocoa application using XCode

Step 2: Modify the MainMenu.xib by adding two custom views from the library. (one custom view will be used for showing the as is/ unsorted data representation. The second view would be used to render the visualization at run time while the sorting is happening.

Step 3: AppDelegate Class Implementation

//
//  KSAppDelegate.h
//  BubbleSortAlgorithmVisualization
//
//  Created by Debasis Das on 7/30/14.
//  Copyright (c) 2014 Knowstack. All rights reserved.
//

#import <Cocoa/Cocoa.h>
@interface KSAppDelegate : NSObject 
@property (assign) IBOutlet NSWindow *window;
@property (assign) IBOutlet NSView *placeholderView1; //View used to render the unsorted data
@property (assign) IBOutlet NSView *placeholderView2; //View will be used to render the data snapshot after each operation
@end

//
//  KSAppDelegate.m
//  BubbleSortAlgorithmVisualization
//
//  Created by Debasis Das on 7/30/14.
//  Copyright (c) 2014 Knowstack. All rights reserved.
//

#import "KSAppDelegate.h"
#import "KSGraphView.h"

@implementation KSAppDelegate

- (void)applicationDidFinishLaunching:(NSNotification *)aNotification
{
    NSArray *dArray =@[@101,@201,@301,@121,@11,@153,@21,@14,@32,@76,@89,@87,@65,@78,@90,@80,@123,@34,@39];
    NSMutableArray *dataArray = [NSMutableArray arrayWithArray:dArray];

    //Create a Graph View instance to render the as is data
    KSGraphView *gv = [[KSGraphView alloc] initWithFrame:[self.placeholderView1 bounds]];
    [gv setDataArray:dataArray];
    [self.placeholderView1 addSubview:gv];
}
//The following method is bound to the "Bubble Sort" button's action
-(IBAction)doBubbleSort:(id)sender
{
        NSOperationQueue *operationQueueOne = [NSOperationQueue new];
        NSInvocationOperation *operation1 = [[NSInvocationOperation alloc] initWithTarget:self selector:@selector(sortByBubble) object:nil];
        [operationQueueOne addOperation:operation1];

}

-(void)sortByBubble
{
    NSArray *dArray =@[@101,@201,@301,@121,@11,@153,@21,@14,@32,@76,@89,@87,@65,@78,@90,@80,@123,@34,@39];
    NSMutableArray *dataArray = [NSMutableArray arrayWithArray:dArray];
    NSLog(@"Before Sorting dataArray %@",dataArray);

    long count = dataArray.count;
    int i;
    bool swapped = TRUE;
    while (swapped)
    {
        swapped = FALSE;
        for (i=1; i<count;i++)         
        {
             if ([dataArray objectAtIndex:(i-1)] > [dataArray objectAtIndex:i])
            {
                [dataArray exchangeObjectAtIndex:(i-1) withObjectAtIndex:i];
                swapped = TRUE;
                
                //Each iteration of the sort is being rendered in a graph view to see the effect
                [self performSelectorOnMainThread:@selector(loadGraph:)
                                                withObject:[NSMutableDictionary dictionaryWithObjectsAndKeys:
                                                           [NSNumber numberWithInt:i],@"colIndex",
                                                           dataArray,@"dataArray", nil]
                                             waitUntilDone:YES];
                usleep(200000); // Introduce a sleep so as to see the sorting happening at real time.
                // Without the sleep the sorting will happen too fast to observe
            }
        }
    }
        NSLog(@"After Sorting dataArray %@",dataArray);
}

-(void)loadGraph:(NSMutableDictionary *)data
{
    //Clean Up the Placeholder before each rendering
    for (NSView *view in [self.placeholderView2 subviews])
    {
        [view removeFromSuperview];
    }
    KSGraphView *gv = [[KSGraphView alloc] initWithFrame:[self.placeholderView2 bounds]];
    [gv setDataArray:[data objectForKey:@"dataArray"]];
    [gv setColIndex:[[data objectForKey:@"colIndex"] intValue]];
    [self.placeholderView2 addSubview:gv];
}
@end

Step 4: GraphView Class Implementation

//
//  KSGraphView.h
//  BubbleSortAlgorithmVisualization
//
//  Created by Debasis Das on 7/30/14.
//  Copyright (c) 2014 Knowstack. All rights reserved.
//

#import <Cocoa/Cocoa.h>

@interface KSGraphView : NSView
{

}
@property (assign) int colIndex;
@property (nonatomic, retain) NSMutableArray *dataArray;
@end

//
//  KSGraphView.m
//  BubbleSortAlgorithmVisualization
//
//  Created by Debasis Das on 7/30/14.
//  Copyright (c) 2014 Knowstack. All rights reserved.
//

#import "KSGraphView.h"

@implementation KSGraphView

- (id)initWithFrame:(NSRect)frame
{
    self = [super initWithFrame:frame];
    if (self) {
        // Initialization code here.
    }
    return self;
}

-(NSDictionary *)styleDictionary
{
    NSDictionary *styleDict = @{NSFontAttributeName: [NSFont systemFontOfSize:11.0],
                               NSForegroundColorAttributeName: [NSColor lightGrayColor]};
    return styleDict;
}

- (void)drawRect:(NSRect)dirtyRect
{
    [super drawRect:dirtyRect];
    [NSGraphicsContext saveGraphicsState];
    [[NSColor blackColor] setFill];
    [[NSBezierPath bezierPathWithRoundedRect:[self bounds] xRadius:0.0 yRadius:0.0] fill];
    [[NSColor whiteColor] set];
    int max = [[self.dataArray valueForKeyPath:@"@max.intValue"] intValue];
    float vRatio = (dirtyRect.size.height - 20)/max;
    for (NSNumber *num in self.dataArray)
    {
        if ([self.dataArray indexOfObject:num] == self.colIndex -1)
        {
            [[NSColor greenColor] set];
        }
        else if (([self.dataArray indexOfObject:num] == self.colIndex)||([self.dataArray indexOfObject:num] == self.colIndex + 1))
        {
            [[NSColor redColor] set];
        }
        else
        {
            [[NSColor whiteColor] set];
        }
        [[NSBezierPath bezierPathWithRect:NSMakeRect([self.dataArray indexOfObject:num] * 20 + 10 , 5, 5, [num floatValue]* vRatio)] fill];
        NSString *str = [NSString stringWithFormat:@"%d",[num intValue]];
        [str drawAtPoint:NSMakePoint([self.dataArray indexOfObject:num] * 20 + 5 , [num floatValue]* vRatio + 2 ) withAttributes:[self styleDictionary]];
    }
    [NSGraphicsContext restoreGraphicsState];
}

@end

Output

On Clicking the Sort Button – Final Output

Created By: Debasis Das