algorytm Quick Sort i Insertion Sort

widowisko3 · Post autor: **widowisko3** » 7 wrz 2010, o 11:56

Mam takie 2 pytania odnośnie algorytmów sortowania.

1. Czy jest możliwe i jeśli tak to dla jakich danych, że algorytm Insertion Sort działa szybciej niż algorytm Quick Sort?

2. Dla jakich danych algorytm Quick Sort będzie miał taki sam koszt jak algorytm Insertion Sort i jaki to koszt?

Fingon · Post autor: **Fingon** » 7 wrz 2010, o 12:58

1. Jest to możliwe, jeśli dane są już posortowane, to insertion sort działa w \(\displaystyle{ \Theta (n)}\).
2. Dla posortowanych danych.