Sorting Techniques
Explanation of various Sorting Algorithms
Link~1
Insertion Sort:
public class InsertionSort {
public static void main(String[] args) {
int arr[]={4,3,2,7,8,1};
for (int i=1;i<arr.length;i++ ) {
int hole=i;
int value=arr[i]
int value=arr[i]
while(hole>0 && arr[hole-1]>value){
arr[hole]=arr[hole-1];
hole=hole-1;
}
arr[hole]=value;
arr[hole]=value;
}
for (int i=0;i<arr.length ;i++ ) {
System.out.println(arr[i]);
}
}
}
- Better than Bubble sort and Selection Sort
- Divide the array into two subsets,one part is sorted and another part is unsorted
- Initially the element at 0 index is a part of sorted subset
- Now take one element from unsorted array and move to sorted array.
- When the array is sorted,then the while loop does not get executed and thus the time complexity is O(n),Which is the best case.
- When the array is reverse,for each iteration that many number of shifts will be performed,thus O(n^2) is the worst case
- If the list is almost sorted, then Insertion Sort performs in linear O(n) time. Contrast this with Selection Sort, which always performs in quadratic time.
Subscribe to:
Post Comments
(
Atom
)
No comments :
Post a Comment