|
| 1 | +fromrandomimportrandint |
| 2 | + |
| 3 | + |
| 4 | +classTimSort: |
| 5 | +""" A class to demonstrate Tim Sort """ |
| 6 | + |
| 7 | +def__init__(self,array): |
| 8 | +self.array=array |
| 9 | +self.arrayLength=len(array) |
| 10 | +self.__RUN=32 |
| 11 | + |
| 12 | +definsertionSort(self,arr): |
| 13 | +""" Sorts the given array from given starting index to ending index """ |
| 14 | + |
| 15 | +foriinrange(1,len(arr)): |
| 16 | +currentElement=arr[i] |
| 17 | +j=i-1 |
| 18 | +whilej>=0andarr[j]>currentElement: |
| 19 | +arr[j+1]=arr[j] |
| 20 | +j-=1 |
| 21 | +arr[j+1]=currentElement |
| 22 | + |
| 23 | +returnarr |
| 24 | + |
| 25 | +defmergeRuns(self,arr1,arr2): |
| 26 | +""" Merges the given two arrays: arr1 and arr2 """ |
| 27 | + |
| 28 | +newArray=list() |
| 29 | +lengthOfArr1=len(arr1) |
| 30 | +lengthOfArr2=len(arr2) |
| 31 | + |
| 32 | +# The variable i is used to keep track of the indices of the first array |
| 33 | +# The variable j is used to keep track of the indices of the second array |
| 34 | +# The variable k is used to keep track of the indices of the newArray array which is to be returned |
| 35 | +i,j,k=0,0,0 |
| 36 | + |
| 37 | +whilei<lengthOfArr1andj<lengthOfArr2: |
| 38 | +ifarr1[i]<=arr2[j]: |
| 39 | +newArray[k]=arr1[i] |
| 40 | +k+=1 |
| 41 | +i+=1 |
| 42 | +elifarr1[i]>=arr2[j]: |
| 43 | +newArray[k]=arr2[j] |
| 44 | +k+=1 |
| 45 | +j+=1 |
| 46 | + |
| 47 | +# The below two loops will append any remaining elements left in any of the two arrays. |
| 48 | +whilei<lengthOfArr1: |
| 49 | +newArray.append(arr1[i]) |
| 50 | +i+=1 |
| 51 | + |
| 52 | +whilej<lengthOfArr2: |
| 53 | +newArray.append(arr2[j]) |
| 54 | +j+=1 |
| 55 | + |
| 56 | +returnnewArray |
| 57 | + |
| 58 | +defchangeRun(self,newRun): |
| 59 | +self.__RUN=newRun |
| 60 | + |
| 61 | +defalgorithm(self): |
| 62 | +""" This function will perfom Tim Sort on the given array """ |
| 63 | + |
| 64 | +# Breaking the array into chunks of subarray(RUNS) of size RUN and perfomring insertionSort on them. |
| 65 | +foriinrange(0,self.arrayLength,self.__RUN): |
| 66 | +currentRunElements=self.array[i:i+self.__RUN] |
| 67 | + |
| 68 | +self.array[i:i+ |
| 69 | +self.__RUN]=self.insertionSort(currentRunElements) |
| 70 | + |
| 71 | +temp_runner=self.__RUN |
| 72 | +whiletemp_runner<self.arrayLength: |
| 73 | +foridxinrange(0,self.arrayLength,temp_runner*2): |
| 74 | +firstArray=self.array[idx:idx+temp_runner] |
| 75 | +secondArray=self.array[idx+ |
| 76 | +temp_runner:idx+temp_runner*2] |
| 77 | +self.array[idx:idx+temp_runner* |
| 78 | +2]=self.mergeRuns(firstArray,secondArray) |
| 79 | +temp_runner=self.__RUN*2 |
| 80 | + |
| 81 | +print(f"The sorted array is :{self.array}") |
| 82 | + |
| 83 | +def__repr__(self): |
| 84 | +returnf"Array:{self.array}\nRUN:{self.__RUN}" |
| 85 | + |
| 86 | + |
| 87 | +myArray= [randint(1,100)foriinrange(15)] |
| 88 | +demo=TimSort(myArray) |
| 89 | +print(demo) |
| 90 | +demo.algorithm() |