DAA - Sıralamayı Birleştir
Bu bölümde, birleştirme sıralamasını tartışacağız ve karmaşıklığını analiz edeceğiz.
Sorun bildirimi
Bir sayılar listesini sıralama problemi, hemen bir böl ve yönet stratejisine dönüşür: listeyi iki yarıya bölün, her bir yarıyı yinelemeli olarak sıralayın ve sonra sıralanan iki alt listeyi birleştirin.
Çözüm
Bu algoritmada, sayılar bir dizide saklanır numbers[]. Buraya,p ve q bir alt dizinin başlangıç ve bitiş dizinini temsil eder.
Algorithm: Merge-Sort (numbers[], p, r)
if p < r then
q = ⌊(p + r) / 2⌋
Merge-Sort (numbers[], p, q)
Merge-Sort (numbers[], q + 1, r)
Merge (numbers[], p, q, r)Function: Merge (numbers[], p, q, r)
n1 = q – p + 1
n2 = r – q
declare leftnums[1…n1 + 1] and rightnums[1…n2 + 1] temporary arrays
for i = 1 to n1
leftnums[i] = numbers[p + i - 1]
for j = 1 to n2
rightnums[j] = numbers[q+ j]
leftnums[n1 + 1] = ∞
rightnums[n2 + 1] = ∞
i = 1
j = 1
for k = p to r
if leftnums[i] ≤ rightnums[j]
numbers[k] = leftnums[i]
i = i + 1
else
numbers[k] = rightnums[j]
j = j + 1Analiz
Birleştirme-Sıralama işleminin çalışma süresini şöyle düşünelim: T(n). Bu nedenle
$ T (n) = \ begin {case} c & if \: n \ leqslant 1 \\ 2 \: x \: T (\ frac {n} {2}) + d \: x \: n & aksi \ son {case} $ burada c ve d sabitler
Bu nedenle, bu tekrarlama ilişkisini kullanarak,
$$ T (n) = 2 ^ i T (\ frac {n} {2 ^ i}) + idn $$
$ İ = log \: n, \: T (n) = 2 ^ {log \: n} T (\ frac {n} {2 ^ {log \: n}}) + log \: ndn $
$ = \: cn + dnlog \: n $
Bu nedenle, $ T (n) = O (n \: log \: n) $
Misal
Aşağıdaki örnekte, Merge-Sort algoritmasını adım adım gösterdik. İlk olarak, her yineleme dizisi, alt dizi yalnızca bir öğe içerene kadar iki alt diziye bölünür. Bu alt diziler daha fazla bölünemediğinde, birleştirme işlemleri gerçekleştirilir.
