What do you understand by 'Sorting' of records? What is its significance?
Answers
Answered by
1
Sorting is critical to many tasks. I will point out just a few, but they are characteristic of the kinds of things you use sorting for.
Example 1: Given a set of a million data records, remove or merge the duplicates.
If the data records are sorted by the main uniqueness criterion, removing the duplicates can be done easily by traversing the list and finding groups of consecutive records that compare equal using that criterion.
Example 2: Compare two large sets of items and find out where they differ.
Let’s try this by hand. Here are two randomly-ordered lists of 15 numbers:
Can you tell me which number from list 1 is missing from list 2 and vice-versa? Pretty difficult, huh? And that’s with only 15 numbers.
Now, let’s try again. Here we have the same two lists in sorted order:
It’s not difficult to go down the lists in parallel and pick out the differences, is it? The same is true for a computer program. Using big-O notation, comparing every element of one list with every element of another list is an O([math]n^2[/math]) operation whereas comparing the sorted lists is an O(n) operation. That means that the cost of comparing the unsorted lists grows with the square of the number of elements, whereas the cost of comparing the sorted lists grows linearly. Think about what that means when you consider a list of a million elements. The same big-O formulas apply to Example 1.
Example 3: Using the same lists as in Example 2, find out if the number 5 appears in each list. For the unsorted lists, you have to look at every element until you either find the 5 or reach the end of the list. On average, for a list of
n elements, it will take
[math]n/2[/math] comparisons to find the thing you’re searching for if it exists and n comparisons if it does not exist. However, with the sorted list, you can use binary search: look at the middle element, if it’s more than 5, keep looking in the first half of the list; if it’s less than 5, keep looking in the second half of the list; keep dividing the list by half until you find it or you have nothing left. Using binary search, you are guaranteed to find your answer or fail in [math]log2(n)[/math] comparisons (4 comparisons max for our list of 15 elements). Next time you use a (paper) dictionary, consider how hard it would be to use if the words were not sorted alphabetically.
Of course, in order to get these performance benefits, you have to pay the cost of sorting the list, which is typically [math]O(n*log(n))[/math], though some sorting algorithms are faster for certain kinds of data. However, it is very common to build up lists and re-used them often, without changes. In that case, you pay the cost of sorting only once (or occasionally), but get the benefits over and over again.
Example 1: Given a set of a million data records, remove or merge the duplicates.
If the data records are sorted by the main uniqueness criterion, removing the duplicates can be done easily by traversing the list and finding groups of consecutive records that compare equal using that criterion.
Example 2: Compare two large sets of items and find out where they differ.
Let’s try this by hand. Here are two randomly-ordered lists of 15 numbers:
Can you tell me which number from list 1 is missing from list 2 and vice-versa? Pretty difficult, huh? And that’s with only 15 numbers.
Now, let’s try again. Here we have the same two lists in sorted order:
It’s not difficult to go down the lists in parallel and pick out the differences, is it? The same is true for a computer program. Using big-O notation, comparing every element of one list with every element of another list is an O([math]n^2[/math]) operation whereas comparing the sorted lists is an O(n) operation. That means that the cost of comparing the unsorted lists grows with the square of the number of elements, whereas the cost of comparing the sorted lists grows linearly. Think about what that means when you consider a list of a million elements. The same big-O formulas apply to Example 1.
Example 3: Using the same lists as in Example 2, find out if the number 5 appears in each list. For the unsorted lists, you have to look at every element until you either find the 5 or reach the end of the list. On average, for a list of
n elements, it will take
[math]n/2[/math] comparisons to find the thing you’re searching for if it exists and n comparisons if it does not exist. However, with the sorted list, you can use binary search: look at the middle element, if it’s more than 5, keep looking in the first half of the list; if it’s less than 5, keep looking in the second half of the list; keep dividing the list by half until you find it or you have nothing left. Using binary search, you are guaranteed to find your answer or fail in [math]log2(n)[/math] comparisons (4 comparisons max for our list of 15 elements). Next time you use a (paper) dictionary, consider how hard it would be to use if the words were not sorted alphabetically.
Of course, in order to get these performance benefits, you have to pay the cost of sorting the list, which is typically [math]O(n*log(n))[/math], though some sorting algorithms are faster for certain kinds of data. However, it is very common to build up lists and re-used them often, without changes. In that case, you pay the cost of sorting only once (or occasionally), but get the benefits over and over again.
Anonymous:
make it little bit compact
ok thankyou
Similar questions