logo

TechCodeview

버블 정렬 – 데이터 구조 및 알고리즘 자습서

버블정렬 가장 간단하다 정렬 알고리즘 이는 인접한 요소의 순서가 잘못된 경우 반복적으로 교체하여 작동합니다. 이 알고리즘은 평균 및 최악의 경우 시간 복잡도가 상당히 높기 때문에 대규모 데이터 세트에는 적합하지 않습니다.

버블 정렬 알고리즘

버블정렬 알고리즘에서는

  • 왼쪽에서 탐색하여 인접한 요소를 비교하고 더 높은 요소가 오른쪽에 배치됩니다.
  • 이런 방식으로 가장 큰 요소가 처음에는 가장 오른쪽 끝으로 이동됩니다.
  • 그런 다음 이 프로세스는 데이터가 정렬될 때까지 두 번째로 큰 것을 찾아 배치하는 등의 작업을 계속합니다.
추천 연습 버블정렬 시도해 보세요!

버블 정렬은 어떻게 작동하나요?

다음 그림을 통해 버블정렬의 원리를 이해해보자.



입력: 도착[] = {6, 0, 3, 5}

첫 번째 패스:

가장 큰 요소는 올바른 위치, 즉 배열의 끝 부분에 배치됩니다.

버블 정렬 알고리즘 : 가장 큰 요소를 올바른 위치에 배치

두 번째 패스:

두 번째로 큰 요소를 올바른 위치에 배치

버블 정렬 알고리즘 : 두 번째로 큰 요소를 올바른 위치에 배치

세 번째 패스:

나머지 두 요소를 올바른 위치에 배치합니다.

버블 정렬 알고리즘 : 나머지 요소를 올바른 위치에 배치

  • 총 번호 패스 수: n-1
  • 총 번호 비교: n*(n-1)/2

버블 정렬 구현

아래는 버블 정렬의 구현입니다. 내부 루프가 스왑을 발생시키지 않으면 알고리즘을 중지하여 최적화할 수 있습니다.

