Insertion sort kaydırma sayısı
Görev tanımı
Problem
Insertion sort her yeni değeri, sıralı kısımdaki her büyük değeri bir konum sağa kaydırarak yerleştirir. Bir sayı listesi verildiğinde, insertion sort onu artan sıraya dizerken kaç tek konumluk kaydırma yaptığını döndür. Eşit değerler asla birbirinin yanından kaymaz ve girdi listesi değiştirilmemeli.
Örnekler
Input: nums = [3, 1, 2]
Output: 2
Neden: 1'i yerleştirmek 3'ü bir kez kaydırır, sonra 2'yi yerleştirmek 3'ü bir kez daha kaydırır
Input: nums = [5, 4, 3, 2, 1]
Output: 10
Neden: her yeni değer zaten yerleştirilmiş her değeri kaydırır
Input: nums = [2, 2, 2]
Output: 0
Neden: edge case: eşit değerler oldukları yerde kalır
İpuçları
0 / 3
Bir formüle ihtiyacın yok. Soru algoritmanın ne yaptığıyla ilgili; bırak algoritma yapsın ve izle.
Listenin bir kopyası üzerinde çalış ve onun üzerinde insertion sort çalıştır; bir değeri bir konum sağa taşıyan satırın yanında bir sayaç tut.
İkinciden itibaren her indeks için değerini tut ve solundaki değer ondan büyük olduğu sürece (eşitken değil) o değeri sağa kaydır ve sayaca bir ekle. Tutulan değeri boşluğa bırak. Sondaki sayaç cevaptır.
- Hedef zaman
- O(n²)
- Hedef alan
- O(n)
Çözüm
Bir kopya üzerinde insertion sort çalıştırıp iç döngüsünün içinde saymak soruyu tam olarak cevaplar, çünkü her kaydırma o döngü gövdesinin bir çalışmasıdır. Karşılaştırma büyük-eşit değil, büyüktür olmalı; eşit değerlerin kaymasını engelleyen ve sıralamayı kararlı (stable) tutan bu. Her kaydırma yanlış sırada görünen bir değer çiftini de düzeltir; ters çevrilmiş bir listenin en pahalısı olmasının sebebi bu. En kötü durumda zaman O(n²), zaten sıralı bir listede O(n); kopya için alan O(n).
def count_shifts(nums):
a = list(nums) # sort a copy, leave the input alone
shifts = 0
for i in range(1, len(a)):
cur, j = a[i], i - 1
while j >= 0 and a[j] > cur: # only strictly larger values make room
a[j + 1] = a[j]
shifts += 1
j -= 1
a[j + 1] = cur # drop the held value into the gap
return shifts
print(count_shifts([3, 1, 2])) # -> 2
print(count_shifts([5, 4, 3, 2, 1])) # -> 10
print(count_shifts([2, 2, 2])) # -> 0Kodda değil de fikirde mi takıldın? Insertion sort bunu anlatıyor.