Язык программирования Python

Как создать эффективный алгоритм для сортировки списка в python?

Рассмотрим следующий отсортированный список с отрицательными и положительными значениями

l = [-4, -1, 0, 2, 5, 10]

Цель: создать эффективный алгоритм для возведения элементов в квадрат и сортировки списка:

Решение

Мое решение, возможно, не оптимальное, но лучшее, которое я нашел на данный момент:

l = [-4, -1, 0, 2, 5, 10] min_value = 9999 l_new = [] for idx,i in enumerate(l): new_i = i**2 if new_i < min_value: min_value = new_i min_value_idx = idx l_new.append(new_i) #print(new_i,min_value,min_value_idx) l_pop = [] for idx in range(min_value_idx): l_pop.append(l_new.pop(0)) for value in l_pop: jdx = len(l_new) - 1 cond = True while cond: jdx -= 1 if value > l_new[jdx]: l_new.insert(jdx+1, value) cond = False print('l_new',l_new)
Code language: HTML, XML (xml)

Результат:

[0, 1, 4, 16, 25, 100]
Code language: JSON / JSON with Comments (json)

Создание функции

def sort_list(l): nb_count = 0 min_value = 9999 l_new = [] for idx,i in enumerate(l): new_i = i**2 if new_i < min_value: min_value = new_i min_value_idx = idx l_new.append(new_i) nb_count += 1 #print(new_i,min_value,min_value_idx) l_pop = [] for idx in range(min_value_idx): l_pop.append(l_new.pop(0)) nb_count += 1 for value in l_pop: jdx = len(l_new) - 1 cond = True while cond: jdx -= 1 if value > l_new[jdx]: l_new.insert(jdx+1, value) cond = False nb_count += 1 if jdx<0: cond = False return l_new, nb_count l = [-4, -1, 0, 2, 5, 10] l_new, nb_count = sort_list(l) print(l_new) print(nb_count)
Code language: HTML, XML (xml)

Результат:

[0, 1, 4, 16, 25, 100] 10
Code language: JSON / JSON with Comments (json)

Сравнение со “встроенными” функциями python

l = [-4, -1, 0, 2, 5, 10] l = [i**2 for i in l] l.sort() print(l)
Code language: PHP (php)

Результат:

[0, 1, 4, 16, 25, 100]
Code language: JSON / JSON with Comments (json)

Создание визуализации

import matplotlib.pyplot as plt import random import math n_list = [] nlogn_list = [] count_list = [] for n in range(10,1000): l = [random.randint(-100,100) for i in range(n)] l.sort() #print(l) l_new, nb_count = sort_list(l) n_list.append(n) nlogn_list.append(n*math.log(n)) count_list.append(nb_count) plt.xlabel('N List Size') plt.ylabel('Iterations') plt.scatter(n_list,count_list) plt.scatter(n_list,nlogn_list)
Code language: PHP (php)

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *