CODEWITHSUNDEEP
pythonsorting
Lexi
Lexi

Reputation: 1

python, insertion sort, strings

I need to sort this list without using built-in sort(). I figured I could use insertion sort, but I've never really used it before. My code doesn't seem to be working. What is wrong with it? Thank you.

fruits = ['grape', 'banana', 'strawberry', 'apple', 'peach', 'cherry']



for i in range(1, len(fruits)):
    tmp = fruits[i]
    j = i-1;
    while (j>0 and fruits[j] > tmp):
        fruits[j+1] = fruits[j]
        j = j-1
        fruits[j+1] = tmp
print(fruits)

Upvotes: 0

Views: 4655

Answers (5)

ANGY
ANGY

Reputation: 23

This works perfectly too!

Fruits= ['grape', 'banana', 'strawberry', 'apple', 'peach', 'cherry']
def insertionSortFruits():
    for i in range(1,len(Fruits)):
        key=Fruits[i]
        j=i-1
        while j>=0 and key<Fruits[j]:
            Fruits[j+1]=Fruits[j]
            j=j-1
        Fruits[j+1]=key
    print(Fruits)

#Testing
insertionSortFruits()

Upvotes: 1

yashjn72
yashjn72

Reputation: 1

fruits = ['grape', 'banana', 'strawberry', 'apple', 'peach', 'cherry']
for i in range(1,len(fruits))
temp=fruits[i]
k = i
    while k > 0 and tmp < fruits[k - 1]:
        fruits[k] = fruits[k - 1]
        k -= 1
    fruits[k] = tmp
print fruits

your loop will execute one time less as j=i-1 j>0 it should be j>-1

Upvotes: 0

Anton vBR
Anton vBR

Reputation: 18906

I changed two things and it works. Not exactly meant as an answer but might help you forward.

fruits = ['grape', 'banana', 'strawberry', 'apple', 'peach', 'cherry']

for i in range(0, len(fruits)):
    tmp = fruits[i]
    j = i-1;
    print(fruits)
    while (j>-1 and fruits[j] > tmp):
        fruits[j+1] = fruits[j] 
        j = j-1
        fruits[j+1] = tmp

print(fruits)

Could be made smaller this way:

fruits = ['grape', 'banana', 'strawberry', 'apple', 'peach', 'cherry']

for i in range(len(fruits)):

    tmp = fruits[i]
    j = i-1 # stop index
    while (j > -1 and fruits[j] > tmp):
        fruits[j:j+2] = tmp,fruits[j] #swap places
        j -= 1

print(fruits)

Returns:

['apple', 'banana', 'cherry', 'grape', 'peach', 'strawberry']

Upvotes: 0

Suaro
Suaro

Reputation: 322

First replace lens() by len().

In other hand, you not apply your function over fruits array, you only declare function.

Finally, arrays start at index 0, so j must be> = 0.

Corrected code:

fruits = ['grape', 'banana', 'strawberry', 'apple', 'peach', 'cherry']

def insertion_sort(fruits):

   for i in range(1, len(fruits)):
       tmp = fruits[i]
       j = i-1;
       while (j>=0 and fruits[j] > tmp):
           fruits[j+1] = fruits[j];
           j = j-1;
      fruits[j+1] = tmp;
   return fruits

if __name__ == "__main__":

     fruits2 = insertion_sort(fruits)
     print(fruits2)

Upvotes: 0

Horia Coman
Horia Coman

Reputation: 8781

The swap operation which appears in the inner loop seems quite strange. If I were a betting person I'd say that's where the error occurs.

Try doing a clean "swap", like you'd do it for three variables:

a = 10
b = 20
tmp = a
a = b
b = tmp
print(a) # prints 20
print(b) # prints 10

Your code will become something like:

for i in range(1, len(fruits)):
    j = i-1
    while j >= 0 and fruits[j] > fruits[j+1]:
        # Swap the two consecutive elements which are unsorted
        tmp = fruits[j]
        fruits[j] = fruits[j+1]
        fruits[j+1] = tmp
        # Prepare to process previous two consecutive elements
        j = j-1

Upvotes: 0

Related Questions