버블 정렬(Bubble Sort) 은 프로그래밍에서 가장 간단한 정렬 알고리즘 중 하나입니다. 정렬할 시퀀스를 반복적으로 살펴보며 한 번에 두 요소를 비교하고 순서가 잘못된 경우 교체합니다. 교환해야 할 요소가 더 이상 없을 때까지 배열 방문 작업을 반복합니다. 이는 배열이 정렬되었음을 의미합니다.
버블 정렬은 물에서 나오는 거품과 같습니다. 버블 정렬에서는 배열을 오름차순 또는 내림차순으로 정렬하는지 여부에 따라 가장 작은 숫자 또는 가장 큰 숫자로 버블이 배열의 시작 또는 끝 쪽으로 나타납니다.
1) 인접한 요소를 비교하십시오. 첫 번째 요소가 두 번째 요소보다 크면 두 요소를 교환하십시오.
2) 첫 번째 쌍에서 시작하여 마지막 쌍으로 끝나는 모든 인접 요소 쌍에 대해 동일한 작업을 수행합니다. 이때 마지막 요소는 가장 큰 숫자가 되어야 합니다.
3) 마지막 요소를 제외한 모든 요소에 대해 위 단계를 반복합니다.
4) 비교할 숫자 쌍이 없을 때까지 점점 더 적은 수의 요소에 대해 위 단계를 반복합니다.
버블 정렬은 빠른 정렬, 병합 정렬, 쉘 정렬과 같은 다른 정렬 알고리즘에 비해 성능이 좋지 않습니다. 이러한 알고리즘의 평균 사례 복잡도는 O(nlogn)인 반면 버블 정렬의 평균 사례 복잡도는 O(n^2)입니다.
가장 좋은 경우에는 버블 정렬이 O(n) 성능의 퀵 정렬보다 낫습니다. 버블 정렬은 n=100인 경우에도 빠른 정렬이나 병합 정렬보다 3배 느리지만 구현하고 기억하기가 더 쉽습니다.
버블 정렬의 복잡성과 성능은 다음과 같습니다.
1) 버블 정렬의 최악의 경우 성능은 O(n^2)입니다.
2) 버블 정렬의 최상의 성능은 O(n)입니다.
3) 버블 정렬의 평균 성능은 O(n^2)입니다.
//버블 정렬 publicstaticvoidbubbleSort(int[]arr){//외부 루프는 배열 루프의 회전 수를 제어하는 데 사용됩니다. for(inti=0;i<arr.length-1;i++){//내부 루프 루프는 요소 값의 비교를 완료하고 더 큰 요소 값을 뒤로 바꾸는 데 사용됩니다. for(intj=0;j<arr.length-1-i;j++){if(arr[j]>arr [j+1]){inttemp= arr[j];arr[j]=arr[j+1];arr[j+1]=temp;}}}//(intn:nums){System에 대한 출력 결과 .out.println(n);} }예를 들어:
publicclassMain{publicstaticvoidmain(String[]args){inta[]={6,1,15,32,9};for(inti=1;i<a.length;i++){for(intj=0;j<a .length-1;j++){if(a[j]>a[j+1]){inttemp=a[j];a[j]=a[j+1];a[j+1]=temp ;}}}System.out.println(버블 정렬 결과는 다음과 같습니다.);for(inttemp:a){System.out.print(temp+);}}}실행 결과는 다음과 같습니다.
버블 정렬의 결과는 1691532입니다.
직접 시도해 볼 수 있습니다!