3.1. Sorting - 3.1.1 Bubble sort

CS - 3. Common Algorithms - 3.1. Sorting - 3.1.1 Bubble sort

 

💡Sorting algorithms are used to sort data in a collection. Sorting is a very common task in computer science, and it is also a very common interview question. There are many different ways to sort data, and different algorithms have different advantages and disadvantages.

Learn about the sorting algorithms and know the best case/worst case, average complexity of each. Also, learn about the stability of sorting algorithms.

정렬 알고리즘은 컬렉션의 데이터를 정렬하는 데 사용됩니다. 정렬은 컴퓨터 과학에서 매우 흔한 작업이며, 면접 질문에도 자주 등장합니다. 데이터를 정렬하는 방법에는 여러 가지가 있으며, 알고리즘마다 장단점이 다릅니다.
정렬 알고리즘에 대해 알아보고 각 알고리즘의 최상의 경우와 최악의 경우, 평균 복잡도를 파악합시다. 또한 정렬 알고리즘의 안정성에 대해서도 알아봅시다.

 

 

Bubble sort

💡 Bubble sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted.

버블 정렬은 목록을 반복적으로 통과하면서 인접한 요소를 비교하고 순서가 잘못된 경우 교체하는 간단한 정렬 알고리즘입니다. 목록이 정렬될 때까지 목록을 통과하는 과정이 반복됩니다.

 

버블 정렬은 가장 간단한 정렬 알고리즘 중 하나로,

인접한 두 원소를 비교해 필요에 따라 위치를 교환하는 방식으로 작동합니다.

 

왜 이름이 버블일까요?

큰 값이 마치 '버블'처럼 배열의 끝으로 떠오르는 모습을 보여주는 정렬 방식이기 떄문입니다.

 

버블 정렬의 동작은

1. 배열의 처음부터 시작해 인접한 두 원소를 비교

2. 만약 앞의 원소가 뒤의 원소보다 크다면, 두 원소의 위치를 변경

3. 배열의 끝까지 이 과정을 반복합니다. 이렇게 하면 가장 큰 원소가 배열의 마지막에 위치하게 됩니다.

4. 가장 큰 원소가 정렬된 위치에 있으므로, 이제는 마지막 원소를 제외하고 나머지 원소에 대해 동일한 과정을 반복합니다.

5. 배열의 모든 원소가 정렬될 떄까지 이 과정을 반복합니다.

 

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

240116 예시 추가

A_list = [8,7,4,18,19,355,1,98]
bubble_sort(A_list)

 

 

예시를 보면 앞에서부터 비교하며 큰것을 뒤로 보냅니다.

 

 

 

시간 복잡도는 O(n^2)입니다.

 

 

 

 

데이터의 양이 많지 않거나, 어느정도 정렬이 된 데이터라면 효과적이지만,

양이 많거나 무작위로 배열된 경우에는 퀵 정렬, 병합정렬등이 더 효율적인 정렬 알고리즘 입니다.