BubbleSort 使用 do-while 循环实现

huangapple go评论57阅读模式
英文:

BubbleSort implemented with do-while loop

问题

我正在学习基本的排序算法。我写了以下的代码,但不确定为什么它从不完全排序?我认为只有在遍历整个数组而不需要排序时,它才会满足退出条件(标志未设置为1)。

void bubbleSort(int lst[], int size)
{
    int flag;
    do{
    for(int i = 0; i < size-1; i++)
    {
        flag = 0; //尚未排序
        int temp = lst[i];
        if(lst[i] > lst[i + 1])
        {
            //交换值
            int temp = lst[i];
            lst[i] = lst[i + 1];
            lst[i+1] = temp;
            flag = 1; //排序发生,设置标志
        }

    }
    }while (flag != 0);
}
英文:

I am learning basic sorting algorithms. I wrote below but no sure why it never completely sorts it? I thought it would only meet the exit criteria (flag not set to 1) if it iterates over the entire array with no sorting needed.

void bubbleSort(int lst[], int size)
{
    int flag; 
    do{
    for(int i = 0; i &lt; size-1; i++) 
    {
        flag = 0; //nothing sorted yet 
        int temp = lst[i];
        if(lst[i] &gt; lst[i + 1])
        {
            //swap values  
            int temp = lst[i]; 
            lst[i] = lst[i + 1];
            lst[i+1] = temp; 
            flag = 1; //sort happened set flag 
        }

    }
    }while (flag != 0); 
}

答案1

得分: 5

你已经快要完成了。你只需要把初始化标志(flag)的位置移到这里:

void bubbleSort(int lst[], int size) {
    int flag;
    do {
        flag = 0; //尚未排序
        for(int i = 0; i < size-1; i++) {
            int temp = lst[i];
            if(lst[i] > lst[i + 1]) {
                //交换值
                int temp = lst[i];
                lst[i] = lst[i + 1];
                lst[i+1] = temp;
                flag = 1; //排序发生,设置标志
            }
        }
    } while (flag != 0);
}

如果你在for循环内部将flag设置为0,那么每当你在if内设置flag时,标志将在for循环的下一次迭代中被重置。

英文:

You were almost there. All you need to do is move where you initialize the flag:

void bubbleSort(int lst[], int size) {
    int flag;
    do {
        flag = 0; //nothing sorted yet
        for(int i = 0; i &lt; size-1; i++) {
            int temp = lst[i];
            if(lst[i] &gt; lst[i + 1]) {
                //swap values
                int temp = lst[i];
                lst[i] = lst[i + 1];
                lst[i+1] = temp;
                flag = 1; //sort happened set flag
            }
        }
    } while (flag != 0);
}

If you set flag to 0 within the for loop, then any time you set flag within the if, the flag will get reset on the next iteration of the for loop.

答案2

得分: 1

以下是已翻译的代码部分:

#include <iostream>
#include <span>
#include <vector>

// 永远不要使用:using namespace std;

void bubbleSort(std::span<int> values)
{
    //int flag; 使用更好的名称和布尔类型
    // 这将使您的代码更可读
    bool something_got_sorted{ false };

    // 不要相信输入,因此验证是否可以进行排序
    // 对于大小为0或1的数组,您的原始代码将无效
    if (values.size() < 2) return;

    do
    {
        something_got_sorted = false;

        for (std::size_t i = 0; i < values.size() - 1ul; ++i)
        {
            if (values[i] > values[i + 1ul])
            {
                // C++有一个交换函数,因此使用它会使代码更易读
                // 每当您必须写注释时,请删除它并制作一个
                // 或使用一个具有可读名称的函数(基于您在注释中将要输入的内容)
                std::swap(values[i], values[i + 1]);
                something_got_sorted = true;
            }
        }
    } while (something_got_sorted);
}

int main()
{
    // 输入数组(请注意不是“C”样式数组)
    std::vector<int> values{ 9,3,5,6,4,2,1,0,8,7 };

    // 注意大小不必分开传递
    bubbleSort(values);

    for (const auto value : values)
    {
        std::cout << value << " ";
    }

    return 0;
}

希望这对您有所帮助。如果您需要进一步的翻译或解释,请随时提问。

英文:

Like the answer fro David, but now in a more C++ style with some coding advices. Like checking your input, using std::span, std::vector, std::swap and in the output a range based for loop

#include &lt;iostream&gt;
#include &lt;span&gt;
#include &lt;vector&gt;

// never use : using namespace std;

void bubbleSort(std::span&lt;int&gt; values)
{
	//int flag; Use a better name and a boolean type
	// it will make your code more readable
	bool something_got_sorted{ false };

	// never trust your input so validate if sorting can happen
	// your original code would be invalid for an array of size 0 or 1
	if (values.size() &lt; 2) return;

	do
	{
		something_got_sorted = false;

		for (std::size_t i = 0; i &lt; values.size() - 1ul; ++i)
		{
			if (values[i] &gt; values[i + 1ul])
			{
				// C++ has a swap function so use it makes the code more readable too
				// anytime you have to write a comment remove it and make
				// or use a function with a readable name (based on what you would have typed in the comment)
				std::swap(values[i], values[i + 1]);
				something_got_sorted = true;
			}
		}
	} while (something_got_sorted);
}

int main()
{
	// input array (note note a &quot;C&quot; style array)
	std::vector&lt;int&gt; values{ 9,3,5,6,4,2,1,0,8,7 };

	// note size does not have to be passed seperately
	bubbleSort(values);

	for (const auto value : values)
	{
		std::cout &lt;&lt; value &lt;&lt; &quot; &quot;;
	}

	return 0;
}

答案3

得分: 0

问题本身在于它的 flag,它在每次 for 循环的迭代中都会被初始化。
要修复它,只需将 flag 变量的声明和初始化移到 do while 循环之外。

void bubbleSort(int lst[], int size) {
    int flag = 0; // 为 do 循环初始化
    do {
        flag = 0; // 尚未排序任何内容
        for (int i = 0; i < size - 1; i++) {
            int temp = lst[i];
            if (lst[i] > lst[i + 1]) {
                // 交换值
                lst[i] = lst[i + 1];
                lst[i + 1] = temp;
                flag = 1; // 发生了排序,设置 flag
            }
        }
    } while (flag != 0);
}
英文:

The problem itself is in its flag, which is being initialized at each iteration of the for loop.
To fix just move the declaration and initialization of the flag variable out of the do while loop.

void bubbleSort(int lst[], int size) {
    int flag = 0; // Initialize for do loop
    do {
        flag = 0; // Nothing sorted yet
        for (int i = 0; i &lt; size - 1; i++) {
            int temp = lst[i];
            if (lst[i] &gt; lst[i + 1]) {
                // swap values
                lst[i] = lst[i + 1];
                lst[i + 1] = temp;
                flag = 1; // Sort happened, set flag
            }
        }
    } while (flag != 0);
}

huangapple
  • 本文由 发表于 2023年5月29日 12:52:32
  • 转载请务必保留本文链接:https://go.coder-hub.com/76354756.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定