局部变量失去其值:选择排序算法

Question

我之前测试了相同的变量，称为“交换”的气泡排序算法，它运行得很好。现在，通过选择排序，变量即使在增量之后也会失去它的值。任何帮助都将不胜感激。

int list[] = {10, 5, 6, 3, 4, 11, 9, 7, 2};
int min = list[0], pos = 0, temp_max = 0;

// Loop until no swap is needed
for (int j = 0, n = sizeof(list) / sizeof(int); j < n; j++)
{
    int swaps = 0, 

    // Iterate through array to find min value
    for (int i = j, y = sizeof(list) / sizeof(int); i < y; i++)
    {
        if (list[i] < min)
        {
            min = list[i];
            pos = i;
        }
    }

    // Insert min value in left most position and add 1 to swaps, meaning array is not yet sorted
    if (pos > j)
    {
        temp_max = list[j];
        list[j] = min;
        list[pos] = temp_max;
        swaps++;
    }

    // The error might occur here: "swaps" keeping value 0 after previous if statement ends
    printf ("swaps = %d\n", swaps);

    // If no swaps ocurred, array is sorted
    if (swaps == 0)
    {       
        // Print sorted array and return  
    }
}

Answer 1

添加到其他答案中，这将用您的代码专门解决问题，您还可以像下面这样处理选择排序算法。

为数组编写此算法的步骤：

1.编写一个助手函数来查找数组中最大元素的索引：

size_t index_of_largest(int list[], size_t n) {
    size_t i, biggest;

    biggest = 0;
    for (i = 0; i < n; i++) {
        if (list[i] > list[biggest]) {
            biggest = i;
        }
    }
    return biggest;
}

2.遍历i=n到i=1，找到list[0]和list[i-1]之间的最大值。找到此元素后，将其交换到最后一个位置。该函数可以如下所示：

void sort_list(int list[], size_t n) {
    size_t i, biggest;

    for (i = n; i > 0; i--) {
        biggest = index_of_largest(list, i);
        int_swap(&list[biggest], &list[i-1]); /* swapping function */
    }
}

3.考虑到这些想法，您可以编写算法的简单版本如下：

#include <stdio.h>

void sort_list(int list[], size_t n);
size_t index_of_largest(int list[], size_t n);
void print_array(int list[], size_t n);
void int_swap(int *x, int *y);

int main(void) {
    int list[] = {10, 5, 6, 3, 4, 11, 9, 7, 2};
    size_t n = sizeof list / sizeof *list;

    printf("Before: ");
    print_array(list, n);

    sort_list(list, n);

    printf("After: ");
    print_array(list, n);

    return 0;
}

void sort_list(int list[], size_t n) {
    size_t i, biggest;

    for (i = n; i > 0; i--) {
        biggest = index_of_largest(list, i);
        int_swap(&list[biggest], &list[i-1]);
    }
}

size_t index_of_largest(int list[], size_t n) {
    size_t i, biggest;

    biggest = 0;
    for (i = 0; i < n; i++) {
        if (list[i] > list[biggest]) {
            biggest = i;
        }
    }
    return biggest;
}

void print_array(int list[], size_t n) {
    size_t i;

    for (i = 0; i < n; i++) {
        printf("%d ", list[i]);
    }
    printf("\n");
}

void int_swap(int *x, int *y) {
    int temp;
    temp = *x;
    *x = *y;
    *y = temp;
}

输出：

Before: 10 5 6 3 4 11 9 7 2
After: 2 3 4 5 6 7 9 10 11

编撰：

gcc -Wall -Wextra -o progname progname.c

Answer 2

将声明int swaps = 0移到for循环之外。

换句话说，改变这一点：

for (int j = 0, n = sizeof(list) / sizeof(int); j < n; j++)
{
    int swaps = 0;
    ...
}

对此：

int swaps = 0;
for (int j = 0, n = sizeof(list) / sizeof(int); j < n; j++)
{
    ...
}

Answer 3

我非常感谢大家。我在你的帮助下解决了这个问题。结果表明，错误与变量作用域(声明它的位置)有关。遵循下面的工作代码。

int main (void)
{

//Declare list to be sorted and other variables
int list[] = {9, 5, 7, 8, 4, 3, 2, 1, 6};
int minValPos = 0, maxTempVal = list[0];

for (int j = 0, siz = sizeof (list) / sizeof (int); j < siz; j++)
{
    int swaps = 0, minVal = list[j];

    // Look for min value after each j iteration
    for (int i = j; i < siz; i++)
    {

        // Find minimum value (minVal) and store its position (minValPos)
        if (list[i] < minVal)
        {
            minVal = list[i];
            minValPos = i;
        }

    }

    // Once with MinVal pinpointed, proceed to swap with jth item
    if (minValPos > j)
    {
        maxTempVal = list[j];
        list[j] = minVal;
        list[minValPos] = maxTempVal;
        swaps++;
    }

    // When array did not need any swaps, it means it is sorted
    if (swaps == 0)
    {
        for (int r = 0; r < siz; r++)
        {
            printf ("Position [%d] = %d\n", r, list[r]);
        }
    }
}

}