how to apply certain list index to sort in python

Question

I have been asked to sort a k messed array I have below code. I have to reduce the complexity from nlogn to nlogk.

arr = [3,2,1,4,5,6,8,10,9]
k = 2
def sortKmessedarr(arr, k):
    i = 1
    j = 0
    n = len(arr)
    while i < n:
        if arr[i] > arr[i-1]:
            pass
        else:
            arr[i-1:i+k].sort() # How to sort elements between two specific indexs
        i += 1
sortKmessedarr(arr, k)
print(arr)

I think if I apply this approach then it will become nlogk

But how to apply this sort() between two indexes.

I have also tried another approach like below:

arr = [3,2,1,4,5,6,8,10,9]
k = 2
def sortKmessedarr(arr, k):
    def merge(arr):
        arr.sort()
        print(arr)
    i = 1
    j = 0
    n = len(arr)
    while i < n:
        if arr[i] > arr[i-1]:
            pass
        else:
            merge(arr[i-1:i+k])#.sort()
        i += 1
sortKmessedarr(arr, k)
print(arr)

But still no luck

If your code works but you want people to suggest better options, your question is probably better suited for Code Review — TemporalWolf
– TemporalWolf, Commented Jan 19, 2017 at 19:49

2ps · Accepted Answer · 2017-01-19 19:47:02Z

1

You can use sorted with slice assignment to get the intended effect syntactically, but I am unsure of the impact on performance (memory or speed):

arr[i-1:i+k] = sorted(a[i-1:i+k])

answered Jan 19, 2017 at 19:47

2ps

16k2 gold badges34 silver badges53 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Rasmi Ranjan Nayak Over a year ago

It did work, then why it was not working with .sort()

juanpa.arrivillaga Over a year ago

@RasmiRanjanNayak Because arr[i - 1: i + k] returns a new list, which is sorted in-place. You never capture the new list, so it gets garbage collected. Essentially, that line of code does nothing useful.

Collectives™ on Stack Overflow

how to apply certain list index to sort in python

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related