Skip to main content

Overview of time and space complexity for sorting algorithm


Bubble sort : In bubble sort ,we will select the 1st element and compare with all the remaining element, same process we will continue for all the elements as we are traveling the whole Array 2 times except the element which we have selected to compare with other elements but still it will be consider as n time.
   So time complexity for bubble sort will be O(n^2).
        space complexity for bubble sort will be O(1).

Selection sort : In selection sort we will divide the Array in 2 parts , sorted and unsorted and select the min element from unsorted and will copy to sorted array.
     Time Complexity for selection sort also is O(n^2).
     space complexity for bubble sort will be O(1).

Insertion sort :  In insertion sort, Same process like selection sort , we will divide the array in sorted and unsorted array and we will select element from unsorted array and will insert it into sorted array at its proper position.
   Time Complexity for Insertion sort also is O(n^2).
   space complexity for bubble sort will be O(1).

Merge sort : In merge sort we will divide the array from middle recursively  until we have only one element in sub-array. After that we will merge sub-array in ascending order.
    Time complexity for merge sort will be O(nlogn) as we are splitting the array from middle so each time it's getting half so for that  it will be log(n) and while merging we are traversing the whole array so for that it will be O(n).
     So after combining both  time complexity will be O(n)+O(logn)= O(nlogn)
     space complexity will be O(n) as we need a extra same size array to hold the unsorted array.

Quick sort : In quick sort, we will consider a pivot element and divide the array so that all the lesser element will be in left side of pivot element while all the greater element will be in right side.
   This process we will continue recursively until array is fully sorted.
     Time complexity will beO(nlogn) but in worst case when elements are in sorted order time complexity will become O(n^2) as in each call only one element will be consider as sorted and for rest again we need to follow same process.
     space complexity will be O(1)
   
Please have a look to the  source code of all sorting method from below link.

Labels:

Comments

Post a Comment

Popular posts from this blog

Java Program : Writing First Java Factorial Program with explanation

 NAMING CONVENTION IN JAVA : Java is an object oriented programming language , we can relate it to real life object like i mapped Java with human in my previous post JAVA OVERVIEW (SESSION 1)  and represent human properties like body parts as properties in Java and Human can dance , drive , walk , run these can be mapped as Behaviour in java.    Now To represent properties and behaviour in java , there are some standard naming conventions we should follow. Class name should always starts with Uppercase letter like class Student { //Code to be executed } Properties or any kind of variables should starts from lower case and afterwards every first letter of each next word should be in Upper case . like class Student { int studentId ; String studentName ; //Code to be executed } Methods name should also starts from lower case and afterwards every first letter of each next word should be in Upper case . like class Student { int studentId ; String studentName ;
2 comments
Read more

OOPS Concept in Java : ENCAPSULATION

OOPS Concept in Java : ENCAPSULATION   This OOPS concept can be used to make things simpler in case of software development . Main purpose of this concept is to hide the properties of any class and give access to fetch and modified based on business criteria.  A simple example can be a POJO ( Plain Old Java Object) in which all the properties of a class can be private and through getter and setter method of properties we can fetch and update the properties of Object. So instead of having direct access to properties we have created 2 methods to make the CLASS things encapsulated in single unit while access to it is via 2 public methods.   Just consider we have requirement that once the object is created its value should not be changed then simplest way to achieve this  can be done by just removing setter method and we will keep only getter methods to access Object properties . In this case after Object creation whatever the value of Object properties has been initialised it will b
Post a Comment
Read more

OOPS Concept in Java : POLYMORPHISM

 POLYMORPHISM IN JAVA :  Polymorphism means mutiple forms of Single reference. And to understand in simple way just take an example from my previous post of OOPS CONCEPT IN JAVA : INHERITANCE  , I request you guys to go through this link before proceding here. So in this post I have created a method called sum() in PARENT class which has been used by CHILD class without writing same sum() method in CHILD class. This was possible becuase of INHERITANCE concept in java.  But what if CHILD class is not satisfied with PARENT sum() and CHILD class wants to improve it like by adding some message before the calculation. To do this we have another OOPS CONCEPT IN JAVA i.e POLYMORPHISM and by applying this logic we can make same sum() method behvae differently based on Object. As I mentioned earlier POLYMORPHISM means different forms and same has been achieved here by calling same sum() method but the output is different based on Object on which it has been called. If Object is of PARENT
Post a Comment
Read more