programing

버블 정렬 구현이 영원히 반복되는 이유는 무엇입니까?

cafebook 2023. 8. 21. 21:36
반응형

버블 정렬 구현이 영원히 반복되는 이유는 무엇입니까?

수업시간에 우리는 분류 알고리즘을 하고 있고, 비록 나는 그것들에 대해 이야기하고 의사 코드를 작성할 때 그것들을 잘 이해하지만, 나는 그것들을 위한 실제 코드를 작성하는 데 어려움을 겪고 있습니다.

이것이 파이썬에서 제가 시도한 것입니다.

mylist = [12, 5, 13, 8, 9, 65]

def bubble(badList):
    length = len(badList) - 1
    unsorted = True

    while unsorted:
        for element in range(0,length):
            unsorted = False
            if badList[element] > badList[element + 1]:
                hold = badList[element + 1]
                badList[element + 1] = badList[element]
                badList[element] = hold
                print badList
            else:
                unsorted = True

print bubble(mylist)

이제 (내가 알기로는) 이것은 올바르게 정렬되지만, 일단 완료되면 무한 반복됩니다.

이 코드를 수정하여 함수가 적절하게 완료되도록 하고 적절한 크기의 목록을 올바르게 정렬할 수 있는 방법은 무엇입니까?

추신. 함수에 인쇄물이 있어서는 안 되고 반환물이 있어야 한다는 것을 알고 있지만, 코드가 아직 작동하지 않기 때문에 아직 그렇게 하지 않았습니다.

하기 위해 이름을 unsortedsorted.

처음에는 목록이 아직 정렬되지 않았습니다.는 론물, 우는리를 설정합니다.sortedFalse.

하자마자.while루프, 우리는 목록이 이미 정렬되었다고 가정합니다. 순서가 두 , 는 아디어이렇다니습는을 합니다. 올바른 순서가 아닌 두 개의 요소를 찾자마자, 우리는 설정합니다.sorted로 돌아가다.False.sorted남아 있을 것입니다.True 잘못된 순서의 요소가 없는 경우에만.

sorted = False  # We haven't started sorting yet

while not sorted:
    sorted = True  # Assume the list is now sorted
    for element in range(0, length):
        if badList[element] > badList[element + 1]:
            sorted = False  # We found two elements in the wrong order
            hold = badList[element + 1]
            badList[element + 1] = badList[element]
            badList[element] = hold
    # We went through the whole list. At this point, if there were no elements
    # in the wrong order, sorted is still True. Otherwise, it's false, and the
    # while loop executes again.

코드를 보다 효율적으로 읽거나 읽을 수 있도록 도와주는 사소한 문제도 있습니다.

  • for는 변수 루프, 은변사수다니용합을 합니다.element 말하면, 엄히말면하밀,면,element요소가 아니라 목록 인덱스를 나타내는 숫자입니다.또한, 그것은 꽤 깁니다.이런 경우에는 다음과 같은 임시 변수 이름을 사용합니다.i"인덱스"의 경우.

    for i in range(0, length):

  • 그range하나의 할 수 .stop이 경우 0부터 해당 인수까지의 모든 정수 목록을 얻을 수 있습니다.

    for i in range(length):

  • Python Style Guide에서는 변수 이름을 밑줄과 함께 소문자로 지정하는 것이 좋습니다.이것은 이와 같은 작은 스크립트에 대한 아주 사소한 트집입니다. 파이썬 코드가 가장 많이 닮은 것에 익숙해지도록 하는 것입니다.

    def bubble(bad_list):

  • 두 변수의 값을 스왑하려면 해당 값을 튜플 할당으로 작성합니다. 오쪽은튜평예가니다됩로플른예(다니:▁(▁the)로 평가됩니다.(badList[i+1], badList[i])이라(3, 5) 두 ()에 할당됩니다.(badList[i], badList[i+1])).

    bad_list[i], bad_list[i+1] = bad_list[i+1], bad_list[i]

이 모든 것을 종합하면 다음과 같은 결과를 얻을 수 있습니다.

