Takmicenje iz programiranja 2018 - Okruzno - Pripreme - Cas 01 - Algoritmi za sortiranje elemenata niza

Dragi takmičari,

Danas smo u učionici i kabinetu nešto detaljnije objašnjavali uglavnom najjednostavniji algoritam za sortiranje nizova, a kroz te primere i sledeće:

• Najjednostavniji (i najsporiji) algoritam za sortiranje elemenata niza metodom Selection sort (https://youtu.be/y3hf_dU9mlE).
• Pristupanje elementima niza u obrnutom redosledu (n+1-i) - Osnovna tehnika za ispitivanje da li je niz palindrom, na primer, ili za rastavljanje broja na cifre i sl.
• Potprogram za zamenu vrednosti 2 promenljive (switch).
• Učitavanje i prikazivanje vrednosti elemenata niza (read/readln, write).
• Ugnježdene brojačke cikluse (spoljna-sporija i unutrašnja-brža petlja) - bitno i za matrice.
• Složenost algoritma - brzina rada - koliko ima operacija ako je N 1000 ili 10 hiljada - Složenost algoritma N*N (n na kvadrat).
• Prekidne tačke i praćenje vrednosti promenljivih u FlowGorithm-u, konzolnoj aplikaciji u Lazarus-u i Free Pascal-u.
• Metoda sortiranja Bubble sort (mehur) - uvođenje nove promenljive (zastavice) i ciklusa sa uslovom (kombinacija cikusa sa uslovom kao spoljne i brojačkog ciklusa kao unutrašnje petlje) - Složenost algoritma je mnogo manja od n*n (ali je i veća od n).
• Samo smo napomenuli da je jedan od najbržih metoda za sortiranje elemenata niza Quick Sort:
  https://www.toptal.com/developers/sorting-algorithms

Tokom današnjeg rada, ponovo smo pregledali sledeće materijale:

 

1. Na NasaSkola.edu.rs/moodle u okviru poglavlja 9.1. Nizovi:

• Jednodimenzionalni nizovi - Stevan Spasić - Nebojša Lazarević
• Nizovi
• Низ (структура података)
• Zadaci za vežbanje aplikacija za rad sa nizovima
• Nizovi – Rešeni zadaci
• Nizovi – Rešeni zadaci 2
• Сортирање - Алгоритми за сортирање низа
• Сортирање селекцијом
• Algoritam za sortiranje niza metodom Selection sort - Jednostavan primer
• Select-sort
• Sortiranje mehurom
• Bubble sort
• Quick-sort

2. Na Vikipediji:

• https://sr.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%B0%D1%9A%D0%B5_%D1%81%D0%B5%D0%BB%D0%B5%D0%BA%D1%86%D0%B8%D1%98%D0%BE%D0%BC
• https://en.wikipedia.org/wiki/Bubble_sort

3. Na petlja.org:

• https://petlja.org/BubbleBee/r/Lectures/osnovni-algoritmi-sortiranja
• https://petlja.org/BubbleBee/r/problemi/Zbirka/ispis_u_obratnom_redosledu

4. Na Free Pascal Wiki:

• http://wiki.freepascal.org/Bubble_sort

Pozdrav,
Dragan Ilić

 

 

----- Original Message -----

From: Dragan Ilic

Sent: Monday, January 15, 2018 11:16 AM

Subject: Algoritam za sortiranje niza metodom Selection sort - Jednostavan primer

Dragi takmičari,

 

Pre nekoliko dana sam vam poslao algoritam za sortiranje niza metodom selekcije (najjednostavniji ali i najsporiji algoritam). Kako bi bolje razumeli brže, ali složenije algoritme, neophodno je da dobro razumemo najpre jednostavne (sporije), te vam zato šaljem algoritamsko rešenje sa prekidnom tačkom i test primerom, kako bi korak po korak, svako od vas na svom računaru testirao algoritam i pratio trenutne vrednosti elemenata.

 

Detaljnije na:

• Algoritam za sortiranje niza metodom Selection sort - Jednostavan primer

Pozdrav,

Dragan Ilić