Количество инверсий с использованием сортировки слияния

Я пытаюсь реализовать знаменитый: подсчет инверсий с использованием сортировки слияния. Я написал для этого код. Код работает хорошо для небольших данных. У меня было несколько тестовых примеров, в которых я проверил ответ. Но код занимает очень много времени, когда вход большой (100000). Итак, я просто хочу убедиться, что сложность моего кода - O (N lgN) и не выше (будучи более сложной, может потребоваться больше времени). Вот мой код в Python:Количество инверсий с использованием сортировки слияния

def merge_sort(u_list,inv): 
    if(len(u_list) == 1): return 0 
    if(len(u_list)>1): 
     mid=len(u_list)//2 
     l_list=u_list[:mid] 
     r_list=u_list[mid:] 
     a=merge_sort(l_list,inv) 
     b=merge_sort(r_list,inv) 
     count=0 

     i=0 
     j=0 
     k=0 
     track=0 
     while i<len(l_list) and j<len(r_list) : 
      if l_list[i]<=r_list[j]: 
       u_list[k]=l_list[i] 
       track+=1 
       i+=1 
       k+=1 

      else: #r_list[j]<l_list[i] 
       u_list[k]=r_list[j] 
       inv=inv+(len(l_list)-track) 
       j+=1 
       k+=1 

     while i<len(l_list) : 
      u_list[k]=l_list[i] 
      i+=1 
      k+=1 

     while j<len(r_list): 
      u_list[k]=r_list[j] 
      j+=1 
      k+=1 
     count=inv+a+b 
     return count 

inv=0 
m=0 
u_list=[] 
x=0 
for m in range(0,100000): 
    x=int(input()) 
    u_list.append(x) 

foo = merge_sort(u_list,inv) 
print(foo)

источник

2015-10-18 Anonymous

можете ли вы оформить свой код? т. е. вы уверены, что не тратит больше времени на ввод? – Ashalynd

Я не вижу ничего плохого, поэтому я согласен, что проблема может заключаться в чтении и анализе ввода. Поместите 'print' перед' foo = merge_sort (u_list, inv) ', чтобы убедиться, что он закончил этот этап и сортирует. –

related: 'O (n log n)' реализация ['sort_and_count()'] (http://stackoverflow.com/a/2989341/4279) – jfs

Я заменил

for m in range(0,100000): 
    x=int(input()) 
    u_list.append(x)

from random import * 
u_list = list(range(100000)) 
shuffle(u_list)

и побежал код и он занимает около секунды, что кажется нормальным. Я думаю, что ваш тип слияния прекрасен, и что-то не так на входе. Как вы передаете вход в скрипт? Если вы транслируете в большом текстовом файле, возможно ли, что файл не является 100000 строк, а программа просто ждет навсегда?

источник

2015-10-19 02:14:25

На самом деле я пользуюсь www.ideone.com. Я думаю, что это не лучший метод. –

Ха-ха определенно нет. –

Да, я понял, что что-то не так с входом. Я опубликовал исправленную версию. Спасибо за вашу помощь. –

Поскольку я имел входные данные в текстовом файле, я заменил:

x=0 
for m in range(0,100000): 
    x=int(input()) 
    u_list.append(x)

с этим:

fileName = 'IntegerArray.txt' 
u_list = [] 
with open(fileName) as f: 
    for line in f: 
     u_list.append(int(line))

И получил выход в секунду или около того.

источник

2015-10-19 18:40:35

Количество инверсий с использованием сортировки слияния

ответ

Смежные вопросы