4 Replies - 191 Views - Last Post: 24 August 2014 - 10:33 AM Rate Topic: -----

#1 yolo  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 1
  • Joined: 23-August 14

Mergesort Not Sorting Correctly

Posted 23 August 2014 - 01:48 PM

code:
def merge_sort(list,i,j,new_list):
    '''
    (list,int,int) -> list
    
    modifies and sorts 'list' showing steps and returns list
    
    >>> merge_sort([3,2,-4,6,5], 0, len([3,2,-4,6,5]),[0]*len([3,2,-4,6,5]))
    
    '''

    if j-i <= 1:
        return []

    n = (i+j)//2

    merge_sort(list,i,n,new_list)
    merge_sort(list,n,j,new_list)

    merge(list,i,j,new_list)

    return new_list

def merge(list,i,j,new_list):
    '''
    (list,int,int,list) -> None

    merges two sub lists in an order
    '''
    
    n = (i+j)//2
    i1 = i
    j1 = n
    i2 = n
    j2 = j

    while i1 < j1 and i2 < j2:
        if list[i1] < list[i2] :
            new_list[i] = list[i1]
            i1 = i1 + 1
        else:
            new_list[i] = list[i2]
            i2 = i2 + 1
        i = i + 1

    while i1 < j1:
        new_list[i] = list[i1]
        i1 = i1 + 1
        i = i + 1

    while i2 < j2:
        new_list[i] = list[i2]
        i2 = i2 + 1
        i = i + 1

    return new_list



when I run it and type:
>>> merge_sort([3,2,-4,6,5], 0, len([3,2,-4,6,5]),[0]*len([3,2,-4,6,5]))
[-4, 3, 2, 6, 5]


I don't get any errors, and I can't seem to find the problem here. Please help! :)

also, the merge() function seems to be working fine:
>>> list = [2,6,9,3,6,8]
>>> merge(list,0,len(list),[0]*len(list))
[2, 3, 6, 6, 8, 9]

This post has been edited by macosxnerd101: 23 August 2014 - 01:51 PM
Reason for edit:: Renamed title to be more descriptive


Is This A Good Question/Topic? 0
  • +

Replies To: Mergesort Not Sorting Correctly

#2 andrewsw  Icon User is online

  • It's just been revoked!
  • member icon

Reputation: 3607
  • View blog
  • Posts: 12,393
  • Joined: 12-December 12

Re: Mergesort Not Sorting Correctly

Posted 23 August 2014 - 03:19 PM

What should the output be?

You wrote this? So hopefully you should have some idea of where the problem is..?

And what do the four arguments to merge_sort represent?
Was This Post Helpful? 0
  • +
  • -

#3 DK3250  Icon User is offline

  • D.I.C Head

Reputation: 27
  • View blog
  • Posts: 105
  • Joined: 27-December 13

Re: Mergesort Not Sorting Correctly

Posted 24 August 2014 - 08:28 AM

In your call to the merge_sort function, don't do
[0]*len([3,2,-4,6,5] 

The values in your new_list becomes not five different zeros but rather the same zero times five. Change of one value will affect all.
You need to do something like:
new_list = []
for i in range(len([...])):
    new_list.append(0)


Another thing: Don't use the name <list> for a variable - list is a reserved word in Python; use <lst> or something else.

This post has been edited by DK3250: 24 August 2014 - 08:31 AM

Was This Post Helpful? 0
  • +
  • -

#4 sepp2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2127
  • View blog
  • Posts: 3,260
  • Joined: 21-June 11

Re: Mergesort Not Sorting Correctly

Posted 24 August 2014 - 10:17 AM

View PostDK3250, on 24 August 2014 - 05:28 PM, said:

The values in your new_list becomes not five different zeros but rather the same zero times five.


That's not a meaningful distinction for integers.

Quote

Change of one value will affect all.


Except you can't perform any changes on integers. All you can do is reassign the array slot, which does not change anything except that array slot.

There's nothing wrong with [0] * n.
Was This Post Helpful? 0
  • +
  • -

#5 DK3250  Icon User is offline

  • D.I.C Head

Reputation: 27
  • View blog
  • Posts: 105
  • Joined: 27-December 13

Re: Mergesort Not Sorting Correctly

Posted 24 August 2014 - 10:33 AM

OK - I just had a similar situation with nested lists. And
[[0]*10]*10

is certainly problematic.
I should have checked the details before posting.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1