Metodo de la burbuja

Universidad Michoacana de San Nicolás de Hidalgo Facultad de Ingeniería Eléctrica Estructuras de Datos

Ramírez Rueda Juventino Ing. en Computación 0686696C

Mostrar por inducción que �� �� =����1 + ������2 es válida para cualquier N con �� = 2�� . Considerando que el número de elementos es potencia de 2 N = 32 = 2 . Definimos C1 como el tiempo para ordenar un arreglo o lista de tamaño unitario y C2el tiempo para pegar un elemento. Así el tiempo para ordenar N elementos lo resolvemos con la recurrencia �� �� = 2 �� Caso base �� = 1 �� ���� = �� �� �� 21 = 2 �� �� 2 = 2 ��
2 2 ���� �� 21 2
5�� + ����2 2

+ ���� ���� + 21 ��2

+ 2��2

�� 2 = 2 �� 1 + 2��2 Como �� 1 = ��1 �� 2 = 2 ��1 + 2��2 �� ���� = ���� ���� + ������ ���� �� 21 = 21 ��1 + 1 21 ��2 �� 2 = 2��1 + 2��2 Para el casobase ambas expresiones son iguales Paso recursivo �� 2��+1 = 2 ��
2 ��+1 2

+ 2��+1 ��2

�� 2��+1 = 2 �� 2�� + 2��+1 ��2 �� 2��+1 = 2��+1 ��1 + �� + 1 2��+1 ��2 �� 2��+1 = 2��+1 ��1 + �� + 12��+1 ��2 �� 2��+1 = 2 2�� ��1 + ��2�� ��2 + 2��+1 ��2 �� 2��+1 = 2 �� 2�� + 2�� +1 ��2 Asi queda demostrado que �� �� = ����1 + ������2 es válida para cualquier N.

1

Universidad Michoacana de SanNicolás de Hidalgo Facultad de Ingeniería Eléctrica Estructuras de Datos

Ramírez Rueda Juventino Ing. en Computación 0686696C

Hacer la simulación para ordenar el arreglo A = {5, 7, 0, 3, 10, 20, 1,15} utilizando: a) Burbuja b) Selection Sort c) MergeSort
Burbuja A = {5, 7, 0, 3, 10, 20, 1, 15} A = {5, 7, 0, 3, 10, 1, 20, 15} A = {5, 7, 0, 3, 10, 1, 15, 20} A = {5, 7, 0, 3, 10, 1, 15, 20} A ={5, 7, 0, 3, 1, 10, 15, 20} A = {5, 7, 0, 3, 1, 10, 15, 20} A = {5, 0, 7, 3, 1, 10, 15, 20} A = {5, 0, 3, 7, 1, 10, 15, 20} A = {5, 0, 3, 1, 7, 10, 15, 20} A = {5, 0, 3, 1, 7, 10, 15, 20} A = {0, 5,3, 1, 7, 10, 15, 20} A = {0, 3, 5, 1, 7, 10, 15, 20} A = {0, 3, 1, 5, 7, 10, 15, 20} A = {0, 3, 1, 5, 7, 10, 15, 20} A = {0, 1, 3, 5, 7, 10, 15, 20} A = {0, 1, 3, 5, 7, 10, 15, 20}...