0513 - K Sort 1

Cerința

Se dă un șir cu n elemente, numere naturale, numerotate începând cu 1 și un număr k. Considerăm k subșiruri ale șirului, astfel:

• primul subșir este format din elementele din șir numerotate cu 1, k+1, 2*k+1, …
• al doilea subșir este format din elementele din șir numerotate cu 2, k+2, 2*k+2, …
• …
• al k-lea subșir este format din elementele din șir numerotate cu k, 2*k, 3*k, …

Ordonați crescător fiecare dintre aceste subșiruri și afișați șirul obținut.

Date de intrare

Programul citește de la tastatură numerele n și k, iar apoi n numere naturale, reprezentând elementele șirului.

Date de ieșire

Programul va afișa pe ecran elementele șirului, separate prin exact un spațiu, după efectuarea operațiilor cerute.

Restricții și precizări

• 1 ≤ k < n ≤ 1000;
• cele n numere citite vor fi mai mici decât 1.000.000.000;

Exemplul 1

Intrare

11 3

7 5 4 3 1 6 8 9 11 10 2

Ieșire

3 1 4 7 2 6 8 5 11 10 9

Datele de intrare corespund restricțiilor impuse.

Exemplul 2

Intrare

0

0

Ieșire

Datele de intrare nu corespund restricțiilor impuse.

Rezolvare

#0513 - K Sort 1
def sortare_intercalata(n, k, a):
    # sortare intercalata
    for i in range(k):
        v = []
        p = 0
        for j in range(i, n, k):
            v.append(a[j])
            p += 1
        v.sort()
        p = 0
        for j in range(i, n, k):
            a[j] = v[p]
            p += 1
    return a

if __name__ == '__main__':
    # citirea numarului de elemente din vector si a vectorului
    n, k = map(int, input("Introduceti numarul de elemente si valoarea k: ").split())
    a = list(map(int, input("Introduceti elementele vectorului (separate prin spatiu): ").split()))

    # verificarea restrictiilor
    if 1 <= n <= 1000 and all(1 <= x <= 10**9 for x in a):
        a_sorted = sortare_intercalata(n, k, a)
        # afisarea vectorului sortat
        print("Datele de intrare corespund restricțiilor impuse.")
        for i in range(n):
            print(a_sorted[i], end=" ")
    else:
        print("Datele de intrare nu corespund restricțiilor impuse.")