버블정렬 python bubbleSort ( 배열, 링크드리스트로 구현)

오늘은 사실 공부를 거의 안했다... 그냥 뭔가 집중도 안되고 하기싫었따

그래도 아예 안할 수는 없어서 버블정렬만 간단하게 정리해봄..!

 

버블정렬

 

강의에서도 보았고 구글에도 떠도는 정말 유용한 gif

 

버블정렬은 인덱스를 하나씩 이동하며 두 값을 비교하여 교환하고, 최댓값을 배열의 끝으로 밀어내는 정렬이다

 

한번 끝까지 갔으면 가장 큰 값이 맨 끝에 있으므로,

맨끝(최대 길이-1) 전까지 다시 처음부터 시행.

그다음은 최대길이-2 전까지 처음부터 시행.

 

버블정렬은 간단하지만 정렬 알고리즘중 최악의 효율을 보인다

정렬알고리즘 중에서 시간복잡도가 가장 높음!

 

시간복잡도는 O(n^2)

 

배열로 버블정렬 구현

def sortBubbleInArray(array):

    for i in range(len(array)-1): 

        for j in range(len(array)-1-i):

            if array[j] > array[j+1]:
                temp = array[j]
                array[j] = array[j+1]
                array[j+1] = temp

    return

range 끝에 -1이 들어간 이유는, 비교를 j와 j+1 끼리 하기 때문이다.

그냥 len(array) 까지 시행하면 인덱스가 오버되버림!

 

배열은.. 딱히 설명할게 없다.

 

 

 

 

 

링크드리스트로 버블정렬 구현

 

↓ 이전글의 링크드리스트가 반드시 필요하다

2022.11.25 - [자료구조] - python 알고리즘용 LinkedList

 

 

def sortBubble(self):

    if self.head is None:
        return None
    elif self.head.next is None:
        return None

    idx = self.tail
    curr = self.head 
    temp = None

    while idx.prev is not None:

        curr = self.head

        while curr != idx:

            if curr.data > curr.next.data:
                temp = curr.data
                curr.data = curr.next.data
                curr.next.data = temp

            curr = curr.next

        idx = idx.prev

    return

 

링크드리스트는 정렬을 위해 양방향으로 연결된 리스트가 필요하다.

 

노드의 .prev 필드를 타고 최대길이를 하나씩 줄여줄 변수 idx를 외부의 반복문 조건으로 넣고,

data를 비교할 curr 변수는 .next필드로 이동하며 값을 교환한다.

 

링크드리스트도 curr.data 와 curr.next.data를 비교하기 때문에

curr가 tail노드의 위치까지 갔을 땐 반복문 내부의 코드를 실행하지 않음. 

 

버블 정렬도 간단하게 구현 완료!