مشکل در برنامه نوسی مرتب سازی ادغامی

[Transporter2009]

با عرض سلام خدمت دوستان همیشه همراه.

من برای درس طراحی الگوریتم باید الگوریتم مرتب سازی ادغامی رو به C++‎‎‎ بنویسم. اما یه جا از شبه کد رو نمیدونم چطوری باید بنویسم. اگر میشه راهنماییم بفرمایید.

void mergsort (int n , keytype S [ ])
{
const int h = Į n/2 ⌡ , m = n – h;
keytype U [1...h],V [1..m];
if (n >1) {
copy S[1] through S[h] to U[h];
copy S [h + 1] through S[h] to V[1] through V[m];
mergesort(h, U);
mergesort(m,V);
merge (h , m , U,V,S);
}
}

void merg ( int h , int m, const keytype U[ ],
const keytype V[ ],
keytype S[ ] )
{
index i , j , k;
i = 1; j = 1 ; k = 1;
while (i <= h && j <= m) {
if (U [i] < V [j]) {
S [k] = U [i]
i+ + ;
}
else {
S [k] = V [j];
j++;
}
k++;
}
if ( i > h)
copy V [j] through V [m] to S [k] through S [ h + m ]
else
copy U [i] through U [h] to S [k] through S [ h + m ]


قسمت هایی که Bold (با تگ <b> مشخص شده اند) شده اند مشکل دارم.

پیشاپیش ممنونم

[shahmohammadi]

سلام. معنی انگلسی منظورتون هست.
<b> copy S[1] through S[h] to U[h]; copy S [h + 1] through S[h] to V[1] through V[m];</b>


یعنی ازS1 تا Sh رو بذار توی U
بقیه ی s رو بذار توی v
<b> copy V [j] through V [m] to S [k] through S [ h + m ] else
copy U [i] through U [h] to S [k] through S [ h + m ] </b>


از Vj تا Vm رو بذار توی s (از خونه ی کا تا اچ + ام)
از خونه ی i تا h یو رو بذار از خونه ی k تا h+m از آرایه ی s.

[Transporter2009]

سلام. معنی انگلسی منظورتون هست.
<b> copy S[1] through S[h] to U[h]; copy S [h + 1] through S[h] to V[1] through V[m];</b>


یعنی ازS1 تا Sh رو بذار توی U
بقیه ی s رو بذار توی v
<b> copy V [j] through V [m] to S [k] through S [ h + m ] else
copy U [i] through U [h] to S [k] through S [ h + m ] </b>


از Vj تا Vm رو بذار توی s (از خونه ی کا تا اچ + ام)
از خونه ی i تا h یو رو بذار از خونه ی k تا h+m از آرایه ی s.

بله دقیقاً. میشه همین رو به زبان c++ بنویسید؟
ممنون

[shahmohammadi]

خب حالا که منظورشو می دونید که بقیش راحته. برای هر کدوم از حالات یه حلقه ی فور بنویسید.

[Transporter2009]

خب حالا که منظورشو می دونید که بقیش راحته. برای هر کدوم از حالات یه حلقه ی فور بنویسید.

دست شما درد نکنه. برنامه رو نوشتم ولی توی مقدار دهی ثابت مثل اینکه مشکل داره. نفهمیدم باید چی کار کنم. مقدار h و m زو هم وقتی مثلا به صورت ثابت 5 وارد می کنم Stack Overflow میده.

چه باید کرد؟

void merge(int h, int m, const int U[], const int V[], int S[]){
int i, j, k;
i = 1; j = 1; k = 1;
while (i <= h && j <= m){
if (U[i] < V[j]){
S[k] = U[i];
i++;
}
else{
S[k] = V[j];
j++;
}
k++;
} //end of While
if (i>h){
for (j = k; j <= h + m; j++){
S[j] = V[j];
}
}
else{
for (i = k; i <= h + m; i++){
S[j] = V[j];
}
}
}


void mergesort(int n, int S[])
{
const int h = n / 2, m = n - h;
int U[h], V[m];
if (n > 1){
for (int i = 1; i <= h; i++){
U[i] = S[i];
}
for (int j = h + 1; j <= n; j++){
V[j] = S[j];
}
}
mergesort(h, U);
mergesort(m, V);
merge(h, m, U, V, S);
}


//The main function
int main()
{
int S[10] = { 2, 5, 6, 4, 7, 2, 8, 3, 9, 10 };


mergesort(10, S);


//Print the sorted array
for (int i = 0; i < 10; i++)
{
cout << S[i] << endl;
}


system("PAUSE");
exit:
return 0;
}

[shahmohammadi]

اول اینکه باید عبارت زیر رو مثل الگوریتم بیاری به داخل شرط:
mergesort(h, U);
mergesort(m, V);
merge(h, m, U, V, S);

دوم اینکه توی سی اندیس ها از 0 شروع میشه ولی توی الگوریتم از 1.
سوم اینکه توی حلقه ی فور برای مثلا S و V از یه اندیس استفاده نکن:
مثلا:
void mergesort(int n, int S[])
{
int h = n / 2, m = n - h;
int U[h], V[m];
if (n > 1){
for (int i = 0; i < h; i++){
U[i] = S[i];
}
for (int j = 0; j < m; j++){
V[j] = S[j+h];
}
mergesort(h, U);
mergesort(m, V);
merge(h, m, U, V, S);
}

}

بقیه ی فورها هم باید به همین شکل اصلاح شوند.

موفق باشید.