We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Sorting
  4. Insertion Sort Advanced Analysis
  5. Discussions

Insertion Sort Advanced Analysis

Sort by

recency

|

357 Discussions

|

  • jjeerreemmyy
     + 0 comments

    Curious why this solution in Python gets a runtime error for about half of the test cases - I am guessing it's something to do with there being an earlier potential exit point for the loop than simply (s < lenA) or that I shouldn't be using functions like index or min in the solution and instead stick to primitive operations. I'm pretty much a novice, so any advice would help:

    def insertionSort(arr):
    # Write your code here
    moves = 0
    s = 0
    a = arr[:]
    lenA = len(arr) - 1
    while s < lenA:
        p = a.index(min(a))
        a.pop(p)
        moves += p
        s += 1
    return moves

  • awasthi_piyush8
     + 0 comments

    Ruby solution:

    def merge(arr, temp_arr, left, mid, right)
    i = left    # Starting index for left subarray
    j = mid + 1 # Starting index for right subarray
    k = left    # Starting index for sorted subarray
    inv_count = 0
  
    while i <= mid && j <= right
      if arr[i] <= arr[j]
        temp_arr[k] = arr[i]
        i += 1
      else
        temp_arr[k] = arr[j]
        inv_count += (mid - i + 1) # Count inversions
        j += 1
      end
      k += 1
    end
  
    while i <= mid
      temp_arr[k] = arr[i]
      i += 1
      k += 1
    end
  
    while j <= right
      temp_arr[k] = arr[j]
      j += 1
      k += 1
    end
  
    (left..right).each do |idx|
      arr[idx] = temp_arr[idx]
    end
  
    inv_count
  end
  
  def merge_sort(arr, temp_arr, left, right)
    inv_count = 0
    if left < right
      mid = (left + right) / 2
  
      inv_count += merge_sort(arr, temp_arr, left, mid)
      inv_count += merge_sort(arr, temp_arr, mid + 1, right)
  
      inv_count += merge(arr, temp_arr, left, mid, right)
    end
    inv_count
  end
  
  # Wrapper to call merge sort
  def count_inversions(arr)
    temp_arr = Array.new(arr.length)
    merge_sort(arr, temp_arr, 0, arr.length - 1)
  end


def insertionSort(arr)
    count = count_inversions(arr)
end

  • rizwan_string00
     + 0 comments

    Just have modify mergesort and count the inversion(shift) .

    def insertionSort(arr):#by using mergesort count = 0 if len(arr) > 1: mid = len(arr)//2 left_list = arr[:mid] right_list = arr[mid:] count = count + insertionSort(left_list) count = count + insertionSort(right_list) count = count + merge(left_list,right_list,arr) return count def merge(left_list,right_list,arr): i=0 j=0 k=0 count = 0 mid = len(arr)//2 while i

  • alfej_fakir9
     + 0 comments

    what the hell , if you are getting wrong answer and if you think your code is correct , then the convert the integer to long in pre written code , they said that the range is in integer's range but it isn't.

  • dangminhhoangdz
     + 0 comments

    The provided template should not expect us to return int. Imagine the case n, n-1, n-2, n-3, ..., 1 , it will require us n*(n - 1) / 2 swap aka will overflow if you use int for n = 1e5. Converted the return type for the provided code to long solved the problem