Already nearly sorted array

Question

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

Pick the 4 out-of-order elements, sort them, merge with the rest of the elements. (or perform an insertion-sort variant) — wildplasser, Dec 07 '16 at 19:17
Look at [adaptive sorts](https://en.wikipedia.org/wiki/Adaptive_sort) like Smoothsort and hybrids like Timsort — BeyelerStudios, Dec 07 '16 at 19:20

score 1 · Answer 1 · answered Dec 07 '16 at 19:22

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

Best solution posted so far. – trincot Dec 07 '16 at 19:26 — trincot, Dec 07 '16 at 19:26

score 0 · Answer 2 · answered Dec 07 '16 at 19:10

0

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.

answered Dec 07 '16 at 19:10

DonO

1,030
1
13
27

score 0 · Answer 3 · edited May 23 '17 at 12:24

0

For smaller arrays, almost all sorting techniques roughly have the same running time. In fact, if the array is partially sorted, insertion sort works the best. You can see a gif comparison here.

Also, this question has already been answered here

edited May 23 '17 at 12:24

Community

1
1

answered Dec 07 '16 at 19:12

daBigBug

343
2
11

Already nearly sorted array

3 Answers3