Алгоритм сортировки вставок и пузырьковой сортировки против алгоритма быстрой сортировки
Я работаю над исследованием в классе, где я тестировал сортировку пузырьков и сортировку вставками, а также быструю сортировку. Я провел тест на случайных числах. Результаты показывают, что сортировка вставок выполняется быстрее, чем пузырьковая, а быстрая сортировка - самая медленная.
Итак, у меня есть рейтинг ниже по времени
сортировка вставок (самая быстрая)пузырьковая сортировка (вторая оценка)быстрая сортировка (самая медленная)Принимая во внимание, что вставка и пузырьковая сортировка имеют сложность 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;
}