which one is faster/easier in sorting? Array or linked list? [closed]

Question

I am coding a project that need to store data either using array or linked list. Later on, the data has to be sorted. I feel like coding array is easier for sorting because we simply swap. For linked List we have to worry(and code) about the pointer and accessing each element is more expensive than array. Am I right?

Answer 1

It depends heavily on your sorting algorithm and what you are sorting. The cost of traversing a linked list is certainly higher than indexing an element in an array. However, if your sorting algorithm involves shifting elements, this can be done in constant time in a linked list (whereas in an array it must be done element by element, copying each one). Swapping elements in a linked list is also constant time (just change the pointers), whereas in an array it will be copying elements (maybe also constant time, depending on your data).

For a set of integers you want to sort using quicksort, it's probably faster to use an array; for a set of large structures you want to sort using selection sort, a linked list will be faster.

Then, there is the question of how you access elements. If your intention in sorting was to access the elements later on by binary search, you'd definitely want to use an array (as binary search is usually slower than linear search on linked lists, unless the linked list is something like a balanced B-tree).

Answer 2

Depending on the kind of sort you'll implement, you'll likely want random access to the elements in your collection. With that in mind, an array is indeed a better choice.

I'll go ahead and guess this is a school/learning project (or else you'd be using pre-existing sort functions, wouldn't you), so the sorting algorithm you choose will have an impact on this decision.

Typically, the fastest sort is quicksort (or mergesort), which benefits from random access (therefore arrays). Your idea about swapping is good too. Usually you want to sort in place and avoid allocating extra memory.