PDA

View Full Version : مقاله: مرتب سازی بدون استفاده از هیچ کدام از روشهای مرتب سازی



Salar Ashgi
سه شنبه 26 شهریور 1387, 17:41 عصر
سلام به همه عزیزان ، همانطور که میدانید الگوریتم های متعددی برای مرتب سازی وجود

دارد ( Bubble Sort, Selection Sort,Merge Sort, Heap Sort,Quick sort, ... ) که هر کدام

برای خود روش و مرتبه زمانی بخصوصی دارند !!!

Bubble Sort, Selection Sort = http://i38.tinypic.com/23kuhhl.jpg


Merge Sort = http://i37.tinypic.com/333uxpw.jpg

و به همین ترتیب !!!

============================
حالا روشی را معرفی می کنم که البته مثل روشهای مرتب سازی بالا ، کارا نیست ولی خوب

برای کسانی که با این روشها آشنایی چندانی ندارند ، میتواند مفید باشد !!!

================
توضیح روش : ابتدا یک آرایه با سایز بزرگ در نظر می گیریم ، بعد تمام خانه های آنرا صفر

میکنیم ، بعد لیستی که قرار است مرتب شود ، اندیس متناظر با هر عضوش را در آرایه 1

می گذاریم ، حال آرایه را از اول نشان می دهیم ، ولی اندیسهایی که مقدارشان 1 است ،

(اعضای لیست) چون اندیس های آرایه به ترتیب صعودی پیش میروند ، اعضای مرتب شده ما

بدست می آید !!!
===============
کد به زبان سی پلاس پلاس :


#include <iostream>
#include <conio>
int main(){
int a[100];
for(int i=0;i<100;i++)
a[i]=0;
//--------------
int k;//tedad;
cout<<"Enter Tedad : \n";
cin>>k;
int *b=new int[k];
cout<<"Enter Your Numbers :\n";
for(int i=0;i<k;i++)
cin>>b[i];
cout<<"-----------------\n";
for(int i=0;i<k;i++)
a[b[i]]=1;
//------------------------
cout<<"Your Sorted List :\n";
for(int i=0;i<100;i++){
if(a[i]==1)
cout<<i<<" ";
}
cout<<endl;
getch();
}

==============
موفق و پیروز باشید !!!

manager
جمعه 29 شهریور 1387, 00:04 صبح
این الگوریتم برای عناصر تکراری جواب نمی ده و اونا رو حذف می کنه. بهتره از الگوریتم مرتب سازی شمارشی استفاده کنی.

MOHSEN8000
دوشنبه 01 مهر 1387, 10:45 صبح
فکر کنم منظورتون counting sort باشه. این روش بسیار خوبی هست از این لحاظ که دارای O(n) هست ولی مشکل آن این هست که فقط برای داده های صحیح کار می کنه و ضمن این که اگه پراکندگی داده ها خیلی زیاد باشه ، فضای خیلی زیادی رو هدر می ده.

manager
سه شنبه 02 مهر 1387, 11:32 صبح
فکر کنم منظورتون counting sort باشه. این روش بسیار خوبی هست از این لحاظ که دارای O(n) هست ولی مشکل آن این هست که فقط برای داده های صحیح کار می کنه و ضمن این که اگه پراکندگی داده ها خیلی زیاد باشه ، فضای خیلی زیادی رو هدر می ده.
خوب این الگوریتم رو نسبت به الگوریتمی که در بالا بهش اشاره شد معرفی کردم که نمونه کامل شده اون هست. اینگونه الگوریتم ها بیشتر الگوریتم های پایه ای و "ایده زا" هستند نه Applicable.