-
Notifications
You must be signed in to change notification settings - Fork 0
/
guia08.txt
472 lines (420 loc) · 25 KB
/
guia08.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
1.
Selection sort Θ(n**2) (da igual el caso, la complejidad siempre es la misma)
Insertion sort Θ(n**2) (es el peor caso)
Merge sort Θ(n*log(n)) (da igual el caso)
Quick sort Θ(n*log(n)) (depende de la elección de pivote; usando el elemento del medio como pivote como vimos en teórica, en pasos sucesivos siempre se divide al array en 2)
Heap sort Θ(n*log(n)) (da igual el caso)
Bucket sort, Counting sort, Radix sort Θ(n) (cuando aplicables, da igual el caso)
2.
Sería beneficioso usar un algoritmo que se beneficie de tener una primer parte de la secuencia preordenada. Un ejemplo visto en clase es insertion sort.
3.
Para las complejidades dadas se asume que el tipo T tiene O(comparacion) = O(copia) = O(1)
algoritmo k_minimos(in arr: Array<T>, in k: int, out res: Array<T>): // T comparable, requiere 0 <= k <= n
crear array de tipo T y dimensión k res
para cada i = 0..k-1 inclusive:
buscar el mínimo y máximo del array en una única pasada, registrando sus valores y también la pos. del máximo // O(n), requiere recorrer el array una única vez
asignar el minimo a res[i] // O(1)
asignar maximo+1 a array[pos_maximo] // O(1)
// el ciclo es O(k*n)
devolver res // O(1)
// el algoritmo completo es O(k*n)
Como el algoritmo es O(k*n) y el mínimo teórico de complejidad de ordenamiento sin información a priori es O(n*log(n)),
y como copiar los primeros k elementos de un array preordenado sería O(k) con k <= n,
sería conveniente preordenar el array si k > log(n).
4.
algoritmo merge_preordered_subarrays_sort(in conjarr: Array<Array<int>>, out res: Array<int>):
si conjarr.longitud() == 1: // O(1)
devolver conjarr[0] // O(1)
si no:
devolver merge(merge_preordered_subarrays_sort(primera_mitad(conjarr)),
merge_preordered_subarrays_sort(segunda_mitad(conjArr))) // O(t), recursión!
Cada merge es de complejidad lineal igual a la suma de las longitudes de los subarrays mergeados,
que eventualmente puede ser acotada por la cantidad total de elementos t.
Como en cada llamado se divide a conjarr en 2, se pueden realizar a lo sumo en el orden de log(n) llamados, siendo n la longitud original de conjarr.
Entonces la complejidad del algoritmo merge_preordered_subarrays_sort es O(t*log(n)).
5.
El algoritmo propuesto es muy similar al del ejercicio 7., cambiando solamente el orden de los elementos en la dupla y el criterio de ordenamiento,
que consiste en ordenar por cantidad de repeticiones (> cantidad de reps. es menor) y desempatar por valor del elemento (< valor es menor).
Dado que la complejidad de comparar seguiría siendo O(1), la complejidad del algoritmo es la misma que la demostrada en el ejercicio 7.: O(n*log(d)),
con d la cantidad de elementos distintos en el arreglo original.
6.
Con una primera pasada sobre el array se identifica la cantidad de escaleras e, el tamaño y valor de inicio de cada una en O(n).
Luego se crea un array tamaño e de tuplas <tamaño, inicio>, y se lo ordena por merge sort usando al tamaño como criterio de ordenamiento pricipal,
y al valor de inicio como criterio de desempate (a mayor tamaño, o igual tamaño y menor valor de inicio, mayor prioridad de orden).
Esto último sería O(e*log(e)), con e la cantidad de escaleras. Como e puede ser acotado por n, la complejidad de este paso puede ser acotada por O(n*log(n))
Luego, a partir del array de tuplas, puede reconstruirse el array de escaleras ordenado como es deseado en O(n).
Todo el algoritmo sería entonces de complejidad O(n*log(n)).
algoritmo ladder_sort(inout arr: Array<int>):
si arr.length > 0: // O(1)
l = nueva lista enlazada vacía // O(1)
inicio = arr[0] // O(1)
e = 1 // O(1)
tamaño = 1 // O(1)
para i = 1..n-1 inclusive: // O(1)
si arr[i] == arr[i-1]: // O(1)
tamaño = tamaño + 1 // O(1)
si no:
l.insertar(<tamaño, inicio>) // O(1)
e = e + 1 // O(1)
inicio = arr[i] // O(1)
// el ciclo es O(n)
tuple_arr = list2array(l) // O(e)
merge_sort(tuple_arr) // O(e*log(e)), con el criterio de ordenamiento antes comentado, in-place
i = 0 // O(1)
para cada tupla de tuple_arr ordenado: // O(1)
tamaño = tupla[0] // O(1)
inicio = tupla[1] // O(1)
para incremento = 0..tamaño-1 inclusive:
arr[i] = inicio + incremento
i = i + 1
// el ciclo es O(tamaño)
// el ciclo es O(n)
// sumando complejidades y tomando máximo, ladder_sort es O(n + e*log(e)), que puede ser acotado por O(n*log(n))
7.
algoritmo AVL_sort(inout arr: Array<int>):
AVL<<int, int>> arbol = new AVL<<int, int>>; // O(1), pedido de memoria
arbol = AVL(); // O(1), inicialización de árbol vacío
for (elem in arr) do
if (arbol.pertenece(elem)) then do // O(log(d)), búsqueda a lo largo del árbol de la tupla que tiene a elem como primer elemento
int elem, reps = obtener(elem); // O(log(d)), asumo tener implementado un método que busca según el elemento que es criterio de ordenamiento y devuelve el valor del nodo completo (en este caso, la dupla de enteros correspondiente)
arbol.eliminar(<elem, reps>); // O(log(d))
arbol.insertar(<elem, reps+1>); // O(log(d))
else do
arbol.insertar(<elem, 1>); // O(log(d)), se asume que el primer elemento de la tupla es el usado para ordenamiento
endif;
endfor; // O(n*log(d))
IteradorInOrder<AVL<<int, int>>> it = new IteradorInOrder<AVL<<int, int>>> // O(1), pedido de memoria para iterador que recorre al AVL in-order
it = arbol.IteradorInOrder(); // O(log(d)), requiere búsqueda del nodo mínimo por ser un iterador in-order
int arr_idx = 0; // O(1)
while (it.haySiguiente()) do // O(log(d))
int elem, reps = it.siguiente(); // O(1)
while (reps >= 1) do // O(1)
arr[arr_idx] = elem; // O(1)
arr_idx = arr_idx + 1; // O(1)
reps = reps - 1; // O(1)
endwhile; // O(cantidad de repeticiones de elem)
endwhile; // O(n)
// sumando complejidades y tomando máximo, AVL_sort es O(n*log(d))
// alternativa
algoritmo AVL_sort(inout arr: Array<int>):
crear un AVL de duplas de enteros // O(1), el primer elemento de cada dupla es el usado para ordenamiento
para cada elemento de arr:
si el elemento no está como primer elemento de una dupla en el AVL // O(log(d))
agregar la dupla <elemento, 1> al AVL // O(log(d))
si lo está
modificar la dupla asociada al elemento incrementando el valor de su segundo elemento en 1 // O(log(d)), podría hacerse con borrado e inserción
// el ciclo completo es O(n*log(d))
partiendo de la pos. 0 del array, para cada elemento del AVL recorrido in-order: // inicializar el iterador necesario es O(log(d)), iterar sobre todo el arbol es O(d) que a su vez puede ser acotado por O(n)
tantas veces como repeticiones tenga el elemento, modificar la próxima posición del array asignandole el valor de elemento // O(cantidad reps. de elemento)
// para cada elem se itera tantas veces como cantidad de repeticiones tiene, dando en total n iteraciones; por lo tanto el ciclo es O(n)
// sumando complejidades y tomando máximo, AVL_sort es O(n*log(d))
8.1.
Recorrer A y armar D, un array de largo n' de tuplas <elemento, repeticiones en A> // O(n)
Para evitar conflictos por tipado de arrays, hacer lo mismo sobre B dando E array de m tuplas de la forma <elemento, 1> (podría tener repetidos) // O(m)
Concatenar D y E en un array F de tamaño n'+m // O(n'+m)
Odenar F por merge sort, usando el primer elemento de cada tupla como criterio de ordenamiento // O((n'+m)*log(n'+m))
Armar C, array de n+m ints, recorriendo F y descomprimiendo las tuplas // O(n+m)
Tomando maximos, la complejidad es O(n + (n'+m)*log(n'+m)), la pedida por enunciado
algoritmo repe_sort(in A, B: Array<int>, out C: Array<int>):
int n' = contar_distintos(A) // O(n)
Array<int> C = new Array<int>[n+m] // O(n+m)
Array<int, int> D = new Array<int, int>[n'] // O(n')
Array<int, int> E = new Array<int, int>[m] // O(m)
Array<int, int> F = new Array<int, int>[n'+m] // O(n'+m)
int contador_n' = 0 // O(1)
for i = 0..n-1 inclusive: // O(1)
if i == 0 or A[i] != D[contador_n'-1][0]: // O(1)
D[contador_n'] = <A[i], 1> // O(1)
contador_n'++ // O(1)
else:
D[contador_n'-1] = <D[contador_n'-1][0], D[contador_n'-1][1]+1> // O(1)
// el ciclo es O(n)
for i = 0..m-1 inclusive: // O(1)
E[i] = <B[i], 1> // O(1)
F[i] = E[i]
// el ciclo es O(m)
for i = m..m+n'-1 inclusive: // O(1)
F[i] = D[i-m] // O(1)
// el ciclo es O(n')
merge_sort(F) // O((n'+m)*log(n'+m))
int C_idx = 0 // O(1)
for i = 0..n'+m-1 inclusive: // O(1)
int elemento, repes = F[i] // O(1)
for _ = 0..repes-1 inclusive: // O(1)
C[C_idx] = elemento // O(1)
C_idx++ // O(1)
// el ciclo es O(repeticiones del elemento en esta tupla en particular)
// el ciclo completo es O(n+m)
return C // O(1)
// el algoritmo repe_sort es O(n + (n'+m)*log(n'+m))
8.2.
El algoritmo es el mismo que en el punto anterior, con la diferencia de que inmediantemente luego de armar D, para cada tupla en D,
se realiza una pasada a lo largo de B contando las apariciones del elemento correspondiente a la tupla y sumandolas a su segundo elemento.
Luego, se puede dejar de lado a B, ordenar el array D modificado por merge sort, y armar C descomprimiento las tuplas.
La complejidad resultante es la pedida, O(n + n'*m + n'*log(n'))
algoritmo repe_sort_BinA(in A, B: Array<int>, out C: Array<int>):
int n' = contar_distintos(A) // O(n)
Array<int> C = new Array<int>[n+m] // O(n+m)
Array<int, int> D = new Array<int, int>[n'] // O(n')
int contador_n' = 0 // O(1)
for i = 0..n-1 inclusive: // O(1)
if i == 0 or A[i] != D[contador_n'-1][0]: // O(1)
D[contador_n'] = <A[i], 1> // O(1)
contador_n'++ // O(1)
else:
D[contador_n'-1] = <D[contador_n'-1][0], D[contador_n'-1][1]+1> // O(1)
// el ciclo es O(n)
for i = 0..n'-1 inclusive: // O(1)
<int, int> tupla = D[i] // O(1), copia por referencia (hay aliasing con el elemento asociado en D)
for elem in B: // O(1)
if elem == tupla[0]: // O(1)
tupla[1]++ // O(1), incrementa la segunda posición de la tupla en el array D
// el ciclo es O(m)
// el ciclo es O(n'*m)
merge_sort(D) // O(n'*log(n'))
int C_idx = 0 // O(1)
for i = 0..n'-1 inclusive: // O(1)
int elemento, repes = D[i] // O(1)
for _ = 0..repes-1 inclusive: // O(1)
C[C_idx] = elemento // O(1)
C_idx++ // O(1)
// el ciclo es O(repeticiones del elemento en esta tupla en particular)
// el ciclo completo es O(n+m)
return C // O(1)
// el algoritmo repe_sort es O(n + n'*m + n'*log(n'))
9.1.
Bucket sort sucesivos, primero por nota y luego por género, con una función de hashing sencilla para género (por separación en casos, F -> 0 y M -> 1, O(1)).
planilla es Array<alumno>
alumno es tupla<nombre: string, género: GEN, puntaje: Nota>
GEN es enum{masc, fem} y Nota es un nat no mayor que 10
algoritmo ordenar_planilla(inout p: planilla):
bucket_sort_nota(planilla) // O(n), primero se ordena por criterio de desempate
bucket_sort_genero(planilla) // O(n), luego se ordena por el criterio principal, siempre usando un algoritmo estable
// la complejidad del algoritmo es O(n)
// bucket_sort_nota usa una función de hashing de la forma:
algoritmo hash_genero(in g: GEN, out i: int):
if g == fem: // O(1)
i = 0 // O(1)
if m == masc: // O(1)
i = 1 // O(1)
return i // O(1)
// O(1)
algoritmo bucket_sort_nota(inout p: planilla):
buckets = nuevo array de 11 listas enlazadas vacías // O(1)
para cada elemento de planilla: // O(1)
_, _, nota = elemento // O(1)
buckets[nota].insertar(elemento) // O(1)
// el ciclo es O(n)
planilla = list2array(concatenar_array_de_listas(buckets)) // O(n)
algoritmo bucket_sort_genero(inout p: planilla):
buckets = nuevo array de tantas listas enlazadas vacías como variantes en GEN // O(1)
para cada elemento de planilla: // O(1)
_, genero, _ = elemento // O(1)
buckets[hash_genero(nota)].insertar(elemento) // O(1)
// el ciclo es O(n)
planilla = list2array(concatenar_array_de_listas(buckets)) // O(n)
9.2.
Lo único que cambia es la función de hashing para género:
algoritmo hash_genero(in g: GEN, out i: int):
i = 0
found = false
for g' in GEN:
if g != g' and not found: // O(1)
i = i + 1 // O(1)
else:
found = true // O(1)
return i // O(1)
9.3.
No, la cota solo aplica para arreglos sobre los que no se tiene ninguna información adicional (salvo que la comparación entre elementos de su tipo es O(1))
y para algoritmos basados en comparaciones. Para este algoritmo se cuenta con información sobre las cotas, la cantidad de valores posibles finita
para cada variable involucrada en el ordenamiento, y el algoritmo en sí no se basa en comparaciones.
10.1.
algoritmo total_sort(inout A: Array<T>): // T comparable
if A.length > 1: // O(1)
casi_sort(A) // O(n)
A = merge(primera_mitad(A), total_sort(segunda_mitad(A))) // O(n)
10.2.
Cada paso de la recursión es O(m) con m la longitud del array input, que es acotable por la longitud del input original n.
Se realizan una cantidad de llamados recursivos que es logaritmo de n.
La complejidad de peor caso es O(n*log(n)). Por teorema maestro (no visto en clase) puede demostrarse que existe una mejor cota: O(n). Esto es porque tanto casi_sort() como merge() son de complejidad lineal sobre el tamaño del input y operan primero sobre todo el input, luego sobre la mitad, luego sobre un cuarto, etcétera. En total realizan en el orden de un múltiplo de 2*n operaciones cada una, que puede ser acotado por O(n).
10.3.
Creo que es imposible, por la necesidad de mergear. El simple hecho de ordenar sublistas recursivamente requiere complejidad O(n).
Sería necesario mergear recursivamente en O(n), pero esto es O(n*log(n))
11.
// Para el caso particular del ejercicio, min es 1 y max es k
algoritmo counting_sort(inout A: Array<int>, in min, max: int):
buckets = nuevo array de max-min+1 enteros inicializados en 0 // O(max-min+1), puede ser acotado por O(n)
para cada elemento de A: // O(1)
buckets[elemento-min]++ // O(1)
// el ciclo es O(n)
bucket_idx = 0
A_idx = 0
mientras bucket_idx < k: // O(1)
reps = buckets[bucket_idx] // O(1)
mientras reps > 0: // O(1)
A[A_idx] = bucket_idx + min // O(1)
reps-- // O(1)
A_idx++ // O(1)
// el ciclo es O(cantidad de repeticiones de bucket_idx + min)
bucket_idx++ // O(1)
// el ciclo es O(n)
// el algoritmo counting_sort es O(n)
12.
algoritmo range_sort(inout arr: Array<int>, in min, max: int):
l1 = nueva lista enlazada vacía // O(1)
l2 = nueva lista enlazada vacía // O(1)
l3 = nueva lista enlazada vacía // O(1)
para cada elemento de arr: // O(1)
si elemento < min: // O(1)
l1.insertar(elemento) // O(1)
si elemento > max: // O(1)
l3.insertar(elemento) // O(1)
si min <= elemento <= max: // O(1)
l2.insertar(elemento) // O(1)
// el ciclo O(n)
a1 = list2array(l1) // O(sqrt(n))
a2 = list2array(l2) // O(n)
a3 = list2array(l3) // O(sqrt(n))
insertion_sort(a1) // O(sqrt(n)**2) = O(n)
insertion_sort(a3) // O(sqrt(n)**2) = O(n)
counting_sort(a2, 20, 40) // O(n), usando el algoritmo descripto en el ejercicio 11.
arr = concatenar_arrays(a1,a2,a3) // O(n)
// el algoritmo range_sort es O(n)
13.1.
El enunciado es ambiguo, creo, sobre la prioridad para ordenamiento. Interpreto que el criterio de ordenamiento principal es el segundo elemento,
y que el primero es criterio de desempate.
El enunciado tampoco aclara que el abecedario de los strings esté acotado, pero esto es lo normal y esperable para cualquier tipo string
y creo que es imposible resolver con la complejidad pedida sin asumirlo.
algoritmo labeled_string_sort(inout A: Array<int, String[l]>):
merge_sort(A) // O(n*log(n)), usando al primer elemento como criterio de ordenamiento
radix_sort(A) // O(n*l), usando a cada caracter para hacer bucket sorts sucesivos comenzando por el caracter en la posicion "menos significativa", la última, del string más largo de todos
// el algoritmo labeled_string_sort es O(n*l + n*log(n))
Para el radix sort se realizan a lo sumo l bucket sorts sucesivos, cada uno sobre un array de |a|+1 listas enlazadas con |a| el tamaño del abecedario.
Como |a| es constante, crear cada array de listas para cada bucket sort puede considerarse O(1).
En cada bucket sort es necesario recorrer todo el array de n posiciones. Por eso la complejidad de hacer radix sort es O(n*l).
Si para el iesimo bucket sort un dado string no tiene un caracter asociado a la posición sobre la que se está ordenando en orden lexicogŕafico
(por ser más corto que el string de largo maximo), se le considera menor a todo el resto. Por eso el array de listas para bucket sort es |a|+1 en vez de |a|,
en esa primera posición adicional se colocarán todos los strings de largo menor o igual al índice (desde 0) de la posición sobre la que se está ordenando.
Por la estabilidad de radix sort, los elementos quedan ordenados como fue pedido.
13.2.
Si los naturales están acotados, se les puede ordenar por counting sort en O(n).
algoritmo labeled_string_sort(inout A: Array<int, String[l]>):
counting_sort(A) // O(n), usando al primer elemento como criterio de ordenamiento
radix_sort(A) // O(n*l), usando a cada caracter para hacer bucket sorts sucesivos comenzando por el caracter en la posicion "menos significativa", la última, del string más largo de todos
// el algoritmo labeled_string_sort es O(n*l)
14.a, b.
Generar listas de multiplos para cada número.
Hacer un MinHeap por heapify de Floyd usando como criterio de ordenamiento al primer elemento (el mínimo) de cada lista.
Desencolar del MinHeap y reestablecer el invariante, desencolar el mínimo de la lista, reinsertar la lista resultante y reestablecer el invariante n*k veces.
proc ordenar_múltiplos(in A: Array<int>, in k: int, out res: Array<int>):
Array<ListaEnlazada<int>> array_de_listas = new Array<ListaEnlazada<int>>[n] // O(n), array de punteros/referencias a listas
for i = 0..n-1 inclusive: // O(1)
ListaEnlazada<int> l = new ListaEnlazada<int> // O(1), lista doblemente enlazada
for m = 1..k inclusive: // O(1)
l.agregarAtras(A[i]*m) // O(1)
// el ciclo es O(k)
array_de_listas[i] = l // O(1), copia por referencia
// el ciclo es O(n*k)
MinHeap heap = heapify(array_de_listas) // O(n), heapify de Floyd usando al primer elemento de cada lista como criterio de ordenamiento, devuelve tipo MinHeap
Array<int> res = new Array<int>[n*k] // O(n*k)
for i = 0..n*k-1 inclusive: // O(1)
ListaEnlazada<int> l = heap.desencolar() // O(log(n))
int min = l.fin() // O(1), devuelve el primer elemento de la lista y modifica a la lista in-place quitando al primer elemento
res[i] = min // O(1)
heap.encolar(l) // O(log(n))
// el ciclo es O(n*k*log(n))
// el proc ordenar_múltiplos es O(n*k*log(n))
15.a, b.
No hay agujero en un array de naturales si solo si el array contiene elementos que, de ser ordenados, formarían una escalera perfecta.
Si la diferencia entre el máximo y el mínimo en el array es igual a la cantidad de elementos sin repetidos, entonces no hay agujero.
La posibilidad de tener repetidos agrega dificultad, pero la lógica es la misma. Hay agujero si:
- n < max-min+1
- n >= max-min+1 (en cuyo caso O(max-min+1) puede ser acotado por O(n)) y algún elemento en [min, max] no pertenece al array.
Basta entonces verificar el cumplimiento o no cumplimiento de estas condiciones.
proc tiene_agujero?(in A: Array<int>, out res: bool):
bool res = false // O(1)
if A.length == 0: // O(1)
return res // O(1)
int min = A[0] // O(1)
int max = A[1] // O(1)
for i = 1..n-1 inclusive: // O(1)
int elem = A[i] // O(1)
if elem < min: // O(1)
min = elem // O(1)
if elem > max: // O(1)
max = elem // O(1)
// el ciclo es O(n)
res = n < max-min+1 // O(1)
if res: // O(1)
return res // O(1)
Array<bool> pertenece = new Array<bool>[max-min+1] // O(max-min+1), puede ser acotado por O(n), array inicializado con false
for i = 0..n-1 inclusive: // O(1)
pertenece[A[i]-min] = true // O(1)
// el ciclo es O(n)
// en este punto, vale res == false
for i = 0..max-min inclusive: // O(1)
if not pertenece[i]: // O(1)
res = true // O(1)
// el ciclo es O(max-min+1), puede ser acotado por O(n)
return res // O(1)
// el proc tiene_agujero? es O(n)
16.a.
Idea 1:
Separar los elementos según si son menores o mayores al maximo.
Luego, en cada sublista separar los elementos según si son menores o mayores a m/4 o m*3/4 según corresponda.
Continuar con este proceso de manera recursiva (a lo sumo, pueden ser O(log(m)) pasos de recursión).
Aplicar merge sobre los llamados recursivos, que puede ser acotado por O(n).
Como en la signatura no se da espacio para pasar un parámetro adicional,
una alternativa es operar usando búsqueda de máximo y mínimo dentro de cada llamado.
proc raro_sort(inout A: array<int>):
if not ordenado(A): // O(n), todo array de longitud 0, 1, o todo array de mayor longitud ordenado de menor a mayor se considera ordenado
int min = buscar_minimo(A) // O(n), como en el ejercicio 15.
int max = buscar_maximo(A) // O(n)
int medio = (min + max)/2 // O(1)
int n_menor_medio = contar_menores(A, medio) // O(n)
int n_mayorigual_medio = contar_mayoriguales(A, medio) // O(n)
Array<int> menores = new Array<int>[n_menor_medio] // se puede acotar por O(n)
Array<int> mayoriguales = new Array<int>[n_mayorigual_medio] // se puede acotar por O(n)
int i = 0 // O(1)
int j = 0 // O(1)
for k = 0..n-1 inclusive: // O(1)
if A[k] < medio: // O(1)
menores[i] = A[k] // O(1)
i++ // O(1)
else:
mayoriguales[j] = A[k] // O(1)
j++ // O(1)
// el ciclo es O(n)
A = merge(raro_sort(menores), raro_sort(mayoriguales)) // O(n)
16.b.
Cada paso de la recursión es O(n) con n la longitud del array input.
Se realizan una cantidad de llamados recursivos que es acotable por el logaritmo de m, ya que en cada llamado se divide el rango de valores a la mitad.
Por lo tanto, la complejidad de peor caso es O(n*log(m)).
16.c.
Otra forma es hacer radix sort sobre los digitos de los elementos del array input. Como la cantidad de digitos es a lo sumo la cantidad de digitos del máximo
y como la cantidad de digitos de un valor es aproximadamente su logaritmo base 10, se obtiene también una complejidad O(n*log(m)).
17.
El elemento más grande del array sólo puede originalmente estar en la última o anteúltima posición del array.
Luego, una vez el maximo esté posicionado correctamente al final del array via (de ser necesario) un swap con el elemento originalmente al final del array,
el próximo elemento más grande sólo puede estar en la penúltima o antepenúltima posición; nuevamente se lo puede swappear con su vecino para ordenar el array.
Este proceso puede ser iterado hasta llegar al comienzo del array: en cada paso, a lo sumo puede ser necesario un swap, porque el próximo elemento más
grande del array solo puede ocupar una de dos posiciones en el array (la "actual" en el ciclo que recorre la lista, o la de su vecino izquierdo).
algoritmo swap_sort(inout A: Array<int>):
for i = n-1..1 inclusive: // O(1), el array se indexa desde 0
if A[i] < A[i-1]: // O(1)
swap(A, i, i-1) // O(1)
// el ciclo es O(n)
// el algoritmo swap_sort es O(n)
18.1.
Un algoritmo particularmente conveniente para este caso es counting_sort (ver ejercicio 11.).
18.2, 3.
algoritmo base_sort(inout A: Array<int>, in k: int): // para 18.2., k = 2
Array<Array<int>> B = convertir_base_n(A, k) // O(n*k), n es el tamaño de A, asumo que tengo función que convierte a cada valor de A en un array de k elementos entre 0 y n-1 ordenados del más al menos significativo en base n
for i = k-1..0 inclusive: // O(1)
counting_sort(B) // O(n), usando como clave de ordenamiento al elemento en posición i de cada subarray de B
// el ciclo es O(n*k)
A = convertir_base_10(B) // O(n*k), para cada B[i] recalcula A[i] como la sumatoria de los B[i]**j con j entre 0 y k-1 inclusive
// el algoritmo base_sort es O(n*k)
18.4.
Se podría buscar el máximo, luego hallar k mínimo tal que n**k > máximo, y aplicar el algoritmo base_sort con ese k. La complejidad seguiría siendo O(n*k).
Si k > log(n), podría convenir hacer merge sort o heap sort sobre todo el array (idem ej. 3.).