PDA

View Full Version : گفتگو: ساخت برنامه برای Sorting Network



Coloner
شنبه 01 اسفند 1394, 08:10 صبح
سلام دوستان کسی هست بدونه با c# چطوری میشه برنامه ای برای شبکه های مرتب ساز نوشت؟؟؟؟

khokhan
یک شنبه 02 اسفند 1394, 09:38 صبح
سلام دوستان کسی هست بدونه با C#‎‎‎ چطوری میشه برنامه ای برای شبکه های مرتب ساز نوشت؟؟؟؟
مرتب سازی شبکه سیمی چندین حالت داره .......
منظور شما کدومه ؟؟؟؟!! صدفی ؟؟ بایتونیک ؟؟؟ درجی ؟؟؟ حبابی ؟؟ کدومش؟

انتخابی :


private void selection_sort(int[] arr, int n)
{

int i;
int j;
int max;
int temp;
for (i = n - 1 ; i > 0 ; i--)
{
max = 0;
for (j = 1 ; j <= i ; j++)
if (arr[max] < arr[j])
max = j;
temp = arr[i];
arr[i] = arr[max];
arr[max] = temp;
}
}

مرتب سازی هرمی :


using namespace std;

//
void max_heapify(int*arr,int n,int i)
{
int left_child = 2 * i + 1;
int right_child = 2 * i + 2;
int large = i;

if (left_child < n && arr[large] < arr[left_child])
{
large = left_child;
}
if (right_child < n && arr[large] < arr[right_child])
{
large = right_child;
}
if (large != i)
{
int temp;
temp = arr[i];
arr[i] = arr[large];
arr[large] = temp;
max_heapify(arr, n, large);
}
}

//
void make_max_heap(int* arr, int n)
{
for (int i = n / 2 + 1; i >= 0; i--)
{
max_heapify(arr, n, i);
}
}
//Heap Sort
void heap_sort(int* arr, int n)
{
make_max_heap(arr, n);

int temp;
for (int i = n-1 ; i > 0; i--)
{
temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
max_heapify(arr, i, 0);
}
}

int main( )
{
int *a = new int[6];
a[0] = 8;
a[1] = 7;
a[2] = 9;
a[3] = 2;
a[4] = 5;
a[5] = -1;

heap_sort(a, 6);

for (int i = 0; i < 6; i++)
{
cout << a[i] << " ,";
}
cout << endl;


return 0;
}



مرتب سازی bitonicen لینک http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/bitonic/bitonicen.htm

Coloner
یک شنبه 02 اسفند 1394, 12:10 عصر
این توضیحاتشه.......


شبکهي مرتبسازي یک مدل انتزاعی ریاضی شامل شبکهاي از سیمها و واحدهاي مقایسهکننده است که براي
مرتبسازي دنبالهاي از اعداد از آن استفاده میشود. هرمقایسهکننده دوسیم را به هم متصل میکند و مقادیر را با
قراردادن مقدار کوچکتر روي یکی از سیمها و مقدار بزرگتر روي سیم دیگر، مرتب میکند. هر سیم داراي یک مقدار
میباشد، و هر مقایسه کننده دوسیم را به عنوان ورودي و خروجی میگیرد. زمانی که دو مقدار وارد مقایسه کننده
میشود، مقایسهکننده مقدار کوچکتر را در سیم بالاتر، ومقدار بزرگتر را در سیم پایین قرار میدهد. به شبکهاي از سیمها
و مقایسهکننده ها که به طور صحیح تمام مقادیر ورودي را به صورت صعودي مرتب کنند یک شبکه مرتبسازي گفته
میشود. شکل زیر، نشان دهندهي یک شبکهي مرتبسازي است. سیمها در این شکل به صورت افقی و مقایسه کننده ها
به صورت عمودي نشان داده شدهاند. مراحل انجام مرتبسازي توسط این شبکه درشکل راست نشان داده شده است. فهم
چگونگی صحیح عملکرد اینشبکه مرتبسازي آسان است. این را مدنظر داشته باشید که مقایسهکنندهها مقدار بزرگ را
به سیم پایین و مقدار کوچک را به سیم بالا منتقل میکنند.

