거품 정렬
둘러보기로 가기
검색하러 가기
![]() 거품 정렬 정적 시각화[1] | |
분류 | 정렬 알고리즘 |
---|---|
자료 구조 | 배열 |
최악 시간복잡도 | 비교, 교환 |
최선 시간복잡도 | 비교, 교환 |
평균 시간복잡도 | 비교, 교환 |
공간복잡도 | 보조 |
거품 정렬( - 整列, 영어: bubble sort, sinking sort)은 두 인접한 원소를 검사하여 정렬하는 방법이다. 시간 복잡도가 로 상당히 느리지만, 코드가 단순하기 때문에 자주 사용된다. 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름이다. 양방향으로 번갈아 수행하면 칵테일 정렬이 된다.
예제[편집]
오름차순으로 정렬하는 거품정렬의 과정은 다음과 같다.
55 07 78 12 42 초기값[파란색은 sorting] 07 55 78 12 42 첫 번째 패스(pass) 07 55 78 12 42 07 55 12 78 42 07 55 12 42 78 두 번째 패스(pass) 07 55 12 42 78 07 12 55 42 78 07 12 42 55 78 세 번째 패스(pass) 07 12 42 55 78 네 번째 패스(pass) 07 12 42 55 78 다섯 번째 패스(pass) 07 12 42 55 78 정렬 끝
의사코드로 나타낸 알고리즘[편집]
procedure bubbleSort( A : list of sortable items ) defined as: for each i in 1 to length(A) do: for each j in length(A) downto i + 1 do: if A[ j ] < A[ j - 1 ] then swap( A[ j ], A[ j - 1 ] ) end if end for end for end procedure
소스 코드[편집]
C[편집]
#include <stdio.h>
# define MAX 10
int* bubble_sort(int arr[], int n) {
int i, j, temp;
for (i=n-1; i>0; i--) {
for (j=0; j<i; j++) {
if (arr[j] > arr[j+1]) {
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
return arr;
}
int main() {
int arr[MAX] = { 2, 6, 4, 8, 10, 12, 89, 68, 45, 37 };
int* arr_new = bubble_sort(arr, MAX);
for (int i = 0; i < MAX; i++) {
printf("%d\n", *(arr_new+i));
}
return 0;
}
C++[편집]
#include <iostream>
using namespace std;
#include <iomanip>
using std::setw;
void printBubbles(const int bubbles[], const int n);
void lineup(int& large, int& small);
int main()
{
const int n = 10;
int bubbles[n] = { 2, 6, 4, 8, 10, 12, 89, 68, 45, 37 };
cout << "Data items in original order\n";
printBubbles(bubbles, n);
for (int level = 0; level < n - 1; level++) {
for (int i = 0; i < n - level - 1; i++) {
if (bubbles[i] > bubbles[i + 1])
lineup(bubbles[i], bubbles[i + 1]);
}
}
cout << "\nData items in ascending order\n";
printBubbles(bubbles, n);
return 0;
}
void printBubbles(const int bubbles[], const int n) {
for (int i = 0; i < n; i++)
cout << setw(4) << bubbles[i];
cout << endl;
}
void lineup(int& large, int& small) {
int save = large;
large = small;
small = save;
}
C#[편집]
int[] data = new int[] { 3, 6, 2, 4, 1, 7, 9, 8, 5 };
int hold = 0;
int[] BubbleSort = new int[] { };
for(int i = 0; i < data.Count() - 1; i++)
{
for (int j = 0; j < data.Count() - 1 - i; j++)
{
if (data[j] > data[j + 1])
{
hold = data[j];
data[j] = data[j + 1];
data[j + 1] = hold;
}
}
}
for (int i = 0; i < data.Count(); i++)
{
Console.WriteLine(data[i]);
}
JAVA[편집]
void bubbleSort(int[] arr) {
int temp = 0;
for(int i = 0; i < arr.length - 1; i++) {
for(int j= 1 ; j < arr.length-i; j++) {
if(arr[j]<arr[j-1]) {
temp = arr[j-1];
arr[j-1] = arr[j];
arr[j] = temp;
}
}
}
System.out.println(Arrays.toString(arr));
}
파이썬[편집]
def bubbleSort(x):
length = len(x)-1
for i in range(length):
for j in range(length-i):
if x[j] > x[j+1]:
x[j], x[j+1] = x[j+1], x[j]
return x
스칼라[편집]
def bubbleSort(arr: Array[Int]):Array[Int] = {
var tmp = 0
for(i <- 0 until arr.length; j <- 1 until arr.length-i) {
if (arr(j-1) > arr(j)) {
tmp = arr(j-1)
arr(j-1) = arr(j)
arr(j) = tmp
}
}
arr
}
각주[편집]
- ↑ Cortesi, Aldo (2007년 4월 27일). “Visualising Sorting Algorithms”. 2017년 3월 16일에 확인함.
외부 링크[편집]
![]() |
이 글은 컴퓨터 과학에 관한 토막글입니다. 여러분의 지식으로 알차게 문서를 완성해 갑시다. |