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

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

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

Alternating prime and square

Question:- Write a Python function  squareprime(l)  that takes a nonempty list of integers and returns  True  if the elements of  l alternate between perfect squares and prime numbers, and returns  False  otherwise. Note that the alternating sequence of squares and primes may begin with a square or with a prime. Here are some examples to show how your function should work. >>> primesquare([4]) True >>> primesquare([4,5,16,101,64]) True >>> primesquare([5,16,101,36,27]) False Solution:- import math def prime_check (n): flag = 0 for i in range ( 2 ,n - 1 ): if n % i == 0 : flag = 1 if flag == 0 : return True else : return False def is_square (n): if math . sqrt(n) % 1 == 0 : return True else : return False def primesquare (l): flag = 0 if len (l) == 1 : if is_square(l[ 0 ]) or prime_check(...
Read more