使用 C 語言實現的 DSA - 氣泡排序

概述

氣泡排序是一種簡單的排序演算法。這種排序演算法是基於比較的演算法，該演算法對每一對相鄰的元素進行比較，如果元素未按順序排序，則交換元素。此演算法不適用於大型資料集，因為它的平均情況和最壞情況複雜度均為 O(n²)，其中 n 是專案數量。

虛擬碼

procedure bubbleSort( A : array of items )
   for i = 1 to length(A) - 1 inclusive do:
      swapped = false
      for j = 1 to length(A) - 1 inclusive do:
         /* compare the adjacent elements */   
         if A[i-1] > A[i] then
            /* swap them */
            swap( A[i-1], A[i] )		 
            swapped = true
         end if
      end for
      /*if no number was swapped that means 
      array is sorted now, break the loop.*/
      if(!swapped) then
         break	 
   end for
end procedure

舉例

#include <stdio.h>
#include <stdbool.h>
#define MAX 7

int intArray[MAX] = {4,6,3,2,1,9,7};
void printline(int count){
   int i;
   for(i=0;i <count-1;i++){
      printf("=");
   }
   printf("=\n");
}
void display(){
   int i;
   printf("[");
   // navigate through all items 
   for(i=0;i<MAX;i++){
      printf("%d ",intArray[i]);
   }
	printf("]\n");
}
void bubbleSort(){
   int temp;
	int i,j;
   bool swapped = false;       
   // loop through all numbers 
   for(i=0; i < MAX-1; i++){ 
      swapped = false;
      // loop through numbers falling ahead 
      for(j=1; j < MAX-i; j++){
		   printf("Items compared: [ %d, %d ]\n" ,intArray[j-1],intArray[j]);
         // check if next number is lesser than current no
         // swap the numbers. 
         // (Bubble up the highest number) 
         if(intArray[j-1] > intArray[j]){
            temp=intArray[j-1];
            intArray[j-1] = intArray[j];
            intArray[j] = temp;
            swapped = true;
         }           
      }
      // if no number was swapped that means 
      // array is sorted now, break the loop. 
      if(!swapped){
         break;
      }
      printf("Iteration %d#: ",(i+1)); 
      display();                     
   }
}
main(){
   printf("Input Array: ");
   display();
   printline(50);
   bubbleSort();
   printf("Output Array: ");
   display();
   printline(50);
}

輸出

如果我們編譯並執行上述程式，將產生以下輸出 −

Input Array: [4, 6, 3, 2, 1, 9, 7]
==================================================
   Items compared: [ 4, 6 ]
   Items compared: [ 6, 3 ]
   Items compared: [ 6, 2 ]
   Items compared: [ 6, 1 ]
   Items compared: [ 6, 9 ]
   Items compared: [ 9, 7 ]
Iteration 1#: [4, 3, 2, 1, 6, 7, 9]
   Items compared: [ 4, 3 ]
   Items compared: [ 4, 2 ]
   Items compared: [ 4, 1 ]
   Items compared: [ 4, 6 ]
   Items compared: [ 6, 7 ]
Iteration 2#: [3, 2, 1, 4, 6, 7, 9]
   Items compared: [ 3, 2 ]
   Items compared: [ 3, 1 ]
   Items compared: [ 3, 4 ]
   Items compared: [ 4, 6 ]
Iteration 3#: [2, 1, 3, 4, 6, 7, 9]
   Items compared: [ 2, 1 ]
   Items compared: [ 2, 3 ]
   Items compared: [ 3, 4 ]
Iteration 4#: [1, 2, 3, 4, 6, 7, 9]
   Items compared: [ 1, 2 ]
   Items compared: [ 2, 3 ]
Output Array: [1, 2, 3, 4, 6, 7, 9]
==================================================