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

<syntaxhighlight lang="python" line="1">

1. 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.")

</syntaxhighlight>