使用 C 語言的 DSA - 選擇排序

概述

選擇排序是一種簡單的排序演算法。這種排序演算法是一種基於比較的原址演算法，其中列表被分為兩部分，左端的已排序部分和右端的未排序部分。最初，已排序部分為空，未排序部分是整個列表。

從未排序陣列中選擇最小元素並與最左邊的元素進行交換，該元素成為已排序陣列的一部分。此過程繼續將未排序陣列的邊界向右移動一個元素。

該演算法不適用於大型資料集，因為它的平均和最壞情況複雜度都是 O(n²)，其中 n 是項數。

虛擬碼

Selection Sort ( A: array of item)
   procedure selectionSort( A : array of items )
   int indexMin
   for i = 1 to length(A) - 1 inclusive do:
      /* set current element as minimum*/
      indexMin = i    
      /* check the element to be minimum */
      for j = i+1 to length(A) - 1 inclusive do:
         if(intArray[j] < intArray[indexMin]){
             indexMin = j;
         }
      end for
      /* swap the minimum element with the current element*/
      if(indexMin != i) then
         swap(A[indexMin],A[i])
      end if
   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 selectionSort(){
   int indexMin,i,j;       
   // loop through all numbers 
   for(i=0; i < MAX-1; i++){ 
      // set current element as minimum 
      indexMin = i;
      // check the element to be minimum 
      for(j=i+1;j<MAX;j++){
         if(intArray[j] < intArray[indexMin]){
            indexMin = j;
         }
      }
      if(indexMin != i){
         printf("Items swapped: [ %d, %d ]\n" ,intArray[i],intArray[indexMin]);
         // swap the numbers 
         int temp=intArray[indexMin];
         intArray[indexMin] = intArray[i];
         intArray[i] = temp;
      }          
      printf("Iteration %d#:",(i+1));
      display();
   }
}
main(){
   printf("Input Array: ");
   display();
   printline(50);
   selectionSort();
   printf("Output Array: ");
   display();
   printline(50);
}

輸出

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

Input Array: [4, 6, 3, 2, 1, 9, 7]
==================================================
   Items swapped: [ 4, 1 ]
iteration 1#: [1, 6, 3, 2, 4, 9, 7]
   Items swapped: [ 6, 2 ]
iteration 2#: [1, 2, 3, 6, 4, 9, 7]
iteration 3#: [1, 2, 3, 6, 4, 9, 7]
   Items swapped: [ 6, 4 ]
iteration 4#: [1, 2, 3, 4, 6, 9, 7]
iteration 5#: [1, 2, 3, 4, 6, 9, 7]
   Items swapped: [ 9, 7 ]
iteration 6#: [1, 2, 3, 4, 6, 7, 9]
Output Array: [1, 2, 3, 4, 6, 7, 9]
==================================================