Ordenació

Algorismes

Un algorisme és 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.

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(n2): 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ó més 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.

Aquesta és la cerca segons el tipus 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:

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

Ordenació

Veure abans aquest vídeo.

Alguns algorismes senzills d'ordenació són:

• Inserció
• Selecció
• Bombolla

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(n2) ⇒ intercanviar contigus mentre hi hagi algun moviment
• selection sort - O(n2) ⇒ 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)

Veure aquest vídeo de com sonen diversos algorismes.

Activitat: implementa el selection sort.

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.