CODEWITHSUNDEEP
algorithmsorting
Shauna
Shauna

Reputation: 23

Sorting algorithm most suitable for sorting array that is almost sorted

What sorting algorithm would be most suitable to use when sorting an array that is already almost sorted?

Upvotes: 2

Views: 349

Answers (3)

user2566092
user2566092

Reputation: 4661

If you define "almost sorted" as having a low number of pairs of data points that are in reverse order instead of the correct order (e.g., imagine taking a sorted list and then taking disjoint consecutive pairs of data points and reversing them), then a bubble sort will work very well where you make one modification that if you swap two elements, then you keep searching to the left and swapping as long as the neighboring elements are out of order. This will have complexity O(n) if the number of pairs out of order is O(n).

Upvotes: 0

StilesCrisis
StilesCrisis

Reputation: 16300

Insertion sort will work well for almost-sorted data. You get close to optimal results.

Here's a great animation which shows how the sort will perform: http://www.sorting-algorithms.com/insertion-sort

Upvotes: 2

user4843530
user4843530

Reputation:

It depends. Size of array? what does "already almost sorted" mean - as in what percentage of the data is already in sequential order? what is your programming and data storage environment - is the data in memory, a database, a file?

Having said that, you might start by researching Timsort. It is a relatively new sort algorithm that will handle large datasets, taking advantage of "runs" (data already in sort order).

Upvotes: 1

Related Questions