ヒープソートっぽくグイグイとラベルを動かすiPhoneアプリのサンプルコードを描いてみます。
動かすとこんな感じです
サンプルコード
#import “ViewController.h”
@interface NSMutableArray(Heap)
@property NSUInteger heapSize;
@end
@implementation NSMutableArray(Heap)
@dynamic heapSize;
– (void)setHeapSize:(NSUInteger)heap
{
self[0] = @(heap);
}
– (NSUInteger)heapSize
{
return [self[0] integerValue];
}
@end
@interface ViewController ()
@property (nonatomic, strong) NSMutableArray *target;
@property (nonatomic, strong) NSMutableArray *animationArray;
@end
@implementation ViewController
– (void)viewDidLoad
{
[super viewDidLoad];
self.target = [@[@”heapsize”, @3, @5, @2, @1, @10, @8, @6, @11, @7] mutableCopy];
[self createViews];
UIButton *start = [UIButton buttonWithType:UIButtonTypeSystem];
[start setTitle:@”START” forState:UIControlStateNormal];
[start sizeToFit];
start.center = CGPointMake(160, 420);
[self.view addSubview:start];
[start addTarget:self action:@selector(startSort) forControlEvents:UIControlEventTouchUpInside];
}
– (void)createViews
{
for (int i=1; i<self.target.count; i++) {
float x = 35 * i – 30;
float y = 100;
UILabel *l = [[UILabel alloc] initWithFrame:CGRectMake(x, y, 30, 30)];
l.tag = i + 100;
l.text = [self.target[i] stringValue];
l.textAlignment = NSTextAlignmentCenter;
l.layer.borderColor = [UIColor brownColor].CGColor;
l.layer.borderWidth = 3;
[self.view addSubview:l];
int h = log2(i);
float x2 = (i – pow(2, h) + 1) * 300.0 / (pow(2, h+1) – pow(2, h) + 1) + 10;
float y2 = 200 + h * 50;
UILabel *l2 = [[UILabel alloc] initWithFrame:CGRectMake(0, 0, 30, 30)];
l2.tag = i + 10;
l2.textAlignment = NSTextAlignmentCenter;
l2.text = l.text;
l2.font = [UIFont boldSystemFontOfSize:18];
l2.textColor = [[UIColor whiteColor] colorWithAlphaComponent:0.8];
l2.center = CGPointMake(x2, y2);
l2.layer.cornerRadius = 15;
l2.layer.backgroundColor = [UIColor brownColor].CGColor;
[self.view addSubview:l2];
}
}
– (void)startSort
{
[self heapSort:self.target];
[self showAnimation];
}
– (NSUInteger)left:(NSUInteger)i
{
return 2 * i;
}
– (NSUInteger)right:(NSUInteger)i
{
return 2 * i + 1;
}
– (void)maxHeapify:(NSMutableArray*)a i:(NSUInteger)i
{
NSUInteger l = [self left:i];
NSUInteger r = [self right:i];
NSUInteger largest;
if (l < a.heapSize && [a[l] intValue] > [a[i] intValue])
largest = l;
else
largest = i;
if (r < a.heapSize && [a[r] intValue] > [a[largest] intValue])
largest = r;
if (largest != i) {
[self exchangeArray:a objectAtIndex:i withObjectAtIndex:largest];
[self maxHeapify:a i:largest];
}
}
– (void)buildMaxHeap:(NSMutableArray*)a
{
a.heapSize = a.count;
for (int i=a.count/2; i>0; i–) {
[self maxHeapify:a i:i];
}
}
– (void)heapSort:(NSMutableArray*)a
{
[self buildMaxHeap:a];
for (int i=a.count–1; i>1; i–) {
[self exchangeArray:a objectAtIndex:1 withObjectAtIndex:i];
a.heapSize = a.heapSize – 1;
[self maxHeapify:a i:1];
}
}
– (void)exchangeArray:(NSMutableArray*)a objectAtIndex:(NSUInteger)idx1 withObjectAtIndex:(NSUInteger)idx2
{
[a exchangeObjectAtIndex:idx1 withObjectAtIndex:idx2];
if (!self.animationArray) {
self.animationArray = [NSMutableArray array];
}
[self.animationArray addObject:@[@(idx1), @(idx2)]];
}
– (void)showAnimation
{
NSArray *idx = [self.animationArray lastObject];
NSInteger idx1 = [idx[0] integerValue];
NSInteger idx2 = [idx[1] integerValue];
UIView *v1 = [self.view viewWithTag:idx1 + 100];
UIView *v2 = [self.view viewWithTag:idx2 + 100];
UIView *v3 = [self.view viewWithTag:idx1 + 10];
UIView *v4 = [self.view viewWithTag:idx2 + 10];
[UIView animateWithDuration:0.8 animations:^{
CGPoint p1 = v1.center;
CGPoint p3 = v3.center;
v1.center = v2.center;
v2.center = p1;
v3.center = v4.center;
v4.center = p3;
} completion:^(BOOL finished) {
[self.animationArray removeLastObject];
if (self.animationArray.count > 0) {
[self showAnimation];
}
}];
}
@end