버블 정렬

[알고리즘][파이썬/Python] 버블 정렬 (Bubble Sort)

정의 차례로 인접한 두 개의 원소를 비교하여 자리를 교환하는 방식의 정렬 알고리즘 동작 방식 1. 배열(혹은 리스트)의 첫 번째 원소부터 마지막 원소까지 인접 원소 간 대소 비교를 반복하는데, 더 큰 값을 가진 원소가 왼쪽에 있다면 서로 자리를 바꿈 (swap) 2. 위 과정을 반복하여 한 단계가 끝나면 가장 큰 값을 가진 원소가 배열 (혹은 리스트)의 마지막 자리로 정렬되어 있음 3. 한 단계가 끝날 때마다 맨 끝에 위치한 원소는 정렬된 상태이므로 다음 단계에서는 정렬된 원소를 제외하고 대소 비교를 실행 메모리 사용 공간 n개의 원소에 대하여 n개의 메모리 사용 연산 시간 1. 최선의 경우 (Best Case) : 자료가 이미 정렬되어 있는 경우 - 비교횟수 : i번째 실행 시 (n-i) 번 비교하므로..