current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 4 down vote favorite

Implementing basic sorting algorithms to learn them, and coding, better. Criticisms/ critiques welcome. Also possible optimizations. 

import unittest
import random

def insertion_sort(seq):
    """Accepts a mutable sequence, utilizes insertion sort algorithm to sort in
    place. Returns an ordered list"""
    #marks point between ordered sublist & unordered list
    partition = 1

    while partition < len(seq):
        temp = partition

        #while temp not in correct pos in sublist, decrement pos
        while temp != 0 and seq[temp] < seq[temp-1]:
            seq[temp], seq[temp-1] = seq[temp-1], seq[temp]
            temp -= 1

        partition += 1

    return seq

class test_insertionsort(unittest.TestCase):
    def test_insertionsort(self):
        """Test insertion_sort()"""
        seq = [random.randrange(0, 1000) for _ in range(1000)]
        self.assertEqual(insertion_sort(seq), sorted(seq))

if __name__ == '__main__':
    unittest.main()
share|improve this question
    
I don't know much python so this maybe don't apply, but usually instead of inserting things to the array, the correct approach is to build a new one from scratch. –  ajax333221 Feb 4 at 5:39
    
@ajax: Insertion sort is usually described as an "in-place sort" so there's nothing wrong with the OP's approach. –  Gareth Rees Feb 4 at 10:12
    
But I do think that using seq.pop and seq.insert is not really in the spirit of the exercise. These methods hide significant details of what the algorithm is doing. To really understand what is going on, you should try to implement it using only list assignment. –  Gareth Rees Feb 4 at 10:16
    
@GarethRees I've updated the code to implement your critique. Also, thank you for all the feedback you've been providing, I've been learning quite a bit from it. –  Rodya_ Feb 4 at 16:01

2 Answers 2

up vote 2 down vote

Answers from Gareth Rees to your other questions about selection sort and bubble sort still apply here but it is clear that you tried to take them into account already.

You can loop with for partition in range(1, len(seq)):. Also, it removes the need for an additional variable as it doesn't really matter anymore if you lose the current value of partition : it will have the right value at the beginning of the next iteration anyway.

Here's what you could do :

for p in range(1, len(seq)):
    while p != 0 and seq[p] < seq[p-1]:
        seq[p], seq[p-1] = seq[p-1], seq[p]
        p -= 1
return seq
share|improve this answer
up vote 1 down vote

One thing that can speed up insertion sort is to pull the partition value to the side and slide elements up into the vacancy until the correct location is found, then drop the partition value into that location. This eliminates one of the three assignments in the while loop:

for p in range(1, len(seq)):
    if seq[p] >= seq[p-1]:
        continue
    p_value = seq[p]
    while p != 0 and p_value < seq[p-1]:
        seq[p] = seq[p-1]
        p -= 1
    seq[p] = p_value
return seq

The unit test shows a substantial speed improvement from doing this.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.