Python Merge sort count inversions
Clash Royale CLAN TAG#URR8PPP
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty margin-bottom:0;
up vote
1
down vote
favorite
def mergeCount(left,right,invCount):
inversionCount = invCount
# print(left,right)
for right_item in right:
offset = 0
insertState = False
for i in range(len(left)):
if left[i] <= right_item:
offset += 1
elif left[i] > right_item:
inversionCount += len(left) - offset
left.insert(i,right_item)
# print("inserted",right_item)
insertState = True
break
if not insertState:
left.append(right_item)
# print("new array is",left)
return left,inversionCount
def mergeSortInversion(array):
if len(array) <= 1:
return array,0
else:
left_arr, left_count = mergeSortInversion(array[:len(array)//2])
right_arr, right_count = mergeSortInversion(array[len(array)//2:])
# print(left_arr,right_arr,left_count+right_count)
return mergeCount(left_arr,right_arr,left_count + right_count)
My merge sort code is taking the same amount of time as the brute force method for some reason. How can I fix the implementation / make it better?
python python-3.x
asked Jan 24 at 16:29
Xuan
61
add a comment |Â
up vote
1
down vote
favorite
def mergeCount(left,right,invCount):
inversionCount = invCount
# print(left,right)
for right_item in right:
offset = 0
insertState = False
for i in range(len(left)):
if left[i] <= right_item:
offset += 1
elif left[i] > right_item:
inversionCount += len(left) - offset
left.insert(i,right_item)
# print("inserted",right_item)
insertState = True
break
if not insertState:
left.append(right_item)
# print("new array is",left)
return left,inversionCount
def mergeSortInversion(array):
if len(array) <= 1:
return array,0
else:
left_arr, left_count = mergeSortInversion(array[:len(array)//2])
right_arr, right_count = mergeSortInversion(array[len(array)//2:])
# print(left_arr,right_arr,left_count+right_count)
return mergeCount(left_arr,right_arr,left_count + right_count)
My merge sort code is taking the same amount of time as the brute force method for some reason. How can I fix the implementation / make it better?
python python-3.x
asked Jan 24 at 16:29
Xuan
61
Have you tried profiling it? Can you show the test cases and timing setup you're using?
– Dannnno
Jan 24 at 17:15
When you take a slice of a list in Python, likearray[:len(array)//2], this has to copy out the contents of the slice, taking time proportional to the number of elements in the slice. This is what makes your code run slowly. You have to leavearrayunsliced and instead pass the indexes of the start and end of the slice as parameters.
– Gareth Rees
Jan 24 at 17:18
There's no need ininversionCount, you can manipulateinvCountdirectly
– Alex.S
Jan 26 at 12:10
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
def mergeCount(left,right,invCount):
inversionCount = invCount
# print(left,right)
for right_item in right:
offset = 0
insertState = False
for i in range(len(left)):
if left[i] <= right_item:
offset += 1
elif left[i] > right_item:
inversionCount += len(left) - offset
left.insert(i,right_item)
# print("inserted",right_item)
insertState = True
break
if not insertState:
left.append(right_item)
# print("new array is",left)
return left,inversionCount
def mergeSortInversion(array):
if len(array) <= 1:
return array,0
else:
left_arr, left_count = mergeSortInversion(array[:len(array)//2])
right_arr, right_count = mergeSortInversion(array[len(array)//2:])
# print(left_arr,right_arr,left_count+right_count)
return mergeCount(left_arr,right_arr,left_count + right_count)
My merge sort code is taking the same amount of time as the brute force method for some reason. How can I fix the implementation / make it better?
python python-3.x
asked Jan 24 at 16:29
Xuan
61
def mergeCount(left,right,invCount):
inversionCount = invCount
# print(left,right)
for right_item in right:
offset = 0
insertState = False
for i in range(len(left)):
if left[i] <= right_item:
offset += 1
elif left[i] > right_item:
inversionCount += len(left) - offset
left.insert(i,right_item)
# print("inserted",right_item)
insertState = True
break
if not insertState:
left.append(right_item)
# print("new array is",left)
return left,inversionCount
def mergeSortInversion(array):
if len(array) <= 1:
return array,0
else:
left_arr, left_count = mergeSortInversion(array[:len(array)//2])
right_arr, right_count = mergeSortInversion(array[len(array)//2:])
# print(left_arr,right_arr,left_count+right_count)
return mergeCount(left_arr,right_arr,left_count + right_count)
My merge sort code is taking the same amount of time as the brute force method for some reason. How can I fix the implementation / make it better?
python python-3.x
asked Jan 24 at 16:29
Xuan
61
asked Jan 24 at 16:29
Xuan
61
asked Jan 24 at 16:29
Xuan
61
asked Jan 24 at 16:29
Xuan
61
61
Have you tried profiling it? Can you show the test cases and timing setup you're using?
– Dannnno
Jan 24 at 17:15
When you take a slice of a list in Python, likearray[:len(array)//2], this has to copy out the contents of the slice, taking time proportional to the number of elements in the slice. This is what makes your code run slowly. You have to leavearrayunsliced and instead pass the indexes of the start and end of the slice as parameters.
– Gareth Rees
Jan 24 at 17:18
There's no need ininversionCount, you can manipulateinvCountdirectly
– Alex.S
Jan 26 at 12:10
add a comment |Â
Have you tried profiling it? Can you show the test cases and timing setup you're using?
– Dannnno
Jan 24 at 17:15
When you take a slice of a list in Python, likearray[:len(array)//2], this has to copy out the contents of the slice, taking time proportional to the number of elements in the slice. This is what makes your code run slowly. You have to leavearrayunsliced and instead pass the indexes of the start and end of the slice as parameters.
– Gareth Rees
Jan 24 at 17:18
There's no need ininversionCount, you can manipulateinvCountdirectly
– Alex.S
Jan 26 at 12:10
Have you tried profiling it? Can you show the test cases and timing setup you're using?
– Dannnno
Jan 24 at 17:15
Have you tried profiling it? Can you show the test cases and timing setup you're using?
– Dannnno
Jan 24 at 17:15
When you take a slice of a list in Python, like
array[:len(array)//2], this has to copy out the contents of the slice, taking time proportional to the number of elements in the slice. This is what makes your code run slowly. You have to leave array unsliced and instead pass the indexes of the start and end of the slice as parameters.– Gareth Rees
Jan 24 at 17:18
When you take a slice of a list in Python, like
array[:len(array)//2], this has to copy out the contents of the slice, taking time proportional to the number of elements in the slice. This is what makes your code run slowly. You have to leave array unsliced and instead pass the indexes of the start and end of the slice as parameters.– Gareth Rees
Jan 24 at 17:18
There's no need in
inversionCount, you can manipulate invCount directly– Alex.S
Jan 26 at 12:10
There's no need in
inversionCount, you can manipulate invCount directly– Alex.S
Jan 26 at 12:10
add a comment |Â
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
Â
draft saved
draft discarded
Â
draft saved
draft discarded
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f185887%2fpython-merge-sort-count-inversions%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Have you tried profiling it? Can you show the test cases and timing setup you're using?
– Dannnno
Jan 24 at 17:15
When you take a slice of a list in Python, like
array[:len(array)//2], this has to copy out the contents of the slice, taking time proportional to the number of elements in the slice. This is what makes your code run slowly. You have to leavearrayunsliced and instead pass the indexes of the start and end of the slice as parameters.– Gareth Rees
Jan 24 at 17:18
There's no need in
inversionCount, you can manipulateinvCountdirectly– Alex.S
Jan 26 at 12:10