You know that searching and sorting are some of the most commonly used operations,and keeping an eye on it's complexity is essentially very important.You can easily perform this operation but let us look into other ways of doing it more optimally.
Lets start with searching for an item in an array.
-->LAY MAN SEARCH:
How is this performed??You keep searching for the element until u find it.What is its best case complexity o(1)-If the search element is your first element.
Worst case complexity o(n) ie.if the search element is the last one.
-->Binary Search:This is performed only in the sorted list.You compare the search element with the middle element
> If both are equal return the position
>If the middle element is less than the search element select the right side and proceed the same steps else move to the left and proceed the same steps.
Because the middle element is considered ,the average complexity is only o(log n).
This is not efficient with linked lists because traversing to the middle element each and every time is wastage of time and efficiency.
2)This is done till the last element,2nd and 3rd are compared,3rd and 4th and so on..
3)This is again carried out n no of times or till there are no more swaps left.
2)Next 3 elements are considered and are put in the sorted order.
3)Similar procedure is carried on for n elements till they are sorted.
2)Smallest element frm an array 'a' is put in another array 'b' adn removed in the 1st array.
3)Then the next smallest element is selected from 'a' and put in 'b'.This process is repeated for n elements.
The above 2 sorts have a complexity of o(n^2)
Other better sorts are
2)Put all element lesser than that to the left of the pivot and other elements to the right.
3)Once this is done again find the pivot element in this new rearranged array and repeat the process in step 2.Continue this till the array is sorted
Average case Complexity for this is o(nlogn) which is much better compared to n^2.
2)We keep on dividing the total elements into 2 sets and this process is continued till you reach the individual elements and again while merging it is merged in the sorted order.
Complexity is O(nlog n).
>It is not good to follow this method of sort if the values are stored in a linked list.
2)Number the elements from 1 to seperation and repeat this for all all n elements.
3)Compare the 1st element and seperation+1th element,swap if 1st ele is greater.
4)Continue this for 0 to n-seperation elements.
5)REcompute seperation and repeat the other steps.
2)Remove this and put it in an array and agin create a minheap by replacing the last child for the root,again remove the root and put it in the array.
3)Repeat this for n elements.
AUDIO BLOG DATA STRUCTURES AND SORTING:http://soundcloud.com/ronamaria/data
- Sourcebits University
Cloud Computing
www.sourcebits.com
Lets start with searching for an item in an array.
-->LAY MAN SEARCH:
How is this performed??You keep searching for the element until u find it.What is its best case complexity o(1)-If the search element is your first element.
Worst case complexity o(n) ie.if the search element is the last one.
-->Binary Search:This is performed only in the sorted list.You compare the search element with the middle element
> If both are equal return the position
>If the middle element is less than the search element select the right side and proceed the same steps else move to the left and proceed the same steps.
Because the middle element is considered ,the average complexity is only o(log n).
This is not efficient with linked lists because traversing to the middle element each and every time is wastage of time and efficiency.
Types of SORTING!
BUBBLE SORT:
1)The 1st element is compared with the 2nd and if its greater it is swapped.2)This is done till the last element,2nd and 3rd are compared,3rd and 4th and so on..
3)This is again carried out n no of times or till there are no more swaps left.
INSERTION SORT:
1)First 2 elements are considered and they are sorted.2)Next 3 elements are considered and are put in the sorted order.
3)Similar procedure is carried on for n elements till they are sorted.
SELECTION SORT:
1)not an inplace sort2)Smallest element frm an array 'a' is put in another array 'b' adn removed in the 1st array.
3)Then the next smallest element is selected from 'a' and put in 'b'.This process is repeated for n elements.
The above 2 sorts have a complexity of o(n^2)
Other better sorts are
QUICKSORT:
1)Select the pivot element2)Put all element lesser than that to the left of the pivot and other elements to the right.
3)Once this is done again find the pivot element in this new rearranged array and repeat the process in step 2.Continue this till the array is sorted
Average case Complexity for this is o(nlogn) which is much better compared to n^2.
MERGE SORT:
1)Pucca Divide and Conquer Strategy.2)We keep on dividing the total elements into 2 sets and this process is continued till you reach the individual elements and again while merging it is merged in the sorted order.
Complexity is O(nlog n).
>It is not good to follow this method of sort if the values are stored in a linked list.
SHELL SORT
1)seperation=n/22)Number the elements from 1 to seperation and repeat this for all all n elements.
3)Compare the 1st element and seperation+1th element,swap if 1st ele is greater.
4)Continue this for 0 to n-seperation elements.
5)REcompute seperation and repeat the other steps.
HEAPSORT:
1)construct a min heap by precolating the smaller element towards the root.2)Remove this and put it in an array and agin create a minheap by replacing the last child for the root,again remove the root and put it in the array.
3)Repeat this for n elements.
AUDIO BLOG DATA STRUCTURES AND SORTING:http://soundcloud.com/ronamaria/data
- Sourcebits University
Cloud Computing
www.sourcebits.com
No comments:
Post a Comment