빠른 버블 정렬

Question

def bubble(lst): 
    swap = 'True' 
    counter = 0 
    n = len(lst) 
    m = len(lst) 
    while swap == 'True': 
      for j in range(n-1): 
        if lst[j] > lst[j+1]: 
          lst[j],lst[j+1] = lst[j+1],lst[j] 
          counter += 1 
          swap = 'True' 
        else: 
          swap = 'False' 
      n = n - 1 
    return counter 

큰 목록에서 사용하기 때문에이 기능의 소요 시간을 단축하려면 어떻게해야합니까?

Answer 1

알고리즘 변경.

MergeSort 또는 QuickSort를 사용하십시오.

BubbleSort는 O (n * n)입니다. 존재하는 유일한 이유는 학생들에게 배열 정렬 방법을 보여주는 것입니다.

MergeSort는 최악의 경우 O (n log n)입니다.

QuickSort는 O (n * n) 최악의 경우, 평균 케이스 O (n log n)이지만 "상수가"이므로 일반적으로 병합 정렬보다 빠릅니다.

웹에서 검색하십시오.

는

def bubble(lst): 
    n = len(lst) 
    while True 
     newn = 0 
     for i in range(1, n-1): 
      if lst[i-1] > lst[i]: 
       lst[i-1],lst[i] = lst[i],lst[i-1] 
       newn = i 
       counter += 1 
     if newn <= 0: 
      return counter 
     n = newn 

복잡성은 그러나됩니다 :

내가 잘못 아니에요 경우 (내가하시기 바랍니다 나는 경우 나 분노하지 않는)은 ... 나는 당신이 원하는 것을 이해 생각 항상 O (n * n)이므로 중요한 차이가 없음을 알 수 있습니다. 예를 들어

:

목록 2000 개 항목이며 거품 정렬, O (* 2000 2000) = 4,000,000 루프 단계를 사용합니다. 이것은 거대합니다.

O (2000 * log2 2000) = 루프 단계의 약 21931이며 이는 관리 가능합니다.

Answer 2

def bubble(lol): 
    lol.sort() 
    return lol 

당신이 날 죽이고있어