It is well accepted that processing sorted arrays is easier and efficient. What would be the pedagogical approach to explain how and why it is more efficient to process sorted collections than unsorted collections.
$\begingroup$
$\endgroup$
1
-
$\begingroup$ Hi m__, welcome to Computer Science Educators. What do you mean by "process", and what age/level are you teaching to? Without some further details, I'm afraid @KimNguyễn's response of "no it's not" is about as far as we can help you. $\endgroup$– Ben I. ♦Dec 3, 2018 at 11:33
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
8
First, it is not "well accepted" that processing sorted array is more efficient. It depends on what you do. If you spend your time inserting, for instance, then sorted arrays are not necessarily a good choice. You are better off inserting at the end (say if you have resizable arrays such as Vector<X> or ArrayList<X> in Java), and then sort afterwards (you'll pay $O(N*log(N))$ instead of $O(N²)$).
It is true that if you don't have insertions (or very few insertions with respect to searching or other operations for instance) then it is more efficient. If you want to find an element in a sorted array, you can use binary search which is $O(log(N))$ while if your array is not sorted you have to scan the whole thing which is $O(N)$.
Likewise if you want to perform set operations on two sorted arrays (intersection, union, difference), then doing so on sorted Arrays is linear. If they are not sorted you will be either quadratic (naive algorithm) or have to use an auxiliary data structure (such as a hash table).
Sorted arrays have the same complexity for these operations than the more involved tree structures (AVL or red-black trees) and they have a very compact and simple representation. But you pay the price that insertion is more expensive, since it has to maintain the order of elements.
-
$\begingroup$ Inserting in a sorted list can be done in O(n), in fact this is an example where a sorted list helps. Only Insertion Sort takes O(n²) $\endgroup$– OBuDec 3, 2018 at 11:32
-
1$\begingroup$ That's my point. If your use case is to insert a lot of values, and have the result sorted at the end it is better to insert at the end of the array (constant time for the structures I mention) and sort everything afterwards. Other wise the whole process takes O(N²) (N is the number of elements inserted). Of course the insertion of a single element is linear. Also, OP asks specifically about arrays. In that case, insertion also needs to move the rest of the elements to the right (which is also linear). So again, it all depends on your use case. $\endgroup$ Dec 3, 2018 at 11:50
-
$\begingroup$ @OBu, inserting in a sorted linked list can be done in O(n), but "List" does not always mean LinkedList. $\endgroup$ Dec 3, 2018 at 19:14
-
$\begingroup$ @SolomonSlow The same holds true for an array implementation. $\endgroup$– OBuDec 3, 2018 at 21:32
-
1$\begingroup$ @OBu inserting n element in to a list $O(n^2)$. Kim is discussing inserting lots of elements, not just one. $\endgroup$ Dec 5, 2018 at 8:35
$\begingroup$
$\endgroup$
I would do it unplugged. Give then a sorted stack of cards, get them to find a number. Repeat with an unsorted list.
Ensure that there are gaps, not a sequence, but sorted. I got caught out with this, pupils could find a card in a sequence in $O(1)$.
answered Dec 5, 2018 at 8:40
$\begingroup$
$\endgroup$
If an array is unsorted, and you want to check an item for membership in it, that is O(n) time procedure. If it is sorted, you can use divide-and-conquer to do this task in O(log(n) time.
