Insertion Sort

In this sorting algorithm, we check every element with it's previous element. If it is lesser than the previous element than we swap. We keeping swapping until the element achieves it's proper place.
It's time complexity is O(n^2).
In case the given list is already sorted, this algorithm works very fast.
A simple code implementation is:-
def insertionSort(l):
  for i in range(len(l)):
    pos=i
    while(l[pos]>l[pos-1] and pos>0):
      (l[pos],l[pos-1])=(l[pos-1],l[pos])
      pos-=1
  return l

Comments

Post a Comment

Popular posts from this blog

Rotating a list

Question. A list rotation consists of taking the first element and moving it to the end. For instance, if we rotate the list  [1,2,3,4,5] , we get  [2,3,4,5,1] . If we rotate it again, we get  [3,4,5,1,2] . Write a Python function  rotatelist(l,k)  that takes a list  l  and a positive integer  k  and returns the list  l  after  k  rotations. If  k  is not positive, your function should return  l  unchanged. Note that your function should not change  l  itself, and should return the rotated list. Here are some examples to show how your function should work. >>> rotatelist([1,2,3,4,5],1) [2, 3, 4, 5, 1] >>> rotatelist([1,2,3,4,5],3) [4, 5, 1, 2, 3] >>> rotatelist([1,2,3,4,5],12) [3, 4, 5, 1, 2] Solution:- If the number of times to be rotated is greater than the length of list then we start iterating from n % size value till the end and append the el...
Read more

Prime partitioning a number

Question:- A positive integer m can be partitioned as primes if it can be written as p + q where p > 0, q > 0 and both p and q are prime numbers. Write a Python function  primepartition(m)  that takes an integer  m  as input and returns  True  if  m  can be partitioned as primes and  False  otherwise. (If  m  is not positive, your function should return  False .) Here are some examples of how your function should work. >>> primepartition(7) True >>> primepartition(185) False >>> primepartition(3432) True Solution:- The idea behind the solution is that I'm computing all the prime numbers till the given number and appending to a list . Then I'm iterating over the list and subtracting it from the given number, if the subtracted value is prime then I'm returning True, otherwise after the loop ends returning False def primes (n): l = [] for i in range ( 2 ,n)...
Read more

Sum of prime numbers in list

Question:-  Write a function sumprimes(l) that takes as input a list of integers and returns the sum of all the prime numbers in l. Here are some examples to show how your function should work. >>> sumprimes([3,3,1,13]) 19 >>> sumprimes([2,4,6,9,11]) 13 >>> sumprimes([-3,1,6]) 0 Solution:- def prime (a): for j in range ( 2 ,a): if a % j == 0 : return False if a == 1 : return False if a <= 0 : return False return True def sumprimes (l): sum = 0 for i in range ( 0 , len (l)): if prime(l[i]): sum = sum + l[i] return sum
Read more