مرتب سازی یک سری عدد

[میلاد قاضی پور]

سلام . من قصد دارم برنامه ای بنویسم که یه سری عدد رو به صورت صعودی یا نزولی مرتب کنه . در مورد الگوریتمش یه ذره ضعف دارم . دوست ندارم کسی الگوریتمشو کامل بنویسه اینجا ولی کمی راهنمایی نیاز دارم تا مراحل کار رو درک کنم . تعداد اعداد بر فرض 10 تا باشه

[Pooria121]

این مدل از الگوریتم ها، به نام Sorting Algorithm معروف هستند. تعدادی زیادی از اینها وجود داره، و نسبت به تعداد لیست که میخواهید مرتب بشود بستگی دارد. به عنوان مثال 10 تا عدد به هیچ عنوان زیاد نیست که مهم باشه با چه الگلوریتمی انجام بشه، ولی به عنوان مثال 100 تا عدد یا 1000 تا یا ..... زمان زیادی میگیرد اگر درست انتخاب نکنید.
اگر سریع، ساده و کلی بخواهم بگم (ولی شما خودتون باید مطالعه کنید، چون یک مبحص خیلی گسترده ای است)، این مدل الگوریتم ها به تعداد حرکت هاییی که انجام میدهند، تا یک لیست n تایی رو sort کنند، دسته بندی میشوند، به عنوان مثال، یک مدل از sort ها ؛ selection sort است، که به عنوان مثال در بدترین حالت، برای مرتب کردن یک لیست n تایی، n^2 حرکت انجام میدهد (البته، گفتن "حرکت" غلط است، ولی برای سادگی و فهم مطلب عرض میکنم) ، همانطوری که میبنی، زمانی که تعداد عداد شما در یک لیست زیاد میشه، تعداد حرکت ها، بصورت توانی (Exponentially) زیاد میشه، ولی برای یک لیست کوچک خیلی مناسبه. تعداد زیادی از اینها هستند، ولی به نظر من راحترین برای شروع، selection sort است و شمارو آماده برای یادگیری مباحث Algorithm میکنه، برای چگونگی کار این به لینک زیر مراجعه کنید.
http://en.wikipedia.org/wiki/Selection_sort

[میلاد قاضی پور]

با تشکر از شما باید بگم مباحث مطرح شده در اون صفحه ویکی پدیا بسیار بسیط و کشـــــ دار بودن . من فقط یه راهنمایی کوچیک نیاز دارم تا یه جرقه ای به این مخ ناکار ما بخوره .

[Pooria121]

من Selection sort رو بصورت اجمالی اینجا توضیح میدم تا مغر شما اون جرقه رو بگیره...
شما فرظ کنید که یک لیست عدد داریند...

5 - 4 - 7 - 1 - 23 - 6


ما در یک حلقه، اولین عدد لیست که 5 باشه رو انتخاب میکنیم، و میریم کوچیکترین عدد داخل لیست که از 5 هم کوچکتر هستند و در سمت راست عدد ما قرار دارند رو پیدا میکنیم، که در این جا، 1 است !، جای 1 و 5 رو باهم عوض میکنم ..

1 - 4 - 7 - 5 - 23 - 6

خوب، حالا میریم دویم عدد تو لیست، که 4 هست، سمت راست 4، هیچ عددی قرار ندارد که از 4 کوچک باشه،
پس عدد بعدی، 7 است. 5 کوچکترین عددی است که در سمت راست 7 قرار دارد، پس جایش را با 7 عوض میکنیم.
LTR]
1 - 4 - 5- 7- 23 - 6
[/LTR]
خوب دوباره عدد، بعد در لیست ما، 7 است، کمتیرین، عدد در سمت راست، 6 است و جای اونرو با 7 عوض میکنیم...
LTR]
1 - 4 - 5- 6- 23 - 7
[/LTR]
حالا عدد بعدی 23 است، که جای اون رو با 7 عوض میکنیم. و به انتها لیست رسیدیم.
ولی دوباره باید لیست رو چک کنیم، تا ببنیم sort است یا نه، اگر نبود دوباره جا به جایی رو انجام بدیم!!!! کافی بود یک کامل تر بگم؟

[میلاد قاضی پور]

راستش شما سوأل منو یه جور دیگه توضیح دادید .مفهوم سورت کردن رو بلدم. من میخوام بدونم این کارایی که گقتید چطور انجام میشه ؟ چه شروطی لازم هست ؟ از چه حلقه ای باید استفاده بشه ؟ چند تا متغیر لازم داریم ؟... این مخ ما رعد و برق هم کمشه ...:لبخند:

[میلاد قاضی پور]

ببینید من میتونم کوچکترین عدد رو پیدا کنم ولی وقتی پیدا کردم ، نیاز دارم که اون عدد رو از دور خارج کنم و مقایسه رو با بقیه اعداد ادامه بدم .

