Jednym z najpopularniejszych algorytmów porządkowania jest sortowanie przez wstawianie.
W tym zadaniu odwołujemy się do zapisu algorytmu podanego poniżej:
Dane:
n – dodatnia liczba całkowita
A[1..n] – tablica zawierająca ciąg n liczb całkowitych x1, x2, …, xn, gdzie A[ i ] = xi
Wynik: tablica A zawierająca te same dane, ale uporządkowane niemalejąco, tzn. dla każdego i = 2, …, n, A[ i ] ≥ A[ i – 1]
Uwaga: przyjmij, że jeśli warunek ( j > 1) nie jest spełniony, to warunek (v < A[ j – 1]) nie jest już sprawdzany.
Na potrzeby tego zadania przyjmiemy, że przypisanie A[ j ] ← A[ j – 1] jest operacją dominującą.
W pliku dane4.txt zapisano ciąg x złożony z 2023 różnych liczb całkowitych x1, x2, …, x2023 z przedziału [1, 2023], po jednej liczbie w wierszu – w wierszu i-tym liczbę xi. Podaj takie i, dla którego liczba par (xi, xj) takich, że xi > xj oraz i > j jest największa.
cena_gazu.txt czestosc.txt dane1_3.txt dane1_4.txt dane2_3.txt dane2_4.txt dane3.txt dane4.txt dane6.txt dane6przyklad.txt dane8.txt gaz.txt pracownicy.txt rejestr_aktywnosci.txt szyfrogram.txt zamowienia.txt
W tym zadaniu odwołujemy się do zapisu algorytmu podanego poniżej:
Dane:
n – dodatnia liczba całkowita
A[1..n] – tablica zawierająca ciąg n liczb całkowitych x1, x2, …, xn, gdzie A[ i ] = xi
Wynik: tablica A zawierająca te same dane, ale uporządkowane niemalejąco, tzn. dla każdego i = 2, …, n, A[ i ] ≥ A[ i – 1]
Algorytm SortW:
dla i = 2, 3, …, n wykonaj:
v ← A[ i ]
j ← i
dopóki (j > 1) oraz (v < A[ j – 1]) wykonaj:
A[ j ] ← A[ j – 1]
j ← j - 1
A[ j ] ← v
Uwaga: przyjmij, że jeśli warunek ( j > 1) nie jest spełniony, to warunek (v < A[ j – 1]) nie jest już sprawdzany.
Na potrzeby tego zadania przyjmiemy, że przypisanie A[ j ] ← A[ j – 1] jest operacją dominującą.
W pliku dane4.txt zapisano ciąg x złożony z 2023 różnych liczb całkowitych x1, x2, …, x2023 z przedziału [1, 2023], po jednej liczbie w wierszu – w wierszu i-tym liczbę xi. Podaj takie i, dla którego liczba par (xi, xj) takich, że xi > xj oraz i > j jest największa.