my_list = [12, 5, 13, 8, 9, 65]

def bubble(bad_list):
    length = len(bad_list) - 1
    sorted = False

    while not sorted:
        sorted = True
        for i in range(length):
            if bad_list[i] > bad_list[i+1]:
                sorted = False
                bad_list[i], bad_list[i+1] = bad_list[i+1], bad_list[i]

bubble(my_list)
print my_list

(참고로, 저는 당신의 인쇄 명세서도 삭제했습니다.

버블 정렬의 목표는 각 라운드에서 하단의 무거운 항목을 이동하는 동시에 가벼운 항목은 위로 이동하는 것입니다.요소를 비교하는 내부 루프에서는 각 회전마다 전체 목록을 반복할 필요가 없습니다.가장 무거운 것이 이미 마지막에 배치되었습니다.스왑된 변수는 추가 검사이므로 목록이 정렬되었음을 표시하고 불필요한 계산이 계속되는 것을 방지할 수 있습니다.

def bubble(badList):
    length = len(badList)
    for i in range(0,length):
        swapped = False
        for element in range(0, length-i-1):
            if badList[element] > badList[element + 1]:
                hold = badList[element + 1]
                badList[element + 1] = badList[element]
                badList[element] = hold
                swapped = True
        if not swapped: break

    return badList

버전 1이 수정되었습니다.

def bubble(badList):
    length = len(badList) - 1
    unsorted = True
    while unsorted:
        unsorted = False
        for element in range(0,length):
            #unsorted = False
            if badList[element] > badList[element + 1]:
                 hold = badList[element + 1]
                 badList[element + 1] = badList[element]
                 badList[element] = hold
                 unsorted = True
                 #print badList
             #else:
                 #unsorted = True

     return badList

이것은 부정적인 의미의 변수 이름을 사용할 때 발생하며, 그 값을 반전시켜야 합니다.다음은 더 쉽게 이해할 수 있는 내용입니다.

sorted = False
while not sorted:
    ...

반면에, 알고리즘의 논리는 약간 틀렸습니다.for 루프 중에 두 개의 요소가 교체되었는지 확인해야 합니다.제가 쓰는 방법은 다음과 같습니다.

def bubble(values):
    length = len(values) - 1
    sorted = False
    while not sorted:
        sorted = True
        for element in range(0,length):
            if values[element] > values[element + 1]:
                 hold = values[element + 1]
                 values[element + 1] = values[element]
                 values[element] = hold
                 sorted = False
    return values

정렬되지 않은 변수를 사용하는 것은 잘못된 것입니다. 두 개의 요소를 스왑했는지 여부를 알려주는 변수를 사용하려는 경우 루프를 종료할 수 있습니다. 그렇지 않으면 루프를 다시 루프해야 합니다.의 본문에 = false 다른 한 다음 = "를 "unsorted = false"인 경우 "unsorted = true"를 .for 루우프

def bubble_sort(l):
    for passes_left in range(len(l)-1, 0, -1):
        for index in range(passes_left):
            if l[index] < l[index + 1]:
               l[index], l[index + 1] = l[index + 1], l[index]
    return l

#두 번째 배열의 문제 공간을 줄임으로써 (분명히) 최적화될 수 있는 매우 간단한 함수입니다.하지만 O(n^2) 복잡도는 동일합니다.

def bubble(arr):
    l = len(arr)        
    for a in range(l):
        for b in range(l-1):
            if (arr[a] < arr[b]):
            arr[a], arr[b] = arr[b], arr[a]
    return arr

몇 가지 오류가 있습니다.첫 번째는 길이이고 두 번째는 정렬되지 않은 사용입니다(McWaffleix에 의해 언급됨).인쇄하려는 경우 목록을 반환할 수도 있습니다.

mylist = [12, 5, 13, 8, 9, 65]

def bubble(badList):
    length = len(badList) - 2
    unsorted = True

    while unsorted:
        for element in range(0,length):
            unsorted = False

            if badList[element] > badList[element + 1]:
                hold = badList[element + 1]
                badList[element + 1] = badList[element]
                badList[element] = hold
                print badList
                unsorted = True

    return badList

print bubble(mylist)

에타: 당신 말이 맞아요, 위에 있는 것들은 정말 엉망이에요.몇 가지 예시를 더 통해 테스트하지 못한 것에 대해 사과드립니다.

def bubble2(badList):
    swapped = True
    length = len(badList) - 2

    while swapped:
        swapped = False
        for i in range(0, length):
            if badList[i] > badList[i + 1]:

                # swap
                hold = badList[i + 1]
                badList[i + 1] = badList[i]
                badList[i] = hold

                swapped = True

    return badList

저는 어제부터 파이썬에 대해 읽기 시작한 신선한 초보자입니다.당신의 예에서 영감을 받아 80년대 스타일로 더 많은 것을 만들었지만, 그럼에도 불구하고 작동합니다.

lista1 = [12, 5, 13, 8, 9, 65]

i=0
while i < len(lista1)-1:
    if lista1[i] > lista1[i+1]:
        x = lista1[i]
        lista1[i] = lista1[i+1]
        lista1[i+1] = x
        i=0
        continue
    else:
        i+=1

print(lista1)

원래 알고리즘의 문제는 목록에서 더 낮은 숫자가 있으면 올바른 정렬 위치로 이동하지 않는다는 것입니다.프로그램은 숫자가 처음부터 끝까지 정렬되도록 매번 처음부터 다시 시작해야 합니다.

코드를 단순화하여 목록에 관계없이 반복되는 숫자가 있더라도 모든 숫자 목록에서 작동합니다.여기 코드가 있습니다.

mylist = [9, 8, 5, 4, 12, 1, 7, 5, 2]
print mylist

def bubble(badList):
    length = len(badList) - 1
    element = 0
    while element < length:
        if badList[element] > badList[element + 1]:
            hold = badList[element + 1]
            badList[element + 1] = badList[element]
            badList[element] = hold
            element = 0
            print badList
        else:
            element = element + 1

print bubble(mylist)

def bubble_sort(l):
    exchanged = True
    iteration = 0
    n = len(l)

    while(exchanged):
        iteration += 1
        exchanged = False

        # Move the largest element to the end of the list
        for i in range(n-1):
            if l[i] > l[i+1]:
                exchanged = True
                l[i], l[i+1] = l[i+1], l[i]
        n -= 1   # Largest element already towards the end

    print 'Iterations: %s' %(iteration)
    return l

def bubbleSort(alist):
if len(alist) <= 1:
    return alist
for i in range(0,len(alist)):
   print "i is :%d",i
   for j in range(0,i):
      print "j is:%d",j
      print "alist[i] is :%d, alist[j] is :%d"%(alist[i],alist[j])
      if alist[i] > alist[j]:
         alist[i],alist[j] = alist[j],alist[i]
return alist

목록 = [54,26,93,17,77,31,44,55,20,-23,-34,16,11,11,11]

인쇄 bubbleSort(목록)

def bubble_sort(a):
    t = 0
    sorted = False # sorted = False because we have not began to sort
    while not sorted:
    sorted = True # Assume sorted = True first, it will switch only there is any change
        for key in range(1,len(a)):
            if a[key-1] > a[key]:
                sorted = False
                t = a[key-1]; a[key-1] = a[key]; a[key] = t;
    print a

더 간단한 예:

a = len(alist)-1
while a > 0:
    for b in range(0,a):
        #compare with the adjacent element
        if alist[b]>=alist[b+1]:
            #swap both elements
            alist[b], alist[b+1] = alist[b+1], alist[b]
    a-=1

이렇게 하면 요소가 0에서 a(기본적으로 해당 라운드의 정렬되지 않은 모든 요소)로 이동하여 인접 요소와 비교하고 인접 요소보다 클 경우 스왑을 수행할 수 있습니다.라운드가 끝나면 마지막 요소가 정렬되고 모든 요소가 정렬될 때까지 프로세스가 해당 요소 없이 다시 실행됩니다.

다음과 같은 조건은 필요하지 않습니다.sort사실인지 아닌지.

이 알고리즘은 스왑할 때만 숫자의 위치를 고려하므로 반복되는 숫자는 영향을 주지 않습니다.

def bubble_sort(li):
    l = len(li)
    tmp = None
    sorted_l = sorted(li)
    while (li != sorted_l):
        for ele in range(0,l-1):
            if li[ele] > li[ele+1]:
                tmp = li[ele+1]
                li[ele+1] = li [ele]
                li[ele] = tmp
    return li

def bubbleSort ( arr ):
    swapped = True 
    length = len ( arr )
    j = 0

    while swapped:
        swapped = False
        j += 1 
        for i in range ( length  - j ):
            if arr [ i ] > arr [ i + 1 ]:
                # swap
                tmp = arr [ i ]
                arr [ i ] = arr [ i + 1]
                arr [ i + 1 ] = tmp 

                swapped = True

if __name__ == '__main__':
    # test list
    a = [ 67, 45, 39, -1, -5, -44 ];

    print ( a )
    bubbleSort ( a )
    print ( a )

def bubblesort(array):
    for i in range(len(array)-1):
        for j in range(len(array)-1-i):
            if array[j] > array[j+1]:
                array[j], array[j+1] = array[j+1], array[j]
    return(array)

print(bubblesort([3,1,6,2,5,4]))

arr = [5,4,3,1,6,8,10,9] # array not sorted

for i in range(len(arr)):
    for j in range(i, len(arr)):
        if(arr[i] > arr[j]):
            arr[i], arr[j] = arr[j], arr[i]

            print (arr)

솔루션을 추가하는 것을 고려하고 있습니다. 왜냐하면 모든 솔루션은

  1. 더 많은 시간
  2. 더 큰 공간 복잡성
  3. 또는 너무 많은 수술을 하는 것

그렇다면 그래야 합니다.

제 해결책은 다음과 같습니다.

def countInversions(arr):
    count = 0
    n = len(arr)
    for i in range(n):
        _count = count
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                count += 1
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
        if _count == count:
            break
    return count

목록 이해를 사용하여 더 짧은 구현에 관심이 있는 사람은 다음과 같습니다.

def bubble_sort(lst: list) -> None:
    [swap_items(lst, i, i+1) for left in range(len(lst)-1, 0, -1) for i in range(left) if lst[i] > lst[i+1]]


def swap_items(lst: list, pos1: int, pos2: int) -> None:
    lst[pos1], lst[pos2] = lst[pos2], lst[pos1]

다음은 다음과 같은 버블 정렬의 다른 변형입니다.for루프. 기본적으로 당신은 고려하고 있습니다.lastIndex의array그리고 천천히decrementing배열의 첫 번째 인덱스가 될 때까지.

그algorithm전체 패스가 아무런 패스 없이 이루어질 때까지 이와 같이 어레이를 계속 이동합니다.swaps발생하고 있는

거품은 기본적으로.Quadratic Time: O(n²)성과에 관한 한.

class BubbleSort: 
  def __init__(self, arr):
    self.arr = arr;

  def bubbleSort(self):
    count = 0;
    lastIndex = len(self.arr) - 1;
    
    while(count < lastIndex):
      if(self.arr[count] > self.arr[count + 1]):
        self.swap(count)  
      count = count + 1;

      if(count == lastIndex):
        count = 0;
        lastIndex = lastIndex - 1;   

  def swap(self, count):
    temp = self.arr[count];
    self.arr[count] = self.arr[count + 1];
    self.arr[count + 1] = temp;
    
arr = [9, 1, 5, 3, 8, 2]
p1 = BubbleSort(arr)

print(p1.bubbleSort())

def bubblesort(L,s):
    if s >-1 :
        bubblesort(L,s-1)
        for i in range(len(L)-1-s):
            if L[i]>L[i+1]:
                temp = L[i+1]
                L[i+1] = L[i]
                L[i] = temp

    return L

Nlist = [3,50,7,1,8,11,9,0,-1,5]
print(bubblesort(Nlist,len(Nlist)))

fury와 Martin Cote가 제공한 답변은 무한 루프의 문제를 해결했지만, 내 코드는 여전히 올바르게 작동하지 않을 것입니다(더 큰 목록의 경우, 올바르게 정렬되지 않을 것입니다).나는 결국 그것을 버렸습니다.unsorted변수를 사용하고 대신 카운터를 사용했습니다.

def bubble(badList):
    length = len(badList) - 1
    n = 0
    while n < len(badList):
        for element in range(0,length):
            if badList[element] > badList[element + 1]:
                hold = badList[element + 1]
                badList[element + 1] = badList[element]
                badList[element] = hold
                n = 0
            else:
                n += 1
    return badList

if __name__ == '__main__':
    mylist = [90, 10, 2, 76, 17, 66, 57, 23, 57, 99]
    print bubble(mylist)

댓글에 제 코드를 개선하는 방법에 대한 조언을 해주시면 감사하겠습니다.

사용해 보세요.

a = int(input("Enter Limit"))


val = []

for z in range(0,a):
    b = int(input("Enter Number in List"))
    val.append(b)


for y in range(0,len(val)):
   for x in range(0,len(val)-1):
       if val[x]>val[x+1]:
           t = val[x]
           val[x] = val[x+1]
           val[x+1] = t

print(val)

9년 후에 이것이 당신에게 도움이 될지 모르겠습니다.간단한 버블 정렬 프로그램입니다.

    l=[1,6,3,7,5,9,8,2,4,10]

    for i in range(1,len(l)):
        for j in range (i+1,len(l)):
            if l[i]>l[j]:
                l[i],l[j]=l[j],l[i]

def merge_bubble(arr):
    k = len(arr)
    while k>2:
        for i in range(0,k-1):
            for j in range(0,k-1):
                if arr[j] > arr[j+1]:
                    arr[j],arr[j+1] = arr[j+1],arr[j]

        return arr
        break
    else:
        if arr[0] > arr[1]:
            arr[0],arr[1] = arr[1],arr[0]
        return arr 

def bubble_sort(l):
    for i in range(len(l) -1):
        for j in range(len(l)-i-1):
            if l[j] > l[j+1]:
                l[j],l[j+1] = l[j+1], l[j]
    return l

def bubble_sorted(arr:list):
    while True:
        for i in range(0,len(arr)-1):
            count = 0
            if arr[i] > arr[i+1]:
                count += 1
                arr[i], arr[i+1] = arr[i+1], arr[i]
        if count == 0:
            break
    return arr
arr = [30,20,80,40,50,10,60,70,90]
print(bubble_sorted(arr))
#[20, 30, 40, 50, 10, 60, 70, 80, 90]

def bubbleSort(a): def swap(x, y): temp = a[x] a[x] = a[y] a[y] = temp #outer loop for j in range(len(a)): #slicing to the center, inner loop, python style for i in range(j, len(a) - j):
#find the min index and swap if a[i] < a[j]: swap(j, i) #find the max index and swap if a[i] > a[len(a) - j - 1]: swap(len(a) - j - 1, i) return a

언급URL : https://stackoverflow.com/questions/895371/why-is-bubble-sort-implementation-looping-forever

반응형

'programing' 카테고리의 다른 글

스프링 부트로 여러 서블릿 컨테이너/서블릿 구성  (0) 2023.08.21
16진수 색상 문자열에서 색상을 가져오는 방법  (0) 2023.08.21
사전 함께 추가  (0) 2023.08.21
라벨 변경 입력 값  (0) 2023.08.21
Android Recyclerview 그리드 레이아웃 관리자 열 간격  (0) 2023.08.21

'programing'의 다른글

  • 현재글버블 정렬 구현이 영원히 반복되는 이유는 무엇입니까?

관련글

댓글

티스토리툴바