使用函數實現選擇排序？

Question

我正在執行選擇排序算法步驟。

我做了兩個函數：一個用於查找最小值的索引，另一個用於selection_sort。

輸出不正確。我找出了這個錯誤，但我不知道如何解決這個問題。 錯誤在find_min函數中。我想我必須更新索引？

請幫忙。

int find_min(int ar[], int size) 
{ 
    int index = 0; 
    bool found = false; 
    for(int i = 1; i < size; i++) 
    { 
     if(ar[index] > ar[i]) 
     { 
      index = i; 
      found = true; 
     } 
    } 

    if (found) 
    { 
     return index; 
    } 
    else 
     return -1; 

} 

void selection_sort(int arr[], int size) 
{ 
    int loc; 
    for(int count = 0; count < size; count++) 
    { 
     loc = find_min(arr, size - count); 
     if (loc >= 0) 
     { 
      exchange(arr[count], arr[loc]); 
     } 
    } 
} 

Answer 1

考慮下面的代碼：

#include <iostream> 

using namespace std; 

// Exchanges two values in array arr, specified by indices i and j 
void exchange(int arr[], int i, int j) 
{ 
    int t = arr[i]; 
    arr[i] = arr[j]; 
    arr[j] = t; 
} 

// Prints an array arr of length len 
void print_array(int arr[], int len) 
{ 
    for(int i=0; i<len; i++) 
    { 
     cout << arr[i] << " "; 
    } 
    cout << endl; 
} 

// Finds the index of the minimum value in array arr of length len between indices 
// init and the last element (len-1) 
int find_min(int arr[], int len, int init) 
{ 
    int index = init; 

    for(int i = init; i < len; i++) 
    { 
     if(arr[index] > arr[i]) 
     { 
      index = i; 
     } 
    } 

    return index; 
} 

// Sort the array using the selection sort algorithm 
void selection_sort(int arr[], int len) 
{ 
    int loc; 
    // We don't need the last iteration when there is only a single element left 
    for(int pos = 0; pos < (len-1); pos++) 
    { 
     cout << "Before iteration " << pos << " array is: "; 
     print_array(arr, len); 

     loc = find_min(arr, len, pos); 
     cout << " Minimum between indices " << pos << " and " << (len-1) << " is: "; 
     cout << arr[loc] << " at index " << loc << endl; 

     if (loc != pos) 
     { 
      cout << " Exchanging indices " << loc << " and " << pos << endl; 
      exchange(arr, pos, loc); 
     } 
     else 
     { 
      cout << " No exchange necessary this iteration. " << endl; 
     } 

     cout << "After iteration " << pos << " array is: "; 
     print_array(arr, len); 

     // Print an extra line newline, space things out a bit 
     cout << endl; 
    } 
} 


int main(void) 
{ 
    int arr[] = {2,6,7,3,1,8}; 

    selection_sort(arr, 6); 
} 

輸出：

 
Before iteration 0 array is: 2 6 7 3 1 8 
    Minimum between indices 0 and 5 is: 1 at index 4 
    Exchanging indices 4 and 0 
After iteration 0 array is: 1 6 7 3 2 8 

Before iteration 1 array is: 1 6 7 3 2 8 
    Minimum between indices 1 and 5 is: 2 at index 4 
    Exchanging indices 4 and 1 
After iteration 1 array is: 1 2 7 3 6 8 

Before iteration 2 array is: 1 2 7 3 6 8 
    Minimum between indices 2 and 5 is: 3 at index 3 
    Exchanging indices 3 and 2 
After iteration 2 array is: 1 2 3 7 6 8 

Before iteration 3 array is: 1 2 3 7 6 8 
    Minimum between indices 3 and 5 is: 6 at index 4 
    Exchanging indices 4 and 3 
After iteration 3 array is: 1 2 3 6 7 8 

Before iteration 4 array is: 1 2 3 6 7 8 
    Minimum between indices 4 and 5 is: 7 at index 4 
    No exchange necessary this iteration. 
After iteration 4 array is: 1 2 3 6 7 8 

Answer 2

解決您的find_min功能

int find_min(int ar[],int s, int size) // s denotes the start index 
{ 
    int index = s-1; //take min pos as start 
    bool found = false; 
    for(int i = s; i < size; i++) 
    { 
     if(ar[index] > ar[i]) 
     { 
      index = i; 
      found = true; 
     } 
    } 

    if (found) 
    { 
     return index; 
    } 
    else 
     return -1; 
} 

現在用途： loc = find_min(arr, count+1,size);

因爲直到count ARR已經排序

見HERE