Python - Algoritmo de Clasificación y Algoritmos de Búsqueda
###########################################
#12 Algoritmo de clasificación en Python
#1. Algoritmo de clasificación de Burbujas:
# (Bubble sort algorithm)
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
return arr
#2. Algoritmo de clasificación de Combinar:
# (Merge sort algorithm)
def merge_sort(arr):
if len(arr) > 1:
mid = len(arr) // 2
left_half = arr[:mid]
right_half = arr[mid:]
merge_sort(left_half)
merge_sort(right_half)
i = j = k = 0
while i < len(left_half) and j < len(right_half):
if left_half[i] < right_half[j]:
arr[k] = left_half[i]
i += 1
else:
arr[k] = right_half[j]
j += 1
k += 1
while i < len(left_half):
arr[k] = left_half[i]
i += 1
k += 1
while j < len(right_half):
arr[k] = right_half[j]
j += 1
k += 1
return arr
#3. Algoritmo de Búsqueda Binaria:
# (Binary search algorithm)
def binary_search(arr, x):
low = 0
high = len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] < x:
low = mid + 1
elif arr[mid] > x:
high = mid - 1
else:
return mid
return -1
#4. Algoritmo de Búsqueda Lineal:
# (Linear search algorithm)
def linear_search(arr, x):
for i in range(len(arr)):
if arr[i] == x:
return i
return -1
#5. Algoritmo de clasificación por inserción:
# (Insertion sort algorithm)
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and key < arr[j]:
arr[j+1] = arr[j]
j -= 1
arr[j+1] = key
return arr
#6. Algoritmo de clasificación rápida:
# (Quick sort algorithm)
def quick_sort(arr):
if len(arr) <= 1:
return arr
else:
pivot = arr[0]
left = []
right = []
for i in range(1, len(arr)):
if arr[i] < pivot:
left.append(arr[i])
else:
right.append(arr[i])
return quick_sort(left) + [pivot] + quick_sort(right)
#7. Algoritmo de clasificación de selección
# (Selection sort algorithm)
def selection_sort(arr):
for i in range(len(arr)):
min_index = i
for j in range(i+1, len(arr)):
if arr[j] < arr[min_index]:
min_index = j
arr[i], arr[min_index] = arr[min_index], arr[i]
return arr
#8. Ordene una lista de números en orden ascendente usando la clasificación de burbujas:
# Sort a list of numbers in ascending order using bubble sort:
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
return arr
#9. Ordene una lista de números en orden ascendente usando la ordenación por selección:
# Sort a list of numbers in ascending order using selection sort:
def selection_sort(arr):
n = len(arr)
for i in range(n):
min_index = i
for j in range(i+1, n):
if arr[j] < arr[min_index]:
min_index = j
arr[i], arr[min_index] = arr[min_index], arr[i]
return arr
#10. Ordene una lista de números en orden ascendente usando la ordenación por inserción:
# Sort a list of numbers in ascending order using insertion sort:
def insertion_sort(arr):
n = len(arr)
for i in range(1, n):
key = arr[i]
j = i-1
while j >= 0 and arr[j] > key:
arr[j+1] = arr[j]
j -= 1
arr[j+1] = key
return arr
#11. Ordene una lista de números en orden ascendente usando la ordenación por combinación:
# Sort a list of numbers in ascending order using merge sort:
def merge_sort(arr):
if len(arr) > 1:
mid = len(arr)//2
left_half = arr[:mid]
right_half = arr[mid:]
merge_sort(left_half)
merge_sort(right_half)
i = j = k = 0
while i < len(left_half) and j < len(right_half):
if left_half[i] < right_half[j]:
arr[k] = left_half[i]
i += 1
else:
arr[k] = right_half[j]
j += 1
k += 1
while i < len(left_half):
arr[k] = left_half[i]
i += 1
k += 1
while j < len(right_half):
arr[k] = right_half[j]
j += 1
k += 1
return arr
#12. Ordene una lista de números en orden ascendente usando la ordenación rápida:
# Sort a list of numbers in ascending order using quick sort:
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[0]
left_half = [x for x in arr[1:] if x < pivot]
right_half = [x for x in arr[1:] if x >= pivot]
return quick_sort(left_half) + [pivot] + quick_sort(right_half)
#13. Quick Sort
quicksort = Y(lambda f: lambda x: ( f([item for item in x if item < x[0]])
+ [y for y in x if x[0] == y] + f([item for item in x if item > x[0]])) if x else [])
quicksort([1, 3, 5, 4, 1, 3, 2])