정렬 알고리즘 - 스왑 및 비교 카운터

Question

내 작업은 알고리즘에서 비교 및 ​​스왑 수를 찾는 것입니다. 인터넷에서 여러 가지 방법을 시도했지만 올바른지 확신 할 수 없습니다. 누군가가 내 변수의 위치를 ​​변경하면 (또는 모든 것이 올바른 경우가 아니라면) 좋을 것입니다. 코드는 설명이 필요하므로 추가 설명은 필요하지 않습니다.

def insertionSort(array): 
    numberOfComp = 0 
    numberOfSwap = 0 
    for index in range(1,len(array)): 
     curr = array[index] 
     position = index 
     numberOfComp += 1 
     while position > 0 and array[position-1] > curr: 

      array[position] = array[position-1] 
      position = position - 1 
      numberOfSwap += 1 
      numberOfComp += 1 
     array[position] = curr 

    complexityOfInsertion.append(numberOfComp) 
    swapsOfInsertion.append(numberOfSwap) 
    return array 



def quickSort(array): 
    global numberOfCompQuick 
    global numberOfSwapsQuick 

    less = [] 
    equal = [] 
    greater = [] 

    if len(array) > 1: 
     pivot = array[int(len(array)/2)] 

     for x in array: 
      if x < pivot: 
       less.append(x) 
      if x == pivot: 
       equal.append(x) 
      if x > pivot: 
       greater.append(x) 
      numberOfCompQuick += 1 
     numberOfSwapsQuick +=1 
     # Don't forget to return something! 
     return quickSort(less)+equal+quickSort(greater) #the + operator to join lists 

    else: #when only have one element in array, just return the array. 
     return array 



def merge(a,b): 
    """ Function to merge two arrays """ 
    global numberOfCompMerge 
    global numberOfSwapsMerge 
    c = [] 
    while len(a) != 0 and len(b) != 0: 
     numberOfCompMerge += 1 
     if a[0] < b[0]: 
      c.append(a[0]) 
      a.remove(a[0]) 

     else: 
      c.append(b[0]) 
      b.remove(b[0]) 
      numberOfSwapsMerge += 1 
    if len(a) == 0: 
     c += b 
     numberOfSwapsMerge += 1 
    else: 
     numberOfSwapsMerge += 1 
     c += a 
    return c 

# Code for merge sort 

def mergeSort(array): 
    """ Function to sort an array using merge sort algorithm """ 
    #global numberOfCompMerge 
    if len(array) == 0 or len(array) == 1: 
     return array 
    else: 
     middle = int(len(array)/2) 
     a = mergeSort(array[:middle]) 
     b = mergeSort(array[middle:]) 
     return merge(a,b) 

Answer 1

def insertionSort(array): 
    numberOfComp = 0 
    numberOfSwap = 0 
    for index in range(1,len(array)): 
     curr = array[index] 
     position = index 
     if position > 0: numberOfComp += 1 
     while position > 0 and array[position-1] > curr: 
      array[position] = array[position-1] 
      position = position - 1 
      numberOfSwap += 1 
      if position > 0: numberOfComp += 1 
     array[position] = curr 
     numberOfSwap += 1 

    complexityOfInsertion.append(numberOfComp) 
    swapsOfInsertion.append(numberOfSwap) 
    return array 



def quickSort(array): 
    global numberOfCompQuick 
    global numberOfSwapsQuick 

    less = [] 
    equal = [] 
    greater = [] 

    if len(array) > 1: 
     pivot = array[int(len(array)/2)] 

     for x in array: 
      if x < pivot: 
       less.append(x) 
      if x == pivot: 
       equal.append(x) 
      if x > pivot: 
       greater.append(x) 
      numberOfCompQuick += 3 #can prior code to reduce this, but I'm only fixing the comp and swap counters 
     numberOfSwapsQuick += 1 
     # Don't forget to return something! 
     return quickSort(less)+equal+quickSort(greater) #the + operator to join lists 

    else: #when only have one element in array, just return the array. 
     return array 



def merge(a,b): 
    """ Function to merge two arrays """ 
    global numberOfCompMerge 
    global numberOfSwapsMerge 
    c = [] 
    while len(a) != 0 and len(b) != 0: 
     numberOfCompMerge += 1 
     if a[0] < b[0]: 
      c.append(a[0]) 
      a.remove(a[0]) 
     else: 
      c.append(b[0]) 
      b.remove(b[0]) 
     numberOfSwapsMerge += 1 
    if len(a) == 0: 
     c += b 
     numberOfSwapsMerge += len(b) 
    else: 
     numberOfSwapsMerge += len(a) 
     c += a 
    return c 

# Code for merge sort 

def mergeSort(array): 
    """ Function to sort an array using merge sort algorithm """ 
    #global numberOfCompMerge 
    if len(array) == 0 or len(array) == 1: 
     return array 
    else: 
     middle = int(len(array)/2) 
     a = mergeSort(array[:middle]) 
     b = mergeSort(array[middle:]) 
     return merge(a,b) 

가 수정되었습니다. 악마가 세부 사항에있어.