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)
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.
Comments
Post a Comment