이번 포스팅에서는 버블 정렬 알고리즘에 대해 알아보겠습니다. 버블 정렬의 작업 절차는 가장 간단합니다. 이 기사는 학생들이 시험에서 문제로 버블 정렬을 직면할 수 있기 때문에 학생들에게 매우 도움이 되고 흥미로울 것입니다. 따라서 주제에 대해 토론하는 것이 중요합니다.
리눅스 디렉토리에서 이름 바꾸기
버블 정렬은 의도한 순서가 아닐 때까지 인접한 요소를 반복적으로 교체하는 방식으로 작동합니다. 배열 요소의 움직임이 물 속의 공기 방울의 움직임과 비슷하기 때문에 버블 정렬이라고 합니다. 물 속의 거품이 표면으로 올라옵니다. 마찬가지로 버블 정렬의 배열 요소는 각 반복의 끝으로 이동합니다.
사용이 간편하지만 현실 세계에서 버블정렬의 성능이 좋지 않아 주로 교육 도구로 사용됩니다. 대규모 데이터 세트에는 적합하지 않습니다. 버블 정렬의 평균 및 최악의 복잡성은 다음과 같습니다. 에2), 어디 N 항목 수입니다.
버블 쇼트는 주로 다음과 같은 경우에 사용됩니다.
- 복잡성은 중요하지 않습니다
- 간단하고 짧은 코드가 선호됩니다
연산
아래 주어진 알고리즘에서 도착 의 배열이다 N 강요. 가정된 교환 알고리즘의 함수는 주어진 배열 요소의 값을 교환합니다.
begin BubbleSort(arr) for all array elements if arr[i] > arr[i+1] swap(arr[i], arr[i+1]) end if end for return arr end BubbleSort
버블정렬 알고리즘의 작동
이제 버블 정렬 알고리즘의 작동 방식을 살펴보겠습니다.
버블 정렬 알고리즘의 작동을 이해하기 위해 정렬되지 않은 배열을 살펴보겠습니다. 버블 정렬이 복잡하다는 것을 알고 있으므로 짧고 정확한 배열을 사용합니다. 에2).
배열의 요소는 다음과 같습니다.
첫 번째 패스
정렬은 처음 두 요소부터 시작됩니다. 비교해서 어느 것이 더 큰지 확인해 보세요.
여기서 32는 13보다 크므로(32 > 13) 이미 정렬되어 있습니다. 이제 32와 26을 비교해 보세요.
여기서 26은 36보다 작습니다. 따라서 교환이 필요합니다. 새 배열을 교체한 후 다음과 같이 표시됩니다.
이제 32와 35를 비교해 보세요.
여기서 35는 32보다 큽니다. 따라서 이미 정렬되어 있으므로 교체가 필요하지 않습니다.
VLC 유튜브 다운로드
이제 비교는 35와 10 사이가 될 것입니다.
여기서 10은 정렬되지 않은 35보다 작습니다. 그래서 교환이 필요합니다. 이제 배열의 끝에 도달했습니다. 첫 번째 통과 후 배열은 -
이제 두 번째 반복으로 이동합니다.
두 번째 패스
두 번째 반복에서도 동일한 프로세스가 수행됩니다.
여기서 10은 32보다 작습니다. 따라서 스왑이 필요합니다. 교체 후 어레이는 -
이제 세 번째 반복으로 이동합니다.
세 번째 패스
세 번째 반복에도 동일한 프로세스가 수행됩니다.
여기서 10은 26보다 작습니다. 따라서 스왑이 필요합니다. 교체 후 어레이는 -
이제 네 번째 반복으로 이동합니다.
네 번째 패스
마찬가지로 네 번째 반복 후에 배열은 다음과 같습니다.
따라서 교체가 필요하지 않으므로 배열이 완전히 정렬됩니다.
버블정렬의 복잡성
이제 최상의 경우, 평균적인 경우, 최악의 경우 버블 정렬의 시간 복잡도를 살펴보겠습니다. 버블 정렬의 공간 복잡도도 살펴보겠습니다.
1. 시간 복잡도
| 사례 | 시간 복잡도 |
|---|---|
| 최선의 경우 | 에) |
| 평균 사례 | 에2) |
| 최악의 경우 | 에2) |
2. 공간 복잡성
| 공간 복잡도 | 오(1) |
| 안정적인 | 예 |
- 버블정렬의 공간복잡도는 O(1)이다. 버블정렬에서는 Swap을 위해 별도의 변수가 필요하기 때문이다.
- 최적화된 버블 정렬의 공간 복잡도는 O(2)입니다. 최적화된 버블 정렬에는 두 개의 추가 변수가 필요하기 때문입니다.
이제 최적화된 버블 정렬 알고리즘에 대해 논의해 보겠습니다.
최적화된 버블정렬 알고리즘
버블 정렬 알고리즘에서는 배열이 이미 정렬된 경우에도 비교가 수행됩니다. 그로 인해 실행 시간이 늘어납니다.
이를 해결하기 위해 추가 변수를 사용할 수 있습니다. 교환되었습니다. 다음과 같이 설정됩니다. 진실 교환이 필요한 경우; 그렇지 않으면 다음과 같이 설정됩니다. 거짓.
반복 후에 스왑이 필요하지 않은 경우 변수의 값이 도움이 될 것입니다. 교환됨 될거야 거짓. 이는 요소가 이미 정렬되어 있으므로 추가 반복이 필요하지 않음을 의미합니다.
이 방법은 실행 시간을 줄이고 버블 정렬을 최적화합니다.
최적화된 버블 정렬을 위한 알고리즘
bubbleSort(array) n = length(array) repeat swapped = false for i = 1 to n - 1 if array[i - 1] > array[i], then swap(array[i - 1], array[i]) swapped = true end if end for n = n - 1 until not swapped end bubbleSort
버블정렬 구현
이제 다양한 프로그래밍 언어로 작성된 버블 정렬 프로그램을 살펴보겠습니다.
유튜브를 다운로드하려면 VLC
프로그램: C언어로 버블정렬을 구현하는 프로그램을 작성해보세요.
#include void print(int a[], int n) //function to print array elements { int i; for(i = 0; i <n; i++) { printf('%d ',a[i]); } void bubble(int a[], int n) function to implement bubble sort i, j, temp; for(i="0;" i < n; for(j="i+1;" j j++) if(a[j] a[i]) temp="a[i];" a[i]="a[j];" a[j]="temp;" main () j,temp; a[5]="{" 10, 35, 32, 13, 26}; n="sizeof(a)/sizeof(a[0]);" printf('before sorting array elements are -
'); print(a, n); bubble(a, printf('
after pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/52/bubble-sort-algorithm-13.webp" alt="Bubble sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement bubble sort in C++ language.</p> <pre> #include using namespace std; void print(int a[], int n) //function to print array elements { int i; for(i = 0; i <n; i++) { cout< <a[i]<<' '; } void bubble(int a[], int n) function to implement bubble sort i, j, temp; for(i="0;" i < n; for(j="i+1;" j j++) if(a[j] a[i]) temp="a[i];" a[i]="a[j];" a[j]="temp;" main() j,temp; a[5]="{45," 1, 32, 13, 26}; n="sizeof(a)/sizeof(a[0]);" cout<<'before sorting array elements are -
'; print(a, n); bubble(a, cout<<'
after return 0; pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/52/bubble-sort-algorithm-14.webp" alt="Bubble sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement bubble sort in C# language.</p> <pre> using System; public class Bubble { static void print (int[]a) //function to print array elements { int n = a.Length; int i; for (i = 0; i <n; 26 i++) { console.write (' ' + a[i]); } static void bubble (int[]a) function to implement sort int n="a.Length;" i, j, temp; for (i="0;" i < n; (j="i" 1; j j++) if (a[j] a[i]) temp="a[i];" a[i]="a[j];" a[j]="temp;" public main () int[] a="{" 45, 1, 32, 13, }; ('
before sorting array elements are -
'); print (a); console.writeline (); after pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/52/bubble-sort-algorithm-15.webp" alt="Bubble sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement bubble sort in Java.</p> <pre> public class Bubble { static void print (int a[]) //function to print array elements { int n = a.length; int i; for (i = 0; i <n; i++) { system.out.print(a[i] + ' '); } static void bubblesort (int a[]) function to implement bubble sort int n="a.length;" i, j, temp; for (i="0;" i < n; (j="i" 1; j j++) if (a[j] a[i]) temp="a[i];" a[i]="a[j];" a[j]="temp;" public main(string[] args) a[]="{35," 10, 31, 11, 26}; b1="new" bubble(); system.out.println('before sorting array elements are - b1.print(a); b1.bubblesort(a); system.out.println(); system.out.println('after pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/52/bubble-sort-algorithm-16.webp" alt="Bubble sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement bubble sort in JavaScript.</p> <pre> var a = [35, 10, 31, 11, 26]; function print() //function to print array elements { for(i = 0; i <5; i++) { document.writeln(a[i]); } document.write('before sorting array elements are - ' + <br>'); print(); for(i = 0; i <5; i++) { for (j="0;" j < 5; j++) if(a[i] a[j]) temp="a[i];" a[i]="a[j];" a[j]="temp;" } document.write(' <br> After sorting array elements are - ' + ' <br>'); print(); </5;></5;></pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/52/bubble-sort-algorithm-17.webp" alt="Bubble sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement bubble sort in PHP.</p> <pre> <?php $a = array(2, 45, 88, 11, 5); function printArray($a) { for($i = 0; $i < 5; $i++) { print_r($a[$i]); echo ' '; } } echo 'Before sorting array elements are - <br>'; printArray($a); for($i = 0; $i <5; $i++) { for ($j="0;" $j < 5; $j++) if($a[$i] $a[$j]) $temp="$a[$i];" $a[$i]="$a[$j];" $a[$j]="$temp;" } echo ' <br> After sorting array elements are - <br>'; printArray($a); ?> </5;></pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/52/bubble-sort-algorithm-18.webp" alt="Bubble sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement bubble sort in python.</p> <pre> a = [35, 10, 31, 11, 26] print('Before sorting array elements are - ') for i in a: print(i, end = ' ') for i in range(0,len(a)): for j in range(i+1,len(a)): if a[j] <a[i]: temp="a[j]" a[j]="a[i]" a[i]="temp" print('
after sorting array elements are - ') for i in a: print(i, end=" " ) < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/52/bubble-sort-algorithm-19.webp" alt="Bubble sort Algorithm"> <p>So, that's all about the article. Hope the article will be helpful and informative to you.</p> <p>This article was not only limited to the algorithm. We have also discussed the algorithm's complexity, working, optimized form, and implementation in different programming languages.</p> <hr></a[i]:></pre></n;></pre></n;></pre></n;></pre></n;> 산출
프로그램: PHP에서 버블 정렬을 구현하는 프로그램을 작성하세요.
<?php $a = array(2, 45, 88, 11, 5); function printArray($a) { for($i = 0; $i < 5; $i++) { print_r($a[$i]); echo \' \'; } } echo \'Before sorting array elements are - <br>'; printArray($a); for($i = 0; $i <5; $i++) { for ($j="0;" $j < 5; $j++) if($a[$i] $a[$j]) $temp="$a[$i];" $a[$i]="$a[$j];" $a[$j]="$temp;" } echo \' <br> After sorting array elements are - <br>'; printArray($a); ?> </5;> 산출
프로그램: 파이썬으로 버블정렬을 구현하는 프로그램을 작성해보세요.
a = [35, 10, 31, 11, 26] print('Before sorting array elements are - ') for i in a: print(i, end = ' ') for i in range(0,len(a)): for j in range(i+1,len(a)): if a[j] <a[i]: temp="a[j]" a[j]="a[i]" a[i]="temp" print(\' after sorting array elements are - \') for i in a: print(i, end=" " ) < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/52/bubble-sort-algorithm-19.webp" alt="Bubble sort Algorithm"> <p>So, that's all about the article. Hope the article will be helpful and informative to you.</p> <p>This article was not only limited to the algorithm. We have also discussed the algorithm's complexity, working, optimized form, and implementation in different programming languages.</p> <hr></a[i]:>