Hello everybody I would like to ask for your opinion. What algorithm would you advice for sorting arrays A with most four numbers that are in wrong place and obtain an efficient asymptotic running time? I was thinking for an insertion sort, but is there something better if there are at most four elements? Thanks in advance
2
-
Pick the 4 out-of-order elements, sort them, merge with the rest of the elements. (or perform an insertion-sort variant)wildplasser– wildplasser2016-12-07 19:17:41 +00:00Commented Dec 7, 2016 at 19:17
-
Look at adaptive sorts like Smoothsort and hybrids like TimsortBeyelerStudios– BeyelerStudios2016-12-07 19:20:57 +00:00Commented Dec 7, 2016 at 19:20
Add a comment
|
3 Answers
if the array has at most 4 elements in wrong place, the insertion sort (with binary search implementation) can do the job well, but the best thing to do is get all wrong elements and sort them, for example
1 2 A 4 B 6 C 7
if A, B and C are wrong, you can just sort them and realloc into the array:
1 2 C 4 A 6 B 7
and as there are just a few elements, you can build an array with them and use selection sort and put them back in the right place on the original array
1 Comment
trincot
Best solution posted so far.
Given the size of the array I don't think the choice of algorithm would make a difference. I would say quick sort. Pick the second number as a pivot and go from there.
