Я хочу отсортировать массив [[x₁, y₁], [x₂, y₂], [x₃, y₃],...] по первому члену. Я знаю, что это выполнимо с помощью пузырьковой сортировки, но есть ли более краткий и эффективный способ сортировки массива? Вот рабочий код для пузырьковой сортировки.
def bubble_sort(n, array):
for i in range(n):
swap = False
for j in range(n-i-1):
if array[j][0] > array[j+1][0]:
array[j][0], array[j+1][0] = array[j+1][0], array[j][0]
swap = True
if not swap:
break
return array
По умолчанию сортировка выполняется по первому термину, затем по второму и так далее. Если вы этого не хотите, см. stackoverflow.com/questions/5212870/… Или вы можете использовать key=lambda x:x[0]
«Я думаю, что сортировка пузырьком была бы неправильным путем». -Барак Обама
Используйте встроенный метод сортировки из Python.
import random
test_list = [[random.randint(0, 10), random.randint(0, 10)] for i in range(10)]
print(test_list)
# sort using the first element
test_list.sort(key=lambda x: x[0])
# or
test_list = sorted(test_list, key=lambda x: x[0])
print(test_list)
Алгоритм сортировки, используемый для sorted
, - это Timsort
, который может достичь O(nlogn)
в худшем случае и O(n)
в лучшем случае. Это быстрее, чем O(n^2)
пузырьковой сортировкой.
ссылка: отсортировано , тимсорт
спасибо :) Это действительно полезно. Я пытался использовать встроенную функцию сортировки, но забыл x:
, поэтому не смог заставить ее работать. Кстати, вы знаете разницу между sorted
и list.sort
, если она есть?
Рад, что вы нашли это полезным! И да, большинство на самом деле предпочитает встроенный метод sorted()
методу списка .sort()
, поскольку .sort()
изменяет исходный список или, другими словами, сортировку «на месте», а sorted()
не просто возвращает отсортированный список. Кроме того, sorted()
можно использовать для всех итерируемых объектов, а .sort()
— нет.
Вы можете использовать sort () (O (NlogN)), который представляет собой адаптивный алгоритм, основанный на сортировке слиянием и вставкой в python, также называемый Timsort, но в C для массивов quicksort — это эффективный метод, который имеет ту же временную сложность, что и Timsort.
Настройка быстрой сортировки на ту же временную сложность, что и Timsort, является некоторым упрощением. Это верно в среднем случае, но не в лучшем и худшем случаях.
Я полностью понимаю, что вы пытаетесь сказать, но вы можете обратиться сюда wiki.python.org/moin/TimeComplexity
Временная сложность пузырьковой сортировки составляет O (n ^ 2). Встроенная функция sort()
в Python автоматически сортирует по первому элементу и сортирует за время O(n log n), что быстрее, чем O(n^2).
def bubble_sort(n, array):
array.sort()
return array
ПРИМЕЧАНИЕ. На самом деле это не алгоритм пузырьковой сортировки. Я просто сохранил имя вашей функции для простоты.
Я не думаю, что это сработает, потому что каждый элемент массива представляет собой список из двух элементов, а не слово/целое число. Однако я могу добавить key=lambda x:x[0]
, чтобы он сортировался по первому элементу. Благодарю за ваш ответ.
Конечно, вы можете использовать функцию
sorted
, она делает свою работу в одну строку.