PDA

View Full Version : سوال: تغییری در الگوریتم مرتب سازی ادغامی merge sort



saberziaei
پنج شنبه 28 اردیبهشت 1396, 21:44 عصر
عزیزان سلام
اگه بخواهیم در الگوریتم merge sort بجای اینکه آرایه به 2 قسمت تقسیم شود بیایم یک عدد بگیریم از کاربر آرایه به اون تعداد تقسیم بشه و باقیه مراحلش انجام بشه چجوری میشه کدش؟
برای توضیح بیشتر مثلا کاربر عدد 3 را وارد کند.بعد آرایه به سه قسمت تقسیم شود.
اگه امکانش هست کسی کدشو بنویسه کامل

این کد merge sort .دوستان بفرمایید کجاشو و چگونه باید تغییر داد تا به این موضوعی که گفتم برسم


using System;
using System.Collections.Generic;
using System.Text;

namespace sortMerge
{
class mergeSort
{
// array of integers to hold values
private int[] a = new int[100];
private int[] b = new int[100];

// number of elements in array
private int x;

// Merge Sort Algorithm
public void sortArray()
{
m_sort(0, x - 1);
}

public void m_sort(int left, int right)
{
int mid;

if (right > left)
{
mid = (right + left) / 2;
m_sort(left, mid);
m_sort(mid + 1, right);

merge(left, mid + 1, right);
}
}

public void merge(int left, int mid, int right)
{
int i, left_end, num_elements, tmp_pos;

left_end = mid - 1;
tmp_pos = left;
num_elements = right - left + 1;

while ((left <= left_end) && (mid <= right))
{
if (a[left] <= a[mid])
{
b[tmp_pos] = a[left];
tmp_pos = tmp_pos + 1;
left = left + 1;
}
else
{
b[tmp_pos] = a[mid];
tmp_pos = tmp_pos + 1;
mid = mid + 1;
}
}

while (left <= left_end)
{
b[tmp_pos] = a[left];
left = left + 1;
tmp_pos = tmp_pos + 1;
}

while (mid <= right)
{
b[tmp_pos] = a[mid];
mid = mid + 1;
tmp_pos = tmp_pos + 1;
}

for (i = 0; i < num_elements; i++)
{
a[right] = b[right];
right = right - 1;
}
}

public static void Main()
{
// Instantiate an instance of the class
mergeSort mySort = new mergeSort();

Console.WriteLine(" \n ************ WWW.SourceCodes.ir ************ ");
Console.WriteLine("__________________________________________________ _");

// Get the number of elements to store in the array
Console.Write("\n Number of elements in the array (less than 100) : ");
string s = Console.ReadLine();
mySort.x = Int32.Parse(s);

// Array header
Console.WriteLine("");
Console.WriteLine("-----------------------");
Console.WriteLine(" Enter array elements ");
Console.WriteLine("-----------------------");

// Get array elements
for (int i = 0; i < mySort.x; i++)
{
Console.Write("<{0}> ", i + 1);
string s1 = Console.ReadLine();
mySort.a[i] = Int32.Parse(s1);
}

// Sort the array
mySort.sortArray();

// Output sorted array
Console.WriteLine("");
Console.WriteLine("-----------------------");
Console.WriteLine(" Sorted array elements ");
Console.WriteLine("-----------------------");

for (int j = 0; j < mySort.x; j++)
{
Console.WriteLine(mySort.a[j]);
}

// Here to stop app from closing
Console.WriteLine("\n\nPress Return to exit.");
Console.Read();
}
}
}

ژیار رحیمی
جمعه 29 اردیبهشت 1396, 00:27 صبح
سلام. در هر صورت که بخوای آرایه اصلی رو به سه چند قسمت تقسیم کنی باز همان الگوریتم هست که ابتدا بخش اول و دم آرایه ادغام سپس نتیجه رو با بخش سوم ادغام میشود.اگر هدف شما بالا بردن سرعت ادغام درآرایه های بزرگ هست با این شیوه بهبودی در اجرای سرعت انجام نمیشود بهتر است از موازی سازی به وسیله چند Thread الگوریتم رو اصلاح کنی.

saberziaei
جمعه 29 اردیبهشت 1396, 23:05 عصر
مثلا اگه روی این کد بخواهیم الگوریتم گفته شده رو پیاده سازی کنیم بچصورت قابل انجام است؟
Algorithm: Sort (L, first, last)
Where L: array of elements
first: lower bound of L
last: higher bound of L

Step 1: Initialise
i. n=last-first+1

Step 2: Check L size n
i. if n<=1
a) Goto Step 4

Step 3: If first<last
i. Call func(L,fisrt,last)
ii. Mid=(first+last)/2
iii. Call Sort(L,first,mid)
iv. Call Sort(L,mid+1,last)
v. Call merge(L,first,mid,mid+1,last)

Step 4: Exit


Sub-Algorithm: func (L,first,last)

Step 1: Initialise
i. m=0
ii. k=first

Step 2: Repeat while k<=last
i. If L[k]>L[k+1]
a) temp=L[k]
b) L[k]=L[k+1]
c) L[k+1]=temp
ii. k=k+2

Step 3: Initialise k=first+1
i. Repeat while k<=last
a) A[m]=L[k]
b) m=m+1
c) k=k+2

Step 4: Initialise x=first and k=first
i. Repeat while k<=last
a) L[x]=L[k]
b) x=x+1
c) k=k+2

Step 5: Initialise k=0
i. Repeat while k<m
a) L[x]=A[k]
b) x=x+1
c) k=k+1

Sub-Algorithm: Merge (L, first, mid, mid+1, last)

Step 1: Initialise i=first, j=mid+1 and k=0

Step 2: Repeat while i<=mid and j<=last
i. If L[i]<L[j]
a) temp[k++]=L[i++]
ii. Else
a) temp[k++]=L[j++]

Step 3: Repeat while i<=mid
i. temp[k++]=L[i++]

Step 4: Repeat while j<=last
i. temp[k++]=L[j++]

Step 5: Initialise i=first and j=0
i. Repeat while i<=last
a) L[i]=temp[j]
b) i=i+1
c)
j=j+1