我只是在練習使用向量實作選擇排序。但它回傳的向量與我作為輸入給出的向量相同。
此實作適用于陣列，但不適用于向量。
#include<bits/stdc .h>
using namespace std;
vector<int> insertionSort(vector<int> v, int n)
{
for(int i=1;i<=n-1;i )
{
int currentEle = v[i];
int prevEle = i-1;
// right index where current is inserted
while(prevEle>=0 and v[prevEle]>currentEle){
v[prevEle 1] = v[prevEle];
prevEle = prevEle-1;
}
v[prevEle 1] = currentEle;
}
return v;
}
int main()
{
int n;
cin>>n;
vector<int> v(n);
for(int i=0;i<n;i )
{
cin>>v[i];
}
insertionSort(v,n);
for(auto x: v)
{
cout<<x<<" ";
}
//OUTPUTS
Input : 5 3 1 2 4
Expected Output : 1 2 3 4 5
My Output : 5 3 1 2 4
是否有使用相同演算法使用選擇排序對向量進行排序的特定方法？
uj5u.com熱心網友回復：
您沒有將回傳的向量存盤insertionSort到任何內容中。
你可以做：
std::vector<int> result = insertionSort(v,n);
代替：
insertionSort(v,n);
然后列印result而不是v
for (auto &x : result) {
std::cout << x << " ";
}
其他一些與問題無關但有幫助的要點。
- 使用
using namespace std被認為是一種不好的做法 - 為什么你不應該使用
#include<bits/stdc .h>
uj5u.com熱心網友回復：
我的問題的解決方案是使用向量作為值或參考
vector<int> insertionSort(vector<int> &v, int n)
在按參考傳遞中，實際引數傳遞給函式。如果按值傳遞引數值復制到另一個變數。所以最好的方法是使用向量作為參考
uj5u.com熱心網友回復：
您正在按值將向量傳遞給insertSort函式，但在主函式中，您沒有收集回傳值。您最終列印了相同的輸入向量v，因此，您將獲得相同的輸出。
所以你的主要功能應該是這樣的。
int main()
{
int n;
cin>>n;
vector<int> v(n);
for(int i=0;i<n;i )
{
cin>>v[i];
}
auto sortedVector = insertionSort(v,n);
for(auto x: sortedVector)
{
cout<<x<<" ";
}
return 0;
}
uj5u.com熱心網友回復：
讓我們像除錯器一樣單步除錯您的代碼。在這里，我們將在insertionSort(v,n);即將被呼叫的行上放置一個斷點。我們假設用戶已經輸入了有效的未排序輸入整數。我會{3,2,9,5,7}隨意使用在您的情況下無關緊要的向量。
我們將按照您的除錯器的方式進入代碼，現在這將因您的特定編譯器和除錯器工具而異，但為了簡單起見，我們可以根據 C 語言的規則概括這里發生的事情。
這里的問題不是在運行時發生的。這里的問題發生在編譯時。它仍然是有效的代碼，因為沒有生成編譯錯誤，因此您認為它一定是運行時錯誤，因為您沒有獲得正確的輸出。
在這里您必須了解 C 編譯器如何解釋函式宣告/定義和函陣列合。編譯時，它會查找您宣告為insertionSort()必須在首次使用前定義的函式。在你的情況下是這樣。您在代碼的第 3 行宣告并定義了它。接下來它必須確定它的回傳型別和引數型別是否匹配。
您在第 30 行的呼叫站點： insertionSort(v,n);
在第 3 行找到匹配的宣告/定義：vector<int> insertionSort(vector<int> v, int n);它回傳 a，vector<int>但在 C 中，在函式的呼叫位置可以忽略回傳型別。接下來是引數型別，因為它采用 avector<int>和int型別 by value。
當您的源代碼被編譯成目標代碼，然后鏈接并翻譯成程式集時。這里發生的事情是，如果您不使用指標或動態記憶體（堆），則此函式將具有自己的堆疊幀，其中這些變數僅可見，并且在此函式的作用域內具有生命周期。
當此函式回傳呼叫站點時，這些變數將被銷毀。此外，按值傳遞通常會導致傳入值的副本。
下面是此函式的堆疊幀可能的樣子： 在這里，我將在措辭演算法圖中使用偽匯編助記符。現在，這是現代硬體的簡化，這是由于編譯器優化和具有多個快取的現代硬體以及可以忽略的向量內在函式，因為它們超出了此處發生的范圍。
- rsp -> 注冊堆疊指標
- ret -> 從程序回傳
- rpt -> 堆疊幀的程序回傳指標
- r0 -> 零暫存器
- [r1 - rn] -> 任意多用途暫存器
- mov -> 操作碼或指令，通過立即值或其他暫存器或記憶體位置將值移動、存盤或加載到某個暫存器中。
//Stack Frame:
{
// Setup the stack and frame pointers... internal housekeeping
// Return Type Setup: vector<int>
rpt assigned to the first value in `vector<int>`
// this is reserved memory specifically for return values
// Parameter Type Setup: vector<int>, int
// n's initialized value stored in reg1
mov r1, n's value
// values to be stored {3,2,9,5,7}
mov r2, 3
mov r3, 2
mov r4, 9
mov r5, 5
mov r6, 7
/* Function Implementation. Not going to convert this to assembly
However, it will use the rpt pointer to construct the new
vector that is local to this function after the necessary
checks are performed...
for(int i=1;i<=n-1;i )
{
int currentEle = v[i];
int prevEle = i-1;
// right index where current is inserted
while(prevEle>=0 and v[prevEle]>currentEle){
v[prevEle 1] = v[prevEle];
prevEle = prevEle-1;
}
v[prevEle 1] = currentEle;
}
*/
// Make sure that shared registers are reassigned or their original values
// are restored before returning from procedure.
// More internal housekeeping...
// Assuming the algorithm is correct and the local registers were assigned
// to the designated memory pointed to by rpt
// Then prt would look something like:
// {rpt[0] = r3, rpt[1] = r2, rpt[2] = r5, rpt[3] = r6, rpt[4] = r1}
ret rpt
}
This is a pseudo example of what your stack frame would look like in assembly sort of. Now, ret is a like a pointer in C/C but in assembly it's a special register that holds a memory address to another register or register segments within the CPU's register files or may even point to cache in modern systems...
Now, within your C code we have reached the end of this function, and it goes out of scope. All local variables are destroyed as that memory is given back to the system and or operating system...
Within the calling of this function you never assign it to any variable from its return value. You passed v into this function by value, and copies are made to the stack. You created a temporary vector internal to this function and performed the sorting algorithm. You return from this function and never use its return value.
In your next line section of C code You are using a ranged based for loop and traversing through main's variable v which was assigned the values {3,2,9,5,7} from the user input.
You passed this into your function by value which is copied information into temporaries. And main's v variable which lives within its own stack frame is never modified. The temporary return variable within insertionSort()' stack frame is the one that was changed.
This isn't a compile time nor a runtime error. This is just a bad implementation design of your algorithm by not fully understanding the specifications of the language and how the compiler treats it.
To fix this function you can drop the return type and pass by reference. The signature will look like this:
void insertionSort(vector<int>& v, int n);
Here a reference to the variable is passed into the function. This time around when your compile sees this and generates the object code later to be translated into assembly. It doesn't make a copy of these values, it uses the same registers or cache lines directly.
In this case, the object being passed into this function can be modified after any computations have been performed on it.
Here's a simple example of a basic integer add function replicating exactly what you have done:
// Pass By Value:
int add(int a, int b) {
a = a b;
return a;
}
int main() {
int a = 3;
int b = 5;
add(a, b);
std::cout << a;
return 0;
}
Here you're expecting to see 8 printed, but in fact a from main is never modified and 3 will be printed to your console and you never used the return value from the function.
Let's check the pass by reference version:
void add(int& a, int b) {
a = a b;
return a;
}
int main() {
int a = 3;
int b = 5;
add(a, b);
std::cout << a;
return 0;
}
In this version because a reference to main's a is used directly within the stack frame of add() main's a will be modified. This time when you print to the console you will see an 8.
I hope this helps to clear up the different ways of passing parameter types into functions within C . You can pass by value, by reference and by pointer and some of them have const versions which is a out of the scope of this topic. Also, do not rely on your parameter or function argument ordering when implementing your algorithms. There is no specification or single use convention or guarantee in how a specific compiler will set up a function's arguments or parameter list when generating the necessary assembly. There are various calling conventions and you would have to know which compiler you are using and what calling convention is being used.
I hope this helps you to understand what is happening with your code, what's going on under the hood at different levels of abstraction and why you are getting the results that you are getting and to help you understand what type of error this is.
Everyone else seems to just say, "passing by value and not reference" assuming you know what they are and mean... I'm treating you as if this was your first day at looking at code or a new language.
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/328472.html