C++ 
// Optimized implementation of Bubble sort #include  using namespace std; // An optimized version of Bubble Sort void bubbleSort(int arr[], int n) {  int i, j;  bool swapped;  for (i = 0; i < n - 1; i++) {  swapped = false;  for (j = 0; j < n - i - 1; j++) {  if (arr[j]>arr[j + 1]) { swap(arr[j], arr[j + 1]);  교환 = 사실;  } } // 내부 루프에 의해 // 두 요소가 교환되지 않은 경우, break if (swapped == false) break;  } } // 배열을 인쇄하는 함수 void printArray(int arr[], int size) { int i;  (i = 0; 나는< size; i++)  cout << ' ' << arr[i]; } // Driver program to test above functions int main() {  int arr[] = { 64, 34, 25, 12, 22, 11, 90 };  int N = sizeof(arr) / sizeof(arr[0]);  bubbleSort(arr, N);  cout << 'Sorted array: 
';  printArray(arr, N);  return 0; } // This code is contributed by shivanisinghss2110>
씨 
// Optimized implementation of Bubble sort #include  #include  void swap(int* xp, int* yp) {  int temp = *xp;  *xp = *yp;  *yp = temp; } // An optimized version of Bubble Sort void bubbleSort(int arr[], int n) {  int i, j;  bool swapped;  for (i = 0; i < n - 1; i++) {  swapped = false;  for (j = 0; j < n - i - 1; j++) {  if (arr[j]>arr[j + 1]) { swap(&arr[j], &arr[j + 1]);  교환 = 사실;  } } // 내부 루프에 의해 두 요소가 교환되지 않은 경우 // break if (swapped == false) break;  } } // 배열을 인쇄하는 함수 void printArray(int arr[], int size) { int i;  (i = 0; 나는< size; i++)  printf('%d ', arr[i]); } // Driver program to test above functions int main() {  int arr[] = { 64, 34, 25, 12, 22, 11, 90 };  int n = sizeof(arr) / sizeof(arr[0]);  bubbleSort(arr, n);  printf('Sorted array: 
');  printArray(arr, n);  return 0; }>
자바 
// Optimized java implementation of Bubble sort import java.io.*; class GFG {    // An optimized version of Bubble Sort  static void bubbleSort(int arr[], int n)  {  int i, j, temp;  boolean swapped;  for (i = 0; i < n - 1; i++) {  swapped = false;  for (j = 0; j < n - i - 1; j++) {  if (arr[j]>arr[j + 1]) { // arr[j]와 arr[j+1]을 교체합니다. temp = arr[j];  arr[j] = arr[j + 1];  arr[j + 1] = 온도;  교환 = 사실;  } } // 내부 루프에 의해 // 두 요소가 교환되지 않은 경우, break if (swapped == false) break;  } } // 배열을 인쇄하는 함수 static void printArray(int arr[], int size) { int i;  (i = 0; 나는< size; i++)  System.out.print(arr[i] + ' ');  System.out.println();  }  // Driver program  public static void main(String args[])  {  int arr[] = { 64, 34, 25, 12, 22, 11, 90 };  int n = arr.length;  bubbleSort(arr, n);  System.out.println('Sorted array: ');  printArray(arr, n);  } } // This code is contributed // by Nikita Tiwari.>
파이썬3 
# Optimized Python program for implementation of Bubble Sort def bubbleSort(arr): n = len(arr) # Traverse through all array elements for i in range(n): swapped = False # Last i elements are already in place for j in range(0, n-i-1): # Traverse the array from 0 to n-i-1 # Swap if the element found is greater # than the next element if arr[j]>arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[j] swapped = True if (swapped == False): break # 위를 테스트할 드라이버 코드 if __name__ == '__main__': arr = [64, 34, 25, 12, 22, 11, 90] bubbleSort(arr) print('정렬된 배열:') for i in range(len(arr)): print('%d' % arr[i], end=' ') # 이 코드는 Suraj krushna Yadav에 의해 수정되었습니다.>
씨# 
// Optimized C# implementation of Bubble sort using System; class GFG {  // An optimized version of Bubble Sort  static void bubbleSort(int[] arr, int n)  {  int i, j, temp;  bool swapped;  for (i = 0; i < n - 1; i++) {  swapped = false;  for (j = 0; j < n - i - 1; j++) {  if (arr[j]>arr[j + 1]) { // arr[j]와 arr[j+1]을 교체합니다. temp = arr[j];  arr[j] = arr[j + 1];  arr[j + 1] = 온도;  교환 = 사실;  } } // 내부 루프에 의해 // 두 요소가 교환되지 않은 경우, break if (swapped == false) break;  } } // 배열을 인쇄하는 함수 static void printArray(int[] arr, int size) { int i;  (i = 0; 나는< size; i++)  Console.Write(arr[i] + ' ');  Console.WriteLine();  }  // Driver method  public static void Main()  {  int[] arr = { 64, 34, 25, 12, 22, 11, 90 };  int n = arr.Length;  bubbleSort(arr, n);  Console.WriteLine('Sorted array:');  printArray(arr, n);  } } // This code is contributed by Sam007>
자바스크립트 
// Optimized javaScript implementation // of Bubble sort // An optimized version of Bubble Sort function bubbleSort(arr, n) {  var i, j, temp;  var swapped;  for (i = 0; i < n - 1; i++)   {  swapped = false;  for (j = 0; j < n - i - 1; j++)   {  if (arr[j]>arr[j + 1]) { // arr[j]와 arr[j+1]을 교체합니다. temp = arr[j];  arr[j] = arr[j + 1];  arr[j + 1] = 온도;  교환 = 사실;  } } // 내부 루프에 의해 // 두 요소가 교환되지 않은 경우, break if (swapped == false) break;  } } // 배열을 인쇄하는 함수 function printArray(arr, size) { var i;  (i = 0; 나는< size; i++)  console.log(arr[i] + ' '); } // Driver program var arr = [ 64, 34, 25, 12, 22, 11, 90 ]; var n = arr.length; bubbleSort(arr, n); console.log('Sorted array: '); printArray(arr, n); // This code is contributed shivanisinghss2110>
PHP 
 // PHP Optimized implementation // of Bubble sort // An optimized version of Bubble Sort function bubbleSort(&$arr) { $n = sizeof($arr); // Traverse through all array elements for($i = 0; $i < $n; $i++) { $swapped = False; // Last i elements are already // in place for ($j = 0; $j < $n - $i - 1; $j++) { // Traverse the array from 0 to // n-i-1. Swap if the element  // found is greater than the // next element if ($arr[$j]>$arr[$j+1]) { $t = $arr[$j]; $arr[$j] = $arr[$j+1]; $arr[$j+1] = $t; $swapped = 참; } } // 내부 루프에 의해 // 두 요소가 교환되지 않은 경우, break if ($swapped == False) break; } } // 드라이버 코드 $arr = array(64, 34, 25, 12, 22, 11, 90); $len = 크기($arr); 버블정렬($arr); echo '정렬된 배열: 
