0

I want to sort the array [[x₁, y₁], [x₂, y₂], [x₃, y₃],...] by the first term. I know that it is doable with bubble sorting, but is there more concise and efficient way to sort the array? Here is a working code for bubble sorting.

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
cs95
  • 379,657
  • 97
  • 704
  • 746
CELLSecret
  • 139
  • 1
  • 9
  • 3
    Sure, you can use the `sorted` function, it does the job in one line. – cs95 Dec 18 '20 at 05:13
  • The default will sort by the first term, then the second, and so on. If you don't want that then see https://stackoverflow.com/questions/5212870/sorting-a-python-list-by-two-fields Or you can use key=lambda x:x[0] – Kenny Ostrom Dec 18 '20 at 05:22
  • 1
    "I think the bubble sort would be the wrong way to go." –Barack Obama – Klaus D. Dec 18 '20 at 05:38

3 Answers3

2

Use the built-in sort method from 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)

The sorting algorithm used for sorted is Timsort, which can achieve O(nlogn) in worst case and O(n) in best case. It is faster than O(n^2) by bubble sort.

reference: sorted, timsort

kennysliding
  • 2,783
  • 1
  • 10
  • 31
  • thank you :) This is helpful actually. I've tried to use the build-in sort function but I forgot `x:` so I couldn't get it to work. By the way, do you know the difference between `sorted` and `list.sort` if there is any? – CELLSecret Dec 18 '20 at 20:08
  • Glad you find that helpful! And yes, most actually prefer the built-in method `sorted()` over the list method `.sort()`, since `.sort()` modifies the original list, or in other word, "in-place" sort, while `sorted()` doesn't but simply return a sorted list. Plus, `sorted()` can be used on all iterable objects but `.sort()` is not. – kennysliding Dec 19 '20 at 03:07
1

Bubble sort's time complexity is O(n^2). The built-in sort() function in Python will automatically sort by the first element and it will sort in O(n log n) time, which is faster than O(n^2).

def bubble_sort(n, array):
  array.sort()
  return array

NOTE: This is not actually a bubble sort algorithm. I just maintained your function name for simplicity.

Paul
  • 137
  • 4
  • I don't think that would work because every item in the array is a two-item list instead of a word/integer. I can, however, add `key=lambda x:x[0]` to let it sort by the first item. Thank you for your response. – CELLSecret Dec 18 '20 at 20:16
0

You can use sort() (O(NlogN))which is an adaptive algorithm based on merge and insertion sort in python also called Timsort but in C for arrays quicksort is the efficient method that has the same time complexity as Timsort.

Rakshit Ajay
  • 7
  • 1
  • 8
  • Setting that quicksort has the same time complexity as Timsort is a bit of a simplification. It's true in the average case, but not the best and worst cases. – Brian McCutchon Dec 18 '20 at 05:33
  • I totally get what you are trying to say but you can refer here https://wiki.python.org/moin/TimeComplexity – Rakshit Ajay Dec 19 '20 at 12:17