Compare performance of Quick Sort vs Insertion Sort — HackerRank

The running time of Quicksort will depend on how balanced the partitions are. If you are unlucky and select the greatest or the smallest element as the pivot, then each partition will separate only one element at a time, so the running time will be similar to Insertion Sort.

However, Quicksort will usually pick a pivot that is mid-range, and it will partition the array into two parts. Let's assume Partition is lucky and it always picks the median element as the pivot. What will be the running time in such a case?

Running Time of Recursive Methods
Quicksort is a recursive method, so we will have to use a technique to calculate the total running time of all the method calls. We can use a version of the "Recursion Tree Method" to estimate the running time for a given array N of elements.

Each time partition is called on a sub-array, each element in the sub-array needs to be compared to the pivot element. Since all the sub-arrays are passed to partition, there will be N total operations for each level of the tree.

Solution

# Insertion sort Swaps
def insertion_sort(arr):
    n = len(arr)
    counter_for_swaps = 0
    for i in range(1, n):
        val = arr[i]
        j = i-1

        while(j >= 0 and arr[j] > val):
            arr[j+1] = arr[j]
            counter_for_swaps += 1
            j -= 1

        arr[j+1] = val
    # print(*arr)
    return counter_for_swaps

class Insertion:
    def __init__(self):
        self.count=0
    def insertionsort(self,a):
        for i in range(1,len(a)):
            key=a[i]
            j=i-1
            while j>=0 and a[j]>key:
                self.count+=1
                a[j+1]=a[j]
                j-=1
            a[j+1]=key
        return self.count

class QuickSort:
    def __init__(self):
        self.count=0
def swap(self,arr,i,j):
        temp=b[j]
        b[j]=b[i]
        b[i]=temp
        return arr
    def partition(self,a,start,end):
        pivot=end
        pindex=start
        for i in range(start,end):
            if a[i] <= a[pivot]:
                self.swap(a,i,pindex)
                self.count+=1
                pindex+=1
        self.count+=1
        self.swap(a,pindex,pivot)
        return pindex
    def quicksort(self,a,s,e):
        if s<e:
            pIndex=self.partition(a,s,e)
            self.quicksort(a, s, pIndex-1)
            self.quicksort(a, pIndex+1, e)
        return self.count
import copy    
if __name__ == '__main__':
    N = int(input())
    original = list(map(int,input().split()))
    duplicate = copy.deepcopy(original)

    insertion_counter_for_swaps = insertion_sort(original)
    # print(insertion_counter_for_swaps)

    # Quicky
    quicksort=QuickSort()
    start = 0
    end = N -1
    quicksort_counter_for_swaps = quicksort.quicksort(duplicate, start, end)
    print(insertion_counter_for_swaps - quicksort_counter_for_swaps)

Cases and solutions

A. Case 1

Input
7
1 3 9 8 2 7 5
Output
1

B. Descending array ( insertion sort performs bad)

Input
10
10 9 8 7 6 5 4 3 2 1
Output
16

E. Ascending array (quicksort performs bad)

Input
10
1 3 4 5 2 7 8 9 6 10
Output
-16

C. Quicksort has 2432 less swaps for the same problem, Insertion sort performs poorly

Input
100
406 157 415 318 472 46 252 187 364 481 450 90 390 35 452 74 196 312 142 160 143 220 483 392 443 488 79 234 68 150 356 496 69 88 177 12 288 120 222 270 441 422 103 321 65 316 448 331 117 183 184 128 323 141 467 31 172 48 95 359 239 209 398 99 440 171 86 233 293 162 121 61 317 52 54 273 30 226 421 64 204 444 418 275 263 108 10 149 497 20 97 136 139 200 266 238 493 22 17 39
Output
2432

D. Quicksort has 38608 less swaps for the same problem, Insertion sort performs poorly

Input
400
193 710 -326 -212 630 434 -378 728 25 702 -324 719 -546 -754 -256 -254 268 -718 -145 -28 12 125 7 -565 54 594 301 -267 776 532 141 -555 -453 663 -556 -607 58 734 584 -632 202 -304 460 -405 17 -97 399 -551 273 400 298 699 -472 275 16 -741 623 -78 768 -421 271 -264 223 -288 239 -502 518 -337 -450 539 327 77 285 73 784 778 -196 -707 -174 654 190 683 375 744 40 749 133 -122 752 404 -34 456 -384 671 -255 -745 496 626 -352 347 -364 -563 515 -321 -382 389 -16 348 -419 -370 645 648 -234 -676 799 138 -739 -592 165 659 13 -475 79 -553 -353 -169 134 513 -641 151 535 325 259 -672 733 -376 603 -580 -714 546 -107 439 -306 462 -432 560 -48 8 -769 -363 -360 -47 -435 -94 480 721 -599 -493 -733 -69 219 674 -751 419 -24 323 -574 50 -679 670 558 310 -26 413 361 -355 694 -348 -70 -215 -204 -708 -478 100 438 368 390 -618 533 262 152 -722 145 -689 -600 762 -422 43 -247 -216 -379 321 526 -396 716 452 790 83 785 493 -765 553 -411 -33 -184 569 743 -703 -383 89 -65 -500 345 -428 -38 46 647 724 -30 364 -239 -68 163 32 740 -316 -644 -698 -305 206 -488 -111 -40 -209 -762 382 295 741 -180 291 365 -654 -731 177 -294 -498 -275 673 747 -685 -506 218 -12 -198 -137 -572 635 -307 281 -5 -311 566 508 381 199 672 -102 617 108 -621 393 94 720 66 -385 -150 144 -388 505 150 342 -627 588 -142 405 472 -486 629 482 712 498 -281 510 286 440 380 605 -242 -577 751 111 -681 476 258 367 -64 -445 -540 -214 409 -162 781 38 -690 353 486 -530 633 339 -323 -717 -328 360 -159 611 478 451 -300 668 -51 461 48 49 658 -544 112 -783 127 -331 -394 146 294 753 -227 436 320 -158 -798 -634 175 -371 -266 408 166 -425 178 -277 -408 507 -31 -315 -289 -244 -119 -521 -318 -343 524 -582 -25 171 764 -128 242 184 -766 -293 -367 -423 -271 -132 512 544 -206 -648 331 -192 -138 665 29
Output
38608