İçeriğe geç

Insertion sort kaydırma sayısı

Kolay#insertion-sort#stable-sort~15 dk

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

Hedef zaman
O(n²)
Hedef alan
O(n)

Kodda değil de fikirde mi takıldın? Insertion sort bunu anlatıyor.

Python 3Ctrl+Enter çalıştırır
Özel test case