クイックソートを視覚的に、、、というiPhoneアプリのサンプルコードを描いてみます。
動かすとこんな感じです
サンプルコード
#import “ViewController.h”
@interface ViewController ()
@property int sceneCount;
@property (nonatomic, strong) NSMutableArray *animationBlocks;
@property (nonatomic, weak) UIView *start;
@property (nonatomic, weak) UIView *middle;
@property (nonatomic, weak) UIView *end;
@end
@implementation ViewController
– (void)viewDidLoad
{
[super viewDidLoad];
self.view.backgroundColor = [UIColor colorWithRed:0.5 green:0 blue:1.0 alpha:1.0];
self.animationBlocks = [NSMutableArray array];
int numbers[] = {2, 8, 7, 1, 3, 5, 6, 4};
int size = sizeof(numbers)/sizeof(int);
[self showNumberLabel:numbers size:size];
[self quicksortA:numbers p:0 r:size-1];
for (int i=0; i<3; i++) {
UIView *line = [[UIView alloc] init];
line.frame = CGRectMake(0, 0, 2, 40);
line.backgroundColor = [UIColor redColor];
[self.view addSubview:line];
if (i==0) {
self.start = line;
line.center = CGPointMake(CGRectGetMinX([self.view viewWithTag:1].frame), CGRectGetMidY([self.view viewWithTag:1].frame));
} else if (i==1) {
self.middle = line;
line.center = CGPointMake(CGRectGetMinX([self.view viewWithTag:1].frame), CGRectGetMidY([self.view viewWithTag:1].frame));
} else {
self.end = line;
line.center = CGPointMake(CGRectGetMinX([self.view viewWithTag:size].frame), CGRectGetMidY([self.view viewWithTag:size].frame));
}
}
}
– (void)touchesBegan:(NSSet *)touches withEvent:(UIEvent *)event
{
[self startAnimations];
}
– (void)showNumberLabel:(int *)number size:(int)size
{
for (int i=0; i<size; i++) {
UILabel *l = [[UILabel alloc] initWithFrame:CGRectMake(i * 29 + 30, 100, 30, 30)];
l.tag = i + 1;
l.text = [@(number[i]) stringValue];
l.textAlignment = NSTextAlignmentCenter;
l.textColor = [UIColor greenColor];
l.font = [UIFont boldSystemFontOfSize:20];
l.layer.borderWidth = 2;
l.layer.borderColor = [UIColor greenColor].CGColor;
[self.view addSubview:l];
}
}
-(void)quicksortA:(int *)A p:(int)p r:(int)r
{
if (p < r) {
// start — create animation block
__weak ViewController *weakSelf = self;
[self.animationBlocks addObject:
^{
weakSelf.start.center = CGPointMake(p * 29 + 30, 100);
weakSelf.middle.center = CGPointMake(p * 29 + 30, 100);
weakSelf.end.center = CGPointMake(r * 29 + 30, 100);
}];
// end — create animation block
int q = [self partitionA:A p:p r:r];
[self quicksortA:A p:p r:q – 1];
[self quicksortA:A p:q + 1 r:r];
}
}
– (int)partitionA:(int*)A p:(int)p r:(int)r
{
int x = A[r];
int i = p – 1;
for (int j=p; j < r; j++) {
// start — create animation block
__weak ViewController *weakSelf = self;
[self.animationBlocks addObject:
^{
weakSelf.middle.center = CGPointMake(j * 29 + 30, 100);
}];
// end — create animation block
if (A[j] <= x) {
i = i + 1;
[self.animationBlocks addObject:
^{
weakSelf.start.center = CGPointMake(i * 29 + 30, 100);
}];
[self swap:A idx1:i idx2:j];
}
}
[self swap:A idx1:i+1 idx2:r];
return i + 1;
}
– (void)swap:(int*)A idx1:(int)idx1 idx2:(int)idx2
{
if (idx1 != idx2) {
int buf = A[idx1];
A[idx1] = A[idx2];
A[idx2] = buf;
// start — create animation block
__weak ViewController *weakSelf = self;
[self.animationBlocks addObject:
^{
UIView *v1 = [weakSelf.view viewWithTag:idx1 + 1];
UIView *v2 = [weakSelf.view viewWithTag:idx2 + 1];
CGPoint p = v1.center;
v1.center = v2.center;
v2.center = p;
v1.tag = idx2 + 1;
v2.tag = idx1 + 1;
}];
// end — create animation block
}
}
– (void)startAnimations
{
for (id animation in self.animationBlocks) {
self.sceneCount ++;
float delay = self.sceneCount * 0.4;
dispatch_after(dispatch_time(DISPATCH_TIME_NOW, (int64_t)(delay * NSEC_PER_SEC)), dispatch_get_main_queue(), ^{
[UIView animateWithDuration:0.2 animations:animation];
});
}
}
@end