遞迴方式實作選擇排序法

練習以遞迴方式實作 "選擇排序法 (selection sort)"

問題: 將整數陣列中存放的資料由小到大重新排列

選擇排序法分析:

以下圖為例, 陣列中存放 n 筆資料 (array[0], ..., array[n-1]), 首先一一比對得到其中的最大元素, 並且與陣列中最後一個元素 array[n-1] 互換, 如此就只剩下前面 n-1 筆資料需要排序了, 如此繼續把最大的元素挑出來, 讓問題的大小逐步減低, 直到所有元素由小到大排好為止。

遞迴演算法設計:

由上面的演算法描述中可以看到問題的困難度逐步降低, 這很適合運用遞迴方法來設計程式, 在設計遞迴時一般需要專注於
1. 如何擴充戰果, 由 n-1 個元素排序完成的狀態擴充到 n 個元素排序完成的狀態,
　 在 "選擇排序法" 中這個部份就是由 n 個元素的陣列中找到最大的元素;
2. 確定遞迴結束的條件;
3. 呼叫自己完成 n-1 個元素的排序

選擇排序的遞迴演算法:

1. if n is 1
      2. the array is sorted
   else
      3. move the largest element to the last of the array
      4. sort the subarray which excludes the last array element (array[0] .. array[n-2]).

程式實作:

place_largest: (step 3)

void place_largest(int array[],   /* input/output - array in which to place largest 	*/
                   int n)         /* input - number of array elements to consider   	*/
{
    int temp,       /* temporary variable for exchange	*/
        j,          /* array subscript and loop control 	*/
        max_index;  /* index of largest so far 	*/
    
    /*  Save subscript of largest array value in max_index	*/
    max_index = n - 1;     /* assume the last element is the largest	*/
    for  (j = n - 2;  j >= 0;  --j)
        if (array[j] > array[max_index])
            max_index = j;
    
    /*  Unless the largest value is already the last element, exchange 
        the largest and the last elements	*/
    if (max_index != n - 1) 
    {
        temp = array[n - 1];
        array[n - 1] = array[max_index];
        array[max_index] = temp;
    }
}

select_sort: (step 4)

void select_sort(int array[],  /* input/output - array to sort 	*/
                 int n)        /* input - number of array elements to sort	*/
{   
    if (n > 1) 
    {
        place_largest(array, n);
        select_sort(array, n - 1);
    }
}

疊代式選擇排序法實作:

根據步驟 2 直接以兩層迴圈實作選擇排序法

swap 函數:

void swap(int *x, int *y)
{
    int tmp;
    tmp = *x;
    *x = *y;
    *y = tmp;
}

printArrayContents 函數:

void printArrayContents(int data[], int ndata)
{
    int i;
    printf("Sorted data:\n");
    for (i=0; i<ndata; i++)
        printf(" %d", data[i]);
    printf("\n");
}

main 函數以及 swap 及 printArrayContents 函數原型:

#include <stdio.h>
#include <stdlib.h>

void swap(int *, int *);
void printArrayContents(int [], int);

int main(void)
{
    int data[] = {12, 3, 37, 8, 24, 15, 5, 33};
    int ndata = sizeof(data) / sizeof(int);
    int i, j;
    int max;

    for (i=0; i<ndata; i++)
    {
        max = 0;
        for (j=1; j<ndata-i-1; j++)
            if (data[j]>data[max]) max = j;
        swap(&data[max], &data[ndata-i-1]);
    }
    
    printArrayContents(data, ndata);
    system("pause");
    return 0;
}

注意: swap(&data[max], &data[ndata-i-1]) 可以用 swap(data+max, data+ndata-i-1) 取代, 兩者效果完全一樣

遞迴以及疊代程式修改:

請修改步驟 4 的遞迴演算法以及步驟 5 的疊代演算法, 選擇演算法的功能維持由小到大排序資料, 但是如下圖所示, 演算法先找出陣列中最小的元素, 將其與陣列中第一個元素交換, 一步一步完成所有資料的排序:

疊代式演算法的修改比較直接

遞迴式演算法的修改會遇見一個小問題: 如何將陣列第 2 個元素到第 n 個元素當成一個陣列傳遞給函數處理?

其實將陣列傳遞給函數時基本上只是把陣列的起始位址傳遞給函數, 例如: 以 printArrayContents(data, ndata) 呼叫 printArrayContents(int array[], int size); 函數時, 函數中 array 陣列變數其實就是 data 陣列, main() 函數中只是把 data 陣列的起始位址交給 printArrayContents() 函數, 如果在 main() 函數中呼叫 printf("%p", data); 看到的資料和在 printArrayContents() 函數中呼叫 printf("%p", array); 會完全一樣; 所以要把 data[1] 到 data[n-1] 這些元素當成陣列傳遞給函數, 只要寫 printfArrayContents(&data[1], ndata-1) 即可; printArrayContents() 函數宣告的時候參數也可以寫 int printArrayContents(int *array, int size), 在 printArrayContents() 函數中使用 array 的程式碼完全不需要改變; 更進一步如果宣告為 int printArrayContents(int *const array, int size) 則可以防止在 printArrayContents() 函數中不小心修改 array 指標的內容; 如果宣告為 int printArrayConents(const int *const array, int size) 則可以防止在 printArrayContents() 函數中不小心修改 array 陣列的內容。