What is sorting ? how can we apply it in array ?
Answers
Answered by
0
Well, we know an array is an indexed series of elements. An array A of size n has elements which are indexed from A[0] through A[n−1]. Such an array doesn't really have any other interesting properties; we can reference a particular element on demand by looking for its index; A[3], for example, if we know that n>3, refers to the fourth element of the array.
A sorted array has a few other interesting properties, and they're quite useful.
First, we can only put items into a sorted array if we know they're comparable. If I have elements p and q, but I can't tell if q>p orq=p or q<p, then I can't put that kind of element into a sorted array.
The next useful attribute of a sorted array is that we ensure the elements are ordered based on that comparison. That is, for any valid index k such that k<n−1, we know that A[k]≤A[k+1].
By induction, we know that for any h and j where h≤j and 0<=h<n and 0<=j<n, we know that A[h]≤A[j].
These properties are useful because they make certain algorithms over the array feasible. For example, if I have an array and I want to know if that array includes a certain element or not but the array is not sorted, I must exhaustively examine each element in the array to see if it contains the element I'm looking for. That means I must make n retrievals from the array, and n comparisons, too.
If I have a sorted array, I have several other options for building an algorithm that tests for the presence in the array. If I start looking at element 0 and move to subsequent elements. Let's index those elements with j.
I start with j=0, so I look at the first element of the array at A[j], which is just A[0]. If I compare the element at A[j] to my candidate k, I can make a decision: if k=A[j], I know I've found my element and I'm done. But if I find that k>A[j], then I know that the element isn't in the array. If k<A[j], then I increment j to the next element. If, after incrementing, j is equal to n, I'm done and I know the element isn't in the array.
Quitting early in the case of k>A[j] saves a lot of time. On average, this algorithm does n/2 comparisons to find the candidate, if the candidate exists in the array.
But we can do even better than that. We can write an algorithm that utilizes the ordering of the array and moves toward the beginning of the array or towards the end of the array based on the comparison. That algorithm is called a "binary search", and can't be applied to an un-sorted array. Binary search requires a sorted array.
A sorted array has a few other interesting properties, and they're quite useful.
First, we can only put items into a sorted array if we know they're comparable. If I have elements p and q, but I can't tell if q>p orq=p or q<p, then I can't put that kind of element into a sorted array.
The next useful attribute of a sorted array is that we ensure the elements are ordered based on that comparison. That is, for any valid index k such that k<n−1, we know that A[k]≤A[k+1].
By induction, we know that for any h and j where h≤j and 0<=h<n and 0<=j<n, we know that A[h]≤A[j].
These properties are useful because they make certain algorithms over the array feasible. For example, if I have an array and I want to know if that array includes a certain element or not but the array is not sorted, I must exhaustively examine each element in the array to see if it contains the element I'm looking for. That means I must make n retrievals from the array, and n comparisons, too.
If I have a sorted array, I have several other options for building an algorithm that tests for the presence in the array. If I start looking at element 0 and move to subsequent elements. Let's index those elements with j.
I start with j=0, so I look at the first element of the array at A[j], which is just A[0]. If I compare the element at A[j] to my candidate k, I can make a decision: if k=A[j], I know I've found my element and I'm done. But if I find that k>A[j], then I know that the element isn't in the array. If k<A[j], then I increment j to the next element. If, after incrementing, j is equal to n, I'm done and I know the element isn't in the array.
Quitting early in the case of k>A[j] saves a lot of time. On average, this algorithm does n/2 comparisons to find the candidate, if the candidate exists in the array.
But we can do even better than that. We can write an algorithm that utilizes the ordering of the array and moves toward the beginning of the array or towards the end of the array based on the comparison. That algorithm is called a "binary search", and can't be applied to an un-sorted array. Binary search requires a sorted array.
Similar questions