22. 버블정렬

■ 98. 버블정렬

 

문제286. 아래의 리스트를 버블 정렬하는 함수를 생성하시오

(loop 문으로 수행)

 

a=[5,4,3,2,1,8,7,10]

print(bubble_sort(a))

 

결과:

[1,2,3,4,5,7,8,10]

----------------------------

def bubble_sort(n):

    x = []

    a = len(n)

    for i in range(a):

        for j in range(a - 1):

            if n[j] < n[j + 1]:

                continue

            else:

(n[j+1],n[j])=(n[j] ,n[j+1])

    return n

a = [5, 4, 3, 2, 1, 8, 7, 10]

print(bubble_sort(a))

 

 

 

 

문제287.(오늘의 마지막 문제)

버블정렬을 재귀로 구현하시오 !

 

!!!!!!!!!!!!! 알아야 할 내용 !!!!!!!!!!!!!

버블정렬은

list=[4,3,2,1]    ->>  len(list) = 4

가 정렬되기 위해 최소 3세트를 비교 하면 된다.

1세트=전체 값 1번 비교

[4,3,2,1]

  ->[3,4,2,1]->[3,2,4,1]->[3,2,1,4]  :1세트

  이때,

맨 마지막 4 는 하나씩 비교하면서 제일 뒤로 밀려난 값이기에

더 이상 비교를 할 필요가 없다.

 

[3,2,1,4]

->[2,3,1,4]->[2,1,3,4] :2세트

맨 마지막 4는 비교대상이 아니기에,

비교횟수도 줄어든다.

이제 뒤에서 2번째도 비교할 필요가 없다.

 

[2,1,3,4]

->[1,2,3,4]: 3세트

 

이렇게 해서

해당 리스트의 최소비교값은 len(list)-1 이다.

 

---------------------------------------------------------

 

1번답:

def bubble_sort(n, i=0, j=0):

    x = len(n)

    if i == x:

        return n

    if j == x-i-1:

        return bubble_sort(n, i + 1, j=0)

    if j < x-i-1:

        if n[j] > n[j + 1]:

            (n[j + 1], n[j]) = (n[j], n[j + 1])

        return bubble_sort(n, i, j + 1)

a = [5, 4, 3, 2, 1, 8, 7, 10]

print(bubble_sort(a))

 

 

||

 

2번답:

def bubble_sort(n, i=0, j=0):

    x = len(n)

    if i < x:

 

        if j < x - 1:

            if n[j] > n[j + 1]:

                (n[j + 1], n[j]) = (n[j], n[j + 1])

            return bubble_sort(n, i, j + 1)

        return bubble_sort(n, i + 1, j=0)

    return n

a = [5, 4, 3, 2, 1, 8, 7, 10]

print(bubble_sort(a))

 

||   마지막에 스스로 푼 것

3번답:

def bubble_sort(n, i=0, j=0):

    x=len(n)

    while i<=x-1: #7

        if j==x-i-1: #7

            return bubble_sort(n,i+1,j=0)

        if j<x-i-1:#7

            if n[j] > n[j+1]:

                (n[j+1],n[j]) = (n[j], n[j+1])

            return bubble_sort(n,i, j+1)

    return n

a = [5, 4, 3, 2, 1, 8, 7, 10]

print(bubble_sort(a))