1-عدد اول را در min بگذار
2-عدد بعدی رو در b
3-اگر b<min بود , b رو در min بذار در غیر اینصورت برو به 5
4-برگرد به 2
5-min رو چاپ کن و حذف کن
6-اگر تعداد اعداد بیش از یکی بود برگرد به 1
-پایان

[Pooria121]

ببین، چندین مدل الگوریتم هست برای sort که زمین تا آسمون باهم فرق دارند ! من کل کدش رو به صورت C++‎‎ مینوسیم دیگه انشالله مشکلی پیشنیاد...




#include <iostream>
using namespace std;
int main(){
// 6 ta adad!!! be hamin tartibi ke hastan!
int list[] = {5,4,1,3,2,0};


//sort

for(int i = 0; i < 6-1; i++){
int temp = i;
for(int j = i+1; j < 6; j++){
if(list[temp] > list[j]){
temp = j;
sorted = false;
}
}
//swap the two
int mytemp = list[i];
list[i] = list[temp];
list[temp] = mytemp;
}


//print array
for(int i = 0; i < 6;i++){
cout << list[i] << endl;
}
return 0;
}

[qwerty11]

ببین دوست عزیز، جواب خیلی ساده تر از اون چیزیه که شما فکر میکنی ! :

برای ایندکس های 1 تا n مینیمم را پیدا کن و با خانه ی اول آن را تعویض کن.
برای ایندکس های 2 تا n مینیمم را پیدا کن و با خانه ی دوم آن را تعویض کن.
برای ایندکس های 3 تا n مینیمم را پیدا کن و با خانه ی سوم آن را تعویض کن.
.
.
.
اوکی !؟

[mohsensaghafi]

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

[میلاد قاضی پور]

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

[Pooria121]

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

شما برای ذخیره ی Data باید از یک Data-structure استفاده کنید، حالا اون میتواند Array باشد یا Linked-list و یا ...
همانطوری که گفتم چندین مدل برای sort داریم، که بعضی از آنها از Tree برای ساختار استفاده میکنند.

مهمترین قسمت این است که، عملیات sort(مثلا در مثال ما، selection sort) ، یک Algorithm بیشتر نیست، که شما میتوانید آنرا یا به کمک Array یا ArrayList یا LinkedList یا Skiplist و ... اجرا کنید، تنها تغییر در کد، قسمت هایی است که شما به اطلاعات میخواهید دسترسی پیدا کنید، به عنوان مثال اگر در Array شما با مشخص کردن index در [] این کار رو میکنید، در linked-list شما باید بصورت، حلقه روی لیست iterate کنید تا به element مورد نظر برسید.

بنده مثال selection sort رو در قسمت معماهای C/C++ در صفحه 11 با linked-list نوشته ام که میتواند مثال خوبی برای شما باشد.

ولی به نظرمن، Array ساده ترین چیزی است که یک تازه کار (شاید دانشجوهای شما) میتوانند متوجه شوند.

[exe123]

با سلام خدمت شما

بی مقدمه میرم سر اصل مطلب ،نگاه شما اگه بتوانید 2 یا چهار عدد را بدون تابع مرتب کنید در واقع جای انها را بایکدیگر عوض نمایید مرتب سازی را به طور کامل فرا میگیرید در واقع در ارایه ها نیز هیمین جابجایی صورت میگیرید با این تغییر که ما اندیس های ارایه را جابجا میکنیم ان هم با حلقه for ، که دیگر لازم نیست به تک تک عضو های ارایه رابا یکدیگر مقایسه کنیم ، اما اگر به طور دستی(یعنی بدون ارایه) این کار را انجام دادیم باید تک تک عضو های ان را با یکدیگر مقایسه کنیم .
اگر نتوانستی کدش را پیدا کنی یا با ایمیلم یا در این تاپیک بگو تا حتما برایت بگویم

[hadi-me251]

هر چند خیلی از زمان سوال گذشته ولی مرتب سازی بدون نیاز به دونستن تعداد کاراکتر های ورودی ،بدون استفاده از آرایه و در حد مبتدی در C++‎:
(در ضمن با تشکر از دکتر بازرگان)



{
int counter;
int input;//adad-e vorodi
int input_copy;// copy adad-e vorodi
int yekan;//zakhire taghirat
int out;

cout << "adad????????"<<endl;
cin >> input;
for (counter = 9; counter >= 0; counter--)
{
input_copy = input;
while (input_copy > 0)
{
yekan = input_copy % 10;
input_copy /= 10;
if (yekan == counter)
{
cout << yekan;
}
else if (counter == 0 && yekan == 0)
{ cout << 0; break; }
}
}
cout << endl;
}

[Shaaaaar]

[QUOTE=میلاد قاضی پور;966535]سلام . من قصد دارم برنامه ای بنویسم که یه سری عدد رو به صورت صعودی یا نزولی مرتب کنه . در مورد الگوریتمش یه ذره ضعف دارم . دوست ندارم کسی الگوریتمشو کامل بنویسه اینجا ولی کمی راهنمایی نیاز دارم تا مراحل کار رو درک کنم . تعداد اعداد بر فرض 10 تا باشه[/QUOTE