'; for($i = 0; $i< $len; $i++) echo $arr[$i].' '; // This code is contributed by ChitraNayal. ?>>
산출 
Sorted array: 11 12 22 25 34 64 90>

버블 정렬의 복잡성 분석 :

시간 복잡도: 에2)
보조 공간: 오(1)

버블 정렬의 장점:

  • 버블 정렬은 이해하고 구현하기 쉽습니다.
  • 추가 메모리 공간이 필요하지 않습니다.
  • 이는 안정적인 정렬 알고리즘입니다. 즉, 동일한 키 값을 가진 요소는 정렬된 출력에서 ​​상대적 순서를 유지합니다.

버블 정렬의 단점:

  • 버블정렬의 시간복잡도는 O(N2) 이로 인해 대규모 데이터 세트의 경우 속도가 매우 느려집니다.
  • 버블 정렬은 비교 기반 정렬 알고리즘입니다. 즉, 입력 데이터 세트에 있는 요소의 상대적 순서를 결정하려면 비교 연산자가 필요합니다. 특정 경우에는 알고리즘의 효율성이 제한될 수 있습니다.

버블 정렬과 관련된 일부 FAQ:

버블 정렬의 경계 사례는 무엇입니까?

버블 정렬은 요소가 이미 정렬되어 있는 경우 최소 시간(n 순서)이 걸립니다. 따라서 O(N을 피하기 위해 배열이 이미 정렬되어 있는지 미리 확인하는 것이 가장 좋습니다.2) 시간 복잡도.

버블 정렬에서는 정렬이 이루어지나요?

예, 버블 정렬은 주요 데이터 구조를 사용하지 않고 인접한 쌍의 교환을 수행합니다. 따라서 버블 정렬 알고리즘은 내부 알고리즘입니다.

버블정렬 알고리즘은 안정적인가요?

예, 버블 정렬 알고리즘은 안정적입니다.

버블정렬 알고리즘은 어디에 사용되나요?

단순성으로 인해 버블 정렬은 정렬 알고리즘의 개념을 소개하는 데 자주 사용됩니다. 컴퓨터 그래픽에서는 거의 정렬된 배열에서 작은 오류(예: 요소 두 개만 교체)를 감지하고 선형 복잡도(2n)로 수정하는 기능으로 유명합니다.

예: 경계선이 특정 스캔 라인(x축에 평행한 선)에서 x 좌표를 기준으로 정렬되고 y가 증가함에 따라 순서가 변경되는(두 요소가 교체됨) 다각형 채우기 알고리즘에 사용됩니다. 두 선의 교차점에서.

관련 기사:

  • 재귀 버블 정렬
  • 정렬을 위한 코딩 연습
  • 버블정렬에 관한 퀴즈
  • 버블 정렬의 복잡성 분석