マージソートと挿入ソートにかかる時間の比較をグラフで表示するiPhoneアプリのサンプルコードを描いてみます。
動かすとこんな感じです
サンプルコード
#import “ViewController.h”
@interface ViewController ()
@property (nonatomic, weak) UIView *plotArea;
@end
@implementation ViewController
– (void)viewDidLoad
{
[super viewDidLoad];
[self createPlotArea];
[self createStartButton];
[self createLabels];
}
– (void)createPlotArea
{
UIView *v = [[UIView alloc] initWithFrame:CGRectMake(10, 50, 300, 300)];
v.layer.borderColor = [UIColor greenColor].CGColor;
v.layer.borderWidth = 1;
[self.view addSubview:v];
self.plotArea = v;
}
– (void)plot:(float)time n:(int)n color:(UIColor*)color
{
UIView *l = [[UIView alloc] initWithFrame:CGRectMake(n * 0.02, 280 – time * 10, 4, 4)];
l.backgroundColor = color;
[self.plotArea addSubview:l];
}
– (void)createStartButton
{
UIButton *startBtn = [UIButton buttonWithType:UIButtonTypeSystem];
[startBtn setTitle:@”Strat” forState:UIControlStateNormal];
[startBtn sizeToFit];
startBtn.center = CGPointMake(CGRectGetMidX(self.view.frame), 430);
[self.view addSubview:startBtn];
[startBtn addTarget:self action:@selector(start) forControlEvents:UIControlEventTouchUpInside];
}
– (void)createLabels
{
UILabel *mergeLabel = [[UILabel alloc] initWithFrame:CGRectMake(210,80,100,20)];
mergeLabel.text = @”■ merge”;
mergeLabel.textColor = [UIColor purpleColor];
[self.view addSubview:mergeLabel];
UILabel *insertionLabel = [[UILabel alloc] initWithFrame:CGRectMake(210,100,100,20)];
insertionLabel.text = @”■ insertion”;
insertionLabel.textColor = [UIColor redColor];
[self.view addSubview:insertionLabel];
for (int i=0; i<5; i++) {
float x = i * 50;
float y = 380;
UILabel *mark = [[UILabel alloc] initWithFrame:CGRectMake(x, y, 100, 20)];
mark.text = [NSString stringWithFormat:@”n = %d”, i * 3000];
mark.transform = CGAffineTransformMakeRotation(M_PI * 0.3);
[self.view addSubview:mark];
}
for (int i=1; i<5; i++) {
float x = 4;
float y = 270 – i * 40;
// y:10pt -> 1sec
UILabel *tmark = [[UILabel alloc] initWithFrame:CGRectMake(x, y, 100, 20)];
tmark.font = [UIFont systemFontOfSize:12];
tmark.text = [NSString stringWithFormat:@”t=%d(s)”, i * 4];
[self.plotArea addSubview:tmark];
}
}
– (NSMutableArray*)generateHugeArray:(int)size
{
NSMutableArray *arr = [NSMutableArray arrayWithCapacity:size];
for (int i=0; i<size; i++) {
[arr addObject:@(arc4random()%10)];
}
return arr;
}
– (void)start
{
for (int i=100; i<15000; i+=1000) {
NSMutableArray *arr = [self generateHugeArray:i];
NSMutableArray *a1 = [arr mutableCopy];
NSMutableArray *a2 = [arr mutableCopy];
// insertion sort
dispatch_async(dispatch_get_global_queue( DISPATCH_QUEUE_PRIORITY_DEFAULT, 0), ^(void){
NSDate *start1 = [NSDate new];
[self insertionSort:a1];
dispatch_async(dispatch_get_main_queue(), ^(void){
[self plot:-[start1 timeIntervalSinceNow] n:i color:[UIColor redColor]];
});
});
// merge sort
dispatch_async(dispatch_get_global_queue( DISPATCH_QUEUE_PRIORITY_DEFAULT, 0), ^(void){
NSDate *start2 = [NSDate new];
[self mergeSort:a2];
dispatch_async(dispatch_get_main_queue(), ^(void){
[self plot:-[start2 timeIntervalSinceNow] n:i color:[UIColor purpleColor]];
});
});
}
}
#pragma mark – insertion sort
– (void)insertionSort:(NSMutableArray*)arr
{
for (int j=1; j<arr.count; j++) {
id key = arr[j];
int i = j-1;
while (i >= 0 && [arr[i] intValue] > [key intValue]) {
arr[i+1] = arr[i];
i–;
}
arr[i + 1] = key;
}
}
#pragma mark – merge sort
– (void)mergeSort:(NSMutableArray*)arr
{
[self mergeSort:arr indexP:0 indexR:arr.count–1];
}
– (void)mergeSort:(NSMutableArray *)a indexP:(int)p indexR:(int)r
{
if (p < r) {
int q = (p + r) / 2;
[self mergeSort:a indexP:p indexR:q];
[self mergeSort:a indexP:q+1 indexR:r];
[self mergeSort:a indexP:p indexQ:q indexR:r];
}
}
– (void)mergeSort:(NSMutableArray *)a indexP:(int)p indexQ:(int)q indexR:(int)r
{
int n1 = q – p + 1;
int n2 = r – q;
int L[n1 + 1];
int R[n2 + 1];
for (int i=0; i<n1; i++)
L[i] = [a[p + i] intValue];
for (int j=0; j<n2; j++)
R[j] = [a[q + j + 1] intValue];
L[n1] = HUGE_VAL;
R[n2] = HUGE_VAL;
int i=0;
int j=0;
for (int k=p; k<=r; k++) {
if (L[i] <= R[j]) {
a[k] = @(L[i]);
i++;
} else {
a[k] = @(R[j]);
j++;
}
}
}
@end