Ordenació

Algorismes

Una especificació no ambigua de com resoldre una classe de problemes. Exemple: sortir de casa.

Especificació (mitjançant un diagrama)
No ambigua (llenguatge clar: plou/no plou)
Resoldre (hi ha un resultat clar: sortir)
Classe de problemes (no només un)

Encara no parlem de programes!

algorisme + dades ⇒ programes

Activitat: algorisme per trobar el nombre més gran d’una llista desordenada (sense codi)

Complexitat

La notació O(...) gran permet classificar els algorismes en funció dels requisits de temps o espai quan les dades d’entrada creixen. Descriu el pitjor escenari.

Exemples de complexitat

Exemple: un dels n alumnes de la classe ha amagat la meva cartera

O(1): sé qui és l’alumne que ha amagat la cartera ⇒ li pregunto

O(n): només un alumne, que ha amagat la cartera, sap on és ⇒ he d’anar un a un preguntant

O(log n): tots els alumnes saben qui ha amagat la cartera, però només m’ho diran si endevino el nom ⇒ vaig dividint la classe i pregunto a tots si és a la dreta o a la esquerra

O(n²): a tota la classe, només un alumne sap a quina taula és la cartera ⇒ pregunto a cada alumne i li pregunto per la resta d’alumnes

Activitat: quina és la complexitat de l’algorisme per trobar el nombre més gran d’una llista desordenada? I si fos una llista ordenada?

Estructures de dades

És una forma d'organitzar i emmagatzemar dades per que que es puguin accedir i (opcionalment) modificar eficientment

quines operacions (queries) tenim? ⇒ quina estructura utilitzar

Operació habitual: trobar un registre que tingui un camp igual a un cert valor

Alguns tipus de dades:

primitius: booleans, nombres sencers i de coma flotant, caràcters, etc.
compostos: arrays (ordenats i desordenats)
abstractes: llistes (ordenades i desordenades), col·leccions, arrays associatius, conjunts, piles, cues, arbres, grafs, etc.

Cerca a estructures de dades

Cerca binària

Activitat

implementa un mètode que crei un array de N sencers, on N és un paràmetre. Utilitza new Random().nextInt()
Ordena'l amb Arrays.sort()
Dissenya l'algorisme de cerca binària per trobar la posició un nombre, si existeix

Anàlisi

Mètode iteratiu. Considera els conceptes en negreta:

Repetir, mentre no es trobi i quedin elements per buscar:

Es calcula la posició de l’element del mig.
Es compara el nombre buscat amb el contingut del mig
- Si és menor, buscar a partir del mig
- Si és major, buscar fins al mig
- Si és igual, l’hem trobat!

Reflexiona:

Quines variables necessitaràs?
Quants cops es repeteix cada bucle?
Quines conseqüències té cada acció de l’algorisme.

Ordenació

Veure vídeo:

https://youtu.be/30WcPnvfiKE?t=42s

Alguns algorismes senzills d'ordenació:

Inserció
Selecció
Bombolla

Activitats d'ordenar

Reflexió: com podem ordenar un array?

Activitat: com faries una ordenació manualment? Descriu el teu algorisme perquè algú el pugui implementar en codi (taller).

Alguns algorismes coneguts:

bubble sort - O(n²) ⇒ intercanviar contigus mentre hi hagi algun moviment
selection sort - O(n²) ⇒ per cada ítem, busquem la seva posició i el movem
merge sort - O(n log n) ⇒ dividim l’array en meitats, les ordenem i les barregem (té solució recursiva)

Com sonen diversos algorismes:

https://www.youtube.com/watch?v=t8g-iYGHpEA

Activitat: implementa el selection sort.

Ordenació per selecció: anàlisi

Mètode iteratiu. Considera els conceptes en negreta:

Repetir, mentre hi hagi elements per ordenar:

Es busca la posició del nombre més gran.
Es compara amb el nombre a la darrera posició.
- Si és més gran, s’intercanvien.
- Si no, no es fa res
Es repeteix, ignorant el darrer element.

Reflexiona:

Quines variables necessitaràs?
Quants cops es repeteix cada bucle?
Quines conseqüències té cada acció de l’algorisme.

Page updated

Report abuse