هدف از این تمرین این است که عملکرد یک شبکه را روي یک دنبالهي ورودي شبیهسازي کنیم. در ورودي، شبکه و
دنبالهي اعداد داده میشوند. خروجی برنامه تعیین میکند که آیا شبکهي داده شده اعداد را بهدرستی مرتب میکند یا
نه. توضیح اینکه لزوماً هر شبکه، به طور صحیح اعداد را مرتب نمیکند. مثال هایی از حالتهاي درست و نادرست در
نمونههاي زیر ذکر میشوند. علاوه بر این، ممکن است در توصیف شبکهي ورودي خطاهایی وجود داشته باشد که
برنامهي شما باید آنها را تشخیص دهد. براي توصیف یک شبکهي ورودي، از ماتریسی از کاراکترها استفاده میکنیم. به
عنوان مثال شبکهي نشان داده شده در شکل فوق توسط ماتریس زیر توصیف میشود.

هر سطر از ماتریس یک سیم را مشخص میکند. هر کاراکتر از یک سطر یا '-' است که نشان دهندهي عدم وجود
مقایسهکننده درآن بخش است یا با یک حرف لاتین مشخص میشود که در این صورت، باید در یکی (و تنها یکی) دیگر
از کاراکتر هاي آن ستون، کاراکتر مشابه اي پیدا شود. به این ترتیب، فرض میشود یک واحد مقایسهکننده بین سیمهاي
متناظر آن دو سطر وجود دارد. به عنوان مثال، در توصیف فوق یک مقایسهکننده بین دو سیم اول و سوم وجود دارد که
مشخص شده. ستون دوم نیز وجود یک مقایسهکننده بین سیم هاي دوم و چهارم است. ترتیب انتقال اعداد از a با حرف
چپ به راست فرض میشود. در توصیف داده شده از شبکه ممکن است خطاهایی به شرح زیر وجود داشته باشد که
برنامهي شما باید آنها را تشخیصدهد:
در یک ستون تنها یک مورد از یک حرف پیدا میشود یا این که بیش از دو مورد از آنحرف وجود دارد. ·
در توصیف شبکه، کاراکتري غیر از حروف کوچک لاتین و ‘-‘ وجود دارد. ·
دقت کنید که دو مقایسهکننده در دو ستون مختلف میتوانند با یک حرف یکسان نمایش داده شوند، چون این امر
ابهامی در عملکرد شبکه ایجاد نمیکند.

ورودي
است که به ترتیب تعداد سطرها و تعداد K و خط دوم حاوي عدد صحیح N خط اول هر مورد آزمون حاوي عدد صحیح
کاراکتر تشکیل K خط پشت سر هم می آیند که هر یک از N ، ستون هاي ماتریس شبکه را مشخص میکنند. بعد از آن
N عدد صحیح که به ترتیب روي سیمهاي 1 تا N ، شدهاند و محتواي کاراکترهاي ماتریس را مشخص میکنند. سپس
قرار خواهند گرفت وارد می شوند. در ورودي مسئله ممکن است تعداد بیش از یک مورد آزمون ذکر شود که هر یک از
با عدد صفر مقدار دهی شوند، برنامه خاتمه می پذیرد. K و N قالب فوق پیروي میکنند. درصورتی که متغیرهاي
خروجی
آمده، یکی از سه « نمونه خروجی » براي هر مورد آزمون، یک خط در خروجی بنویسید که با قالبی مانند آنچه در بخش
به این معنی که اعداد ورودي پس از پردازش توسط شبکه مرتب Not Sorted ؛ نتیجهي ممکن را مشخص کند
به Invalid network به این معنی که اعداد ورودي پس از پردازش توسط شبکه مرتب میشوند و Sorted . نمیشوند
این معنی که ورودي داده شده قوانین مطرح شده در توصیف مسئله را نقض میکند.