I am working on a list of integers from a file. And I have to use a sorting algorithm to categorize them in descending order. I am familiar with the run time of a few sorting algorithms and I know the use of them is situational. So my question is: What would be the quickest sorting algorithm for a list of ANY size that is already 90% sorted? (in my file I have 10.000 entries but 9.500 of them are already sorted).
Thank you,
The Timsort algorithm as developed for Python, (and now used in Java), has optimisations to deal with partially sorted "runs" built in.
Insertion sort should be fine, if you choose to code it yourself rather than using the language provided sort functions.
Presenting the Python implementation of Insertion Sort.
Program
def InsertionSort(Array):
Total = 0
for i in xrange(1, len(Array)):
j, I, = i - 1, i
while j >= 0 and Array[I] > Array[j]:
Array[I], Array[j] = Array[j], Array[I]
j, I, Total = j - 1, I - 1, Total + 1
print "Insertion Sort Total Operations :", Total
Output
Worstcase
TestArray = range(1, 11)
InsertionSort(TestArray)
Insertion Sort Total Operations : 45
Bestcase
TestArray = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
InsertionSort(TestArray)
Insertion Sort Total Operations : 0
90% Sorted Array
TestArray = [1, 9, 8, 7, 6, 5, 4, 3, 2, 10]
InsertionSort(TestArray)
Insertion Sort Total Operations : 17
Half Sorted Array
TestArray = [10, 9, 8, 7, 6, 1, 2, 3, 4, 5]
InsertionSort(TestArray)
Insertion Sort Total Operations : 10
For its std::sort C++ uses introspective sort, where the array/list is first sorted using quicksort for a certain depth of recursion followed by heapsort. I dunno about 90% but heapsort seems to perform well on already sorted arrays/lists... so I'd recommend you try that.
