私はバブルソートと挿入ソートとクイックソートをテストしたクラスで研究に取り組んでおり、乱数のテストを行いました。結果は、挿入ソートがバブル ソートよりも速く、クイック ソートが最も遅いことを示しています。
だから私は時間の面で以下のランキングを持っています
- 挿入ソート（最速）
- バブル ソート (2 番目のスコア)
- クイックソート (最も遅い)
挿入とバブル ソートの複雑さは O(n2) ですが、クイック ソート O(n log n) と O (n log n) の方が高速であることを考慮してください !!!
誰か説明を教えてくれませんか?
ありがとう
(NSMutableArray *)quickSort:(NSMutableArray *)a
{
// Log the contents of the incoming array
NSLog(@"%@", a);
// Create two temporary storage lists
NSMutableArray *listOne = [[[NSMutableArray alloc]
initWithCapacity:[a count]] autorelease];
NSMutableArray *listTwo = [[[NSMutableArray alloc]
initWithCapacity:[a count]] autorelease];
int pivot = 4;
// Divide the incoming array at the pivot
for (int i = 0; i < [a count]; i++)
{
if ([[a objectAtIndex:i] intValue] < pivot)
{
[listOne addObject:[a objectAtIndex:i]];
}
else if ([[a objectAtIndex:i] intValue] > pivot)
{
[listTwo addObject:[a objectAtIndex:i]];
}
}
// Sort each of the lesser and greater lists using a bubble sort
listOne = [self bubbleSort:listOne];
listTwo = [self bubbleSort:listTwo];
// Merge pivot onto lesser list
listOne addObject:[[NSNumber alloc] initWithInt:pivot]];
// Merge greater list onto lesser list
for (int i = 0; i < [listTwo count]; i++)
{
[listOne addObject:[listTwo objectAtIndex:i]];
}
// Log the contents of the outgoing array
NSLog(@"%@", listOne);
// Return array
return listOne;
}