{"id":590,"date":"2014-12-31T12:57:48","date_gmt":"2014-12-31T11:57:48","guid":{"rendered":"http:\/\/www.valcon.it\/pascal\/?p=590"},"modified":"2015-07-03T13:20:10","modified_gmt":"2015-07-03T11:20:10","slug":"bubble-sort","status":"publish","type":"post","link":"https:\/\/www.valcon.it\/pascal\/bubble-sort\/","title":{"rendered":"Bubble Sort"},"content":{"rendered":"

Algoritmo molto diffuso perch\u00e9 intuitivo ma con prestazioni scadenti<\/em>.<\/p>\n

\"UnaUna passata<\/h3>\n

Una passata con ordinamenti di due elementi<\/a> su tutte le n-1<\/strong> coppie, all’interno di un array, provoca lo spostamento in alto<\/em> della bolla<\/em> pi\u00f9 grande.<\/p>\n

Sia<\/p>\n

V=(20, 15, 10, 3)<\/p>\n

alla fine della passata l’elemento pi\u00f9 grande 20<\/strong> si trova in ultima posizione<\/p>\n

V=(15, 10, 3, 20<\/strong>)<\/p>\n

For j:=1 To N-1 Do\r\n   If(V[j] > V[j+1]) Then\r\n      SCAMBIA(V[j], V[j+1]);<\/pre>\n
Bubble sort<\/h3>\n
N<\/strong> passate, sulle n-1<\/strong> coppie, ordinano sicuramente l’array<\/p>\n
Procedure BUBBLESORT(Var V: Vettore; N: Integer);\r\nVar\r\n   i, j: Integer;\r\nBegin\r\n   For i:=1 To N Do\r\n      For j:=1 To N-1 Do\r\n         If(V[j] > V[j+1]) Then\r\n            SCAMBIA(V[j], V[j+1]);\r\nEnd;<\/pre>\n
In realt\u00e0 sono necessarie al massimo N-1<\/strong> passate su N-i<\/strong> coppie (di ciascuna passata)<\/p>\n
Procedure BUBBLESORT(Var V: Vettore; N: Integer);\r\nVar\r\n   i, j: Integer;\r\nBegin\r\n   For i:=1 To N-1 Do\r\n      For j:=1 To N-i Do\r\n         If(V[j] > V[j+1]) Then\r\n            SCAMBIA(V[j], V[j+1]);\r\nEnd;<\/pre>\n
Osserva,,,<\/p>\n
\"Bubble<\/p>\n
Miglioramenti?<\/h3>\n
Nel caso in cui il vettore risulti ordinato dopo un certo numero di passate \u00e8 possibile interrompere l’esecuzione del While()\u00a0<\/strong>introducendo la variabile ANCORA<\/strong><\/p>\n
Procedure BUBBLESORT(Var V: Vettore; N: Integer);\r\nVar\r\n   ANCORA: Boolean;\r\n   i, j  : Integer;\r\nBegin\r\n   i:=1;\r\n   ANCORA:=True;\r\n   While(i < N) And (ANCORA) Do\r\n      Begin\r\n         ANCORA:=False;\r\n         For j:=1 To N-i Do\r\n            If(V[j] > V[j+1]) Then\r\n               Begin\r\n                  SCAMBIA(V[j], V[j+1]);\r\n                  ANCORA:=True;\r\n               End;\r\n         Inc(i);\r\n      End;\r\nEnd;<\/pre>\n
Il numero di passate dipende solo da ANCORA<\/strong><\/p>\n
Procedure BUBBLESORT(Var V: Vettore; N: Integer);\r\nVar\r\n   ANCORA: Boolean;\r\n   i, j  : Integer;\r\nBegin\r\n   i:=1;\r\n   ANCORA:=True;\r\n   While(ANCORA) Do\r\n      Begin\r\n         ANCORA:=False;\r\n         For j:=1 To N-i Do\r\n            If(V[j] > V[j+1]) Then\r\n               Begin\r\n                  SCAMBIA(V[j], V[j+1]);\r\n                  ANCORA:=True;\r\n               End;\r\n         Inc(i);\r\n      End;\r\nEnd;<\/pre>\n
Se la variabile ANCORA<\/strong> non interviene si ha una passata in pi\u00f9.<\/p>\n
Elimino la differenza N-i<\/strong><\/p>\n
Procedure BUBBLESORT(Var V: Vettore; N: Integer);\r\nVar\r\n   ANCORA      : Boolean;\r\n   UltimaCoppia,\r\n   j           : Integer;\r\nBegin\r\n   ANCORA:=True;\r\n   UltimaCoppia:=N-1;\r\n   While(Ancora) Do\r\n      Begin\r\n         ANCORA:=False;\r\n         For j:=1 To UltimaCoppia Do\r\n            If(V[j] > V[j+1]) Then\r\n               Begin\r\n                  SCAMBIA(V[j], V[j+1]);\r\n                  ANCORA:=True;\r\n               End;\r\n         Dec(UltimaCoppia);\r\n      End;\r\nEnd;<\/pre>\n
La lunghezza del vettore dipende da UltimoScambio<\/strong> piuttosto che da UltimaCoppia<\/strong><\/p>\n
Procedure BUBBLESORT(Var V: Vettore; N: Integer);\r\nVar\r\n   ANCORA       : Boolean;\r\n   UltimaCoppia , \r\n   UltimoScambio, \r\n   i            : Integer;\r\nBegin\r\n   ANCORA:=True;\r\n   UltimaCoppia:=N-1;\r\n   While(ANCORA) Do\r\n      Begin\r\n         ANCORA:=False;\r\n         UltimoScambio:=1;\r\n         For i:=1 To UltimaCoppia Do\r\n            If(V[i] > V[i+1]) Then\r\n               Begin\r\n                  SCAMBIA(V[i], V[i+1]);\r\n                  ANCORA:=True;\r\n                  UltimoScambio:=i;\r\n               End;\r\n         UltimaCoppia:=UltimoScambio-1;\r\n      End;\r\nEnd;<\/pre>\n
In questo modo le passate diventano pi\u00f9 corte.<\/p>\n
Il While…Do<\/strong> esterno diventa Repeat…Until<\/strong><\/p>\n
Procedure BUBBLESORT(Var V: Vettore; N: Integer);\r\nVar\r\n   UltimaCoppia , \r\n   UltimoScambio, \r\n   i            : Integer;\r\n   FINITO       : Boolean;\r\nBegin\r\n   UltimaCoppia:=N-1;\r\n   Repeat\r\n      FINITO:=True;\r\n      UltimoScambio:=1;\r\n      For i:=1 To UltimaCoppia Do\r\n         If(V[i] > V[i+1]) Then\r\n            Begin\r\n               SCAMBIA(V[i], V[i+1]);\r\n               FINITO:=False;\r\n               UltimoScambio:=i;\r\n            End;\r\n      UltimaCoppia:=UltimoScambio-1;\r\n   Until(FINITO);\r\nEnd;<\/pre>\n
Elimino la variabile FINITO<\/strong><\/p>\n
Procedure BUBBLESORT(Var V: Vettore; N: Integer);\r\nVar\r\n   UltimaCoppia ,\r\n   UltimoScambio,\r\n   i            : Integer;\r\nBegin\r\n   UltimaCoppia:=N-1;\r\n   Repeat\r\n      UltimoScambio:=1;\r\n      For i:=1 To UltimaCoppia Do\r\n         If(V[i] > V[i+1]) Then\r\n            Begin\r\n               SCAMBIA(V[i], V[i+1]);\r\n               UltimoScambio:=i;\r\n            End;\r\n      UltimaCoppia:=UltimoScambio-1;\r\n   Until(UltimoScambio = 1);\r\nEnd;<\/pre>\n\n
L’istruzione SCAMBIA()<\/tt> viene eseguita ogni volta che ha successo\u00a0il controllo dell’istruzione If(...) Then<\/tt>.
\nConsideriamo il caso pessimo, cio\u00e8 che succeda a ogni passo.
\nQuanti sono i controlli e le esecuzioni di SCAMBIA()<\/tt>?<\/p>\n
\n\n\n\n\n\n\n\n\n
i<\/em><\/td>\nj<\/em><\/td>\nTC<\/sub><\/em><\/td>\nTS<\/sub><\/em><\/td>\n<\/tr>\n
1<\/td>\n1…n-1<\/td>\nn-1<\/td>\nn-1<\/td>\n<\/tr>\n
2<\/td>\n1…n-2<\/td>\nn-2<\/td>\nn-2<\/td>\n<\/tr>\n
…<\/td>\n…<\/td>\n…<\/td>\n…<\/td>\n<\/tr>\n
n-2<\/td>\n1…(n-(n-2))
\n1…2<\/td>\n		2<\/td>\n2<\/td>\n<\/tr>\n
n-1<\/td>\n1…(n-(n-1))
\n1…1<\/td>\n		1<\/td>\n1<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n
Quindi<\/p>\n
TC<\/sub>(n)=TS<\/sub>(n)=(n-1)+(n-2)+...+1<\/tt>.<\/div>\n
Quanto vale la somma?
\nSappiamo che 1+2+...n=n(n+1)\/2<\/tt> e quindi<\/p>\n
T(n)=(n-1)n\/2=\u00bdn2<\/sup>-\u00bdn<\/tt>.<\/div>\n
La complessit\u00e0 in tempo asintotica dell’algoritmo di ordinamento Bubble Sort \u00e8 O(n2<\/sup>)<\/strong>, sia per il numero di confronti<\/strong> che per il numero di scambi<\/strong>.<\/p>\n
Nel caso ottimo<\/strong>, il vettore gi\u00e0 ordinato, il numero di scambi \u00e8 0<\/strong> ma rimane quadratico il numero di confronti.<\/p>\n","protected":false},"excerpt":{"rendered":"
Algoritmo molto diffuso perch\u00e9 intuitivo ma con prestazioni scadenti. Una passata Una passata con ordinamenti di due elementi su tutte le n-1 coppie, all’interno di un array, provoca lo spostamento in alto della bolla pi\u00f9 grande. Sia V=(20, 15, 10, 3) alla fine della passata l’elemento pi\u00f9 grande 20 si trova in ultima posizione V=(15, … Leggi tutto<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[10],"tags":[],"_links":{"self":[{"href":"https:\/\/www.valcon.it\/pascal\/wp-json\/wp\/v2\/posts\/590"}],"collection":[{"href":"https:\/\/www.valcon.it\/pascal\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.valcon.it\/pascal\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.valcon.it\/pascal\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.valcon.it\/pascal\/wp-json\/wp\/v2\/comments?post=590"}],"version-history":[{"count":9,"href":"https:\/\/www.valcon.it\/pascal\/wp-json\/wp\/v2\/posts\/590\/revisions"}],"predecessor-version":[{"id":5656,"href":"https:\/\/www.valcon.it\/pascal\/wp-json\/wp\/v2\/posts\/590\/revisions\/5656"}],"wp:attachment":[{"href":"https:\/\/www.valcon.it\/pascal\/wp-json\/wp\/v2\/media?parent=590"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.valcon.it\/pascal\/wp-json\/wp\/v2\/categories?post=590"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.valcon.it\/pascal\/wp-json\/wp\/v2\/tags?post=590"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}