[python] 버블 정렬 숙제

Program / 글쓴이

수업에서 우리는 정렬 알고리즘을하고 있는데, 그것들에 대해 이야기하고 의사 코드를 작성할 때 잘 알고 있지만 실제 코드를 작성하는 데 문제가 있습니다.

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

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)

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

이 코드를 어떻게 수정하여 함수가 올바르게 완료되고 (합리적인) 크기 목록을 올바르게 정렬합니까?

추신 : 나는 함수에서 실제로 인쇄를해서는 안되며 리턴을해야한다는 것을 알고 있지만 코드가 실제로 작동하지 않기 때문에 아직 그렇게하지 않았습니다.

답변

스크립트가 현재 작동하지 않는 이유를 설명하기 위해, 나는 변수의 이름을 바꿀 수 있습니다 unsorted로 sorted.

처음에는 목록이 아직 정렬되지 않았습니다. 물론로 설정 sorted했습니다 False.

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“index” 와 같은 임시 변수 이름 만 사용하십시오 .

    for i in range(0, length):

  • 이 range명령은 하나의 인수 ( stop) 만 사용할 수도 있습니다 . 이 경우 0에서 해당 인수까지의 모든 정수 목록이 표시됩니다.

    for i in range(length):

  • 파이썬 스타일 가이드는 변수가 밑줄과 소문자로 명명하는 것이 좋습니다. 이것은 다음과 같은 작은 스크립트에 대한 아주 작은 nitpick입니다. 파이썬 코드와 가장 유사한 것에 익숙해지는 것이 더 좋습니다.

    def bubble(bad_list):

  • 두 변수의 값을 바꾸려면 튜플 할당으로 작성하십시오. 오른쪽은 튜플로 평가 된 다음 (예 : (badList[i+1], badList[i])is (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

답변

정렬되지 않은 변수 사용이 잘못되었습니다. 두 요소를 교체했는지 여부를 알려주는 변수가 필요합니다. 그렇게 한 경우 루프를 종료 할 수 있습니다. 그렇지 않으면 다시 루프해야합니다. 여기있는 것을 고치려면 if 케이스 본문에 “unsorted = false”를 넣으십시오. else 케이스를 제거하십시오. for루프 앞에 “unsorted = true”를 입력하십시오 .

답변

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

답변

거기에 몇 가지 오류가 있습니다. 첫 번째는 길이이고 두 번째는 정렬되지 않은 상태로 사용하는 것입니다 (McWafflestix에서 명시한대로). 인쇄하려는 경우 목록을 반환 할 수도 있습니다.

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)

eta : 당신 말이 맞아, 위의 지옥 같은 버그입니다. 더 많은 예제를 통해 테스트하지 않아서 나쁘다.

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