آموزش توربو سی بخش سیزدهم

آموزش توربو سی بخش سیزدهم

توسط amin8505 | گروه مقاله های آموزشی | 1394/07/06

نظرات 0

روشهاي مرتب سازي  (Sorting)

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

روش مرتب‌سازي حبابي  (Bubble  Sort)
      اين روش از نظر منطق ، ساده‌ترين و از نظر كارآيي پايين ترين روش مرتب‌سازي اطلاعات بشمار مي رود . در اين روش ابتدا عنصر اول با عنصر دوم مقايسه مي‌شود . اگر عنصر اول بزرگتر از دومي باشد ، جاي آن دو تعويض مي‌شود . سپس اين عمل در مورد عنصر دوم با سوم و همينطور براي بقيه عناصر به‌صورت متوالي انجام مي‌گيرد . يعني در پايان ، با عنصر n-1 اُم مقايسه مي‌شود كه اگر بزرگتر از آن بود ، جايشان تعويض مي‌شود . وقتي كه اين عمل يك بار كامل شده ، بزرگترين عنصر آرايه ، به آخر آرايه منتقل مي‌شود . حال اگر خانة آخر را ناديده بگيريم و اين عمل را دوباره براي خانه‌ها يا عناصر 1 تا n-1 تكرار كنيم ، اين بار بزرگترين عنصر خانه‌ها 1 تا n-1 (كه دومين عنصر بزرگ آرايه خواهد بود) به خانه n-1 آرايه منتقل مي‌شود . اگر اين عمل را بصورت تكراري براي n-1 بار انجام دهيم و براي سرعت عمل بيشتر ، در هر بار تكرار نيز خانه آخر محدوده جاري آرايه را ناديده بگيريم ، يعني هر بار از طول ناحيه مورد مقايسه يك واحد كاسته شود ، در پايان ، عناصر آرايه بصورت صعودي مرتب مي‌گردد . اگر بخواهيم كه عناصر آرايه مورد نظر به‌صورت نزولي مرتب شود ، بايد در مقايسه دو عنصر متوالي ai با ai+1  ، چنانچه ai كوچكتر از ai+1 باشد ، جاي آن دو با يكديگر تعويض شود .
    از آنجايي كه در اين روش مرتب ‌سازي در هر بار تكرار ، بزرگترين عنصر آرايه به سمت بالا يا انتهاي آرايه حركت مي‌كند (مانند حبابهاي هوا كه در آب جوش موجود است) ، آن را مرتب ‌سازي حبابي نامند .

مثال -  تابع زير آرايه n عنصري A را به روش حبابي ، مرتب مي نمايد .
void  BubbleSort (int A[ ] , int  n)
{
int  i , j , temp ;
for ( i =1 ; i<n ; + +i )
for ( j =0 ; j<n-i ; + +j )
 if ( A[ j] > A[ j+1] )
   {
       temp = A [ j] ;
    A[ j] = A[ j+1] ;
    A[ j+1] = temp ;
    }
 }
 
روش مرتب ‌سازي انتخابي  (Selection Sort)
      در اين روش مرتب سازي ، شيوه كار بدين صورت است كه محل بزرگترين عنصر را در درون آرايه n عنصري مورد نظر پيدا مي‌كنيم و جاي آن را با عنصر آخر يعني an عوض مي‌كنيم ؛ سپس بين عناصر a1 تا an-1 محل بزرگترين عنصر را (كه درواقع دومين بزرگترين عنصر آرايه اصلي خواهد بود) به‌دست مي‌آوريم و جاي آن را با عنصر an-1 عوض مي‌كنيم . اين كار را n-1 بار تكرار مي‌كنيم . در اينصورت در تكرار آخر فقط دو عنصر a1 و a2 را خواهيم داشت كه بايد بزرگترين آن دو در خانه a2 قرار گيرد .
     برتري اين روش نسبت به روش مرتب سازي حبابي آن است كه تعداد تعويض عناصر كمتر مي‌شود . زيرا در اين روش ، در هر تكرار حداكثر يكبار جابجايي انجام مي‌گيرد .

مثال - تابع زير آرايه n عنصريA  را به روش انتخابي مرتب مي نمايد .
void  SelectionSort (int a[ ] , int  n)
{
int  i , max , temp ;
for (i = 1 ; i<n ; + + i )
     {
        max = 0 ;
        for ( j =1 ; j<= n-i+1 ; + + j )
        if (A[ j] > A[max] ) 
            max = j ;
           if ( max != n-i ) 
             {
             temp = A[max] ;
             A[max] = A[n-i] ;
            A[n-i] = temp ;
          }
  }
 }

روشهاي جستجو  (Searching)
     يکي ديگراز کاربردهاي متداول آرايه ها ، استفاده از آنها در روشهاي جسجو است . 
هر گاه در داخل مجموعه‌اي از عناصر ، دنبال عنصر خاصي بگرديم ، اين عمل را جستجو كردن يا searching نامند . جستجو ، در اغلب زمينه‌ها ، به‌ويژه در مورد بانکهاي اطلاعاتي و سيستمهاي تجاري ، كاربرد زيادي دارند .
      شيوه هاي متعددي براي جستجو وجود دارد كه دو روش  متداول آن ، در ادامه بررسي مي‌گردد .

جستجو به روش خطي  (Linear Search)
      اين روش ساده‌ترين راه براي جستجو در يك آرايه يا جدول نامرتب است . براي اينکار عنصر مورد جستجو را بطور متوالي با عناصر اول تا  nاُم آن جدول مقايسه مي كنيم . چنانچه در حين مقايسه ، عنصر مزبور پيدا شد ، شمارة آن يادداشت شده و عمل جستجو خاتمه مي‌ يابد . در غير اين صورت پيغام مناسب صادر مي شود . در اين روش رابطه بين تعداد عناصر جدول و تعداد مقايسه ها ، بصورت يك معادله درجه اول خواهد بود . 

مثال - تابع زير عنصر x را در آرايه n عنصري A به روش جستجوي خطي جستجو ميكند. اگر پيدا شد ، انديس آن ، و در غير اينصورت مقدار صفر را برميگرداند .
int  LinearSearch (int A[ ] , int  n , int  x)
   {
      int  i ;
      for ( i = 0 ; i < n ; + + i )
          if (x = = A[i] )
             return (i +1) ;
      return (0) ;
   }

جستجو به روش دودويي  (Binary Search)
     روش ديگر براي جستجوي عنصري در داخل يك جدول يا آرايه ، روش دودويي است . اين روش ، درصورتي امكان‌پذير است كه عناصر جدول مورد نظر ، مرتب شده باشد . همچنين در مقايسه با روش قبلي ، از سرعت بيشتري برخوردار است .
در اين روش ، عنصر اول و عنصر آخر جدول را با دو متغير مانند L و H نمايش مي‌دهيم و سپس عنصر مورد جستجو را با عنصر وسطي جدول يا :
m = ( L + H ) / 2
مقايسه مي‌كنيم . اگر مساوي بود عنصر مورد جستجو پيدا شده است . در غير اينصورت چنانچه عنصر مورد جستجو از عنصر وسطي بزرگتر باشد ، L را مساوي m+l وگرنه H را مساوي m-1 قرار مي‌دهيم ؛ سپس اين عمليات را باز هم تكرار مي‌كنيم ؛ يعني باز هم عنصر وسطي جدول حاصل را به‌دست مي‌آوريم و عنصر مورد جستجو را با مقدار آن مقايسه مي‌كنيم . اين عمل تا موقعي كه شرط :
L ≤ H
برقرار نباشد ، عمل جستجو خاتمه مي‌يابد و پيغامي مبني بر عدم وجود عنصر مورد جستجو در داخل جدول مورد نظر چاپ مي‌گردد .

مثال -  مراحل الگوريتم جستجو به روش دودويي براي ده عدد زير، در جدول نمايش داده شده  است :
65 , 141 , 192 , 205 , 218 , 389 , 424 , 500 , 538 , 567

جستجوي عدد 567

جستجوي عدد 205

m

h

l

X

m

h

l

X

5

10

1

218

5

10

1

218

8

10

6

500

2

4

1

141

9

10

9

538

3

4

3

192

10

10

10

567

4

4

4

205

 
مثال - تابع زير در يک آرايه مرتب شده n عنصري  ، به روش دودويي عنصر x را جستجو ميكند. اگر پيدا شد  انديس آن ، و در غير اينصورت مقدار صفر را برميگرداند .
int  BinarySearch (int  A[ ] , int  n , int  x)
    {
int   middle , L , H  ;
L = 0 ;
H = n-1 ;
while ( L <= H)
    {
       middle = (L+H)/2 ;
       if ( x = = A[middle] )
  return (middle +1) ;
       if ( x >A[middle] )
  L = middle +1 ;
       else
   H = middle -1 ;
          }
return (0) ;
}

توابع كتابخانه‌اي (در مورد رشته‌ها)
      اغلب نسخه های زبان C ، مجموعة وسيعي از توابع كتابخانه‌اي در مورد عمليات روي رشته‌ها را پشتيباني مي‌كنند كه در مبحث توابع كتابخانه‌اي مورد بحث قرار خواهند گرفت . در اينجا چند تابع بسيار متداول كه در نوشتن برنامه‌ها كاربرد زيادي دارند ، به شرح زير بيان مي‌گردد:

عمل تابع

نام تابع

رشته s2 را روي رشته s1 كپي مي‌كند .

strcpy (s1 , s2)

رشته s2 را به دنبال رشته s1 ملحق (ضميمه) مي‌كند.

strcat (s1 , s2)

طول رشته s را برمي‌گرداند .

strlen (s)

رشته s1 را با رشته s2 مقايسه مي‌كند .                

strcmp (s1, s2)

 
اگر بخواهيم درمورد مقايسه دو رشته ، تمايز بين حروف بزرگ و كوچك ناديده گرفته شود ، تابع strcmp بصورت strcmpi  بكار برده مي‌شود .
در ضمن يادآور مي‌شويم كه توابع كتابخانه‌اي مربوط به رشته‌ها در فايل string.h قرار دارند. پس اگر بخواهيم در برنامه‌اي از اين تابع استفاده كنيم ، بايد دستور :
# include<string.h>
را نيز قبل از تابع main   بكار بريم .
      حال به چند مثال در مورد رشته‌ها توجه نماييد .

مثال -  برنامه زير نحوه استفاده و كاربرد چند تابع كتابخانه‌اي را نشان مي‌دهد :
# include<string.h>
# include<stdio.h>
main ( )
   {
   char s1 [80] , s2 [80] , s3 [80] ;
   gets (s1) ;
   gets (s2) ;
   printf ("\n Lengths : %d %d\n" , strlen (s1) , strlen (s2)) ;
   if  (!strcmp (s1 , s2)) 
       printf ("\n The strings are equal\n") ;
   strcpy (s1 , s3) ;
   strcat (s1 , s2) ;
   printf ("\n %s" , s3) ;
   printf ("\n %s" , s1) ;
}

اگر اين برنامه اجرا كنيم و براي دو رشته s1 و s2 كلمه "computer science" را وارد گردد، خروجي برنامه مزبور بصورت زير خواهد بود :
Lengths : 16 16
The strings are equal
computer science
computer sciencecomputer science

مثال -  برنامه‌اي بنويسيد كه اسامي n نفر دانشجو را بخواند ، سپس آنها را به ترتيب الفبا مرتب و چاپ كند . n ، حداكثر 15 مي‌باشد كه با اولين دستور ورودي خوانده مي‌شود .
حل : برنامه مورد نظر در زير نشان داده شده است :
# include<stdio.h>
# include<string.h>
main ( )
    {
int  i , n , j ;
char  name [15][12] , temp [12] ;
scanf ("%d" , &n) ;
for ( i=0 ; a<n ; ++i )
   scanf ("%s" , &name[i] ) ;
         for ( i=1 ; i<n ; ++i )
    for ( j=0 ; j<n-i ; ++j )
        if (strcmp (name[j] , name [j+1]) > 0 )
           {
             strcpy (temp , name [j] ) ;
             strcpy (name[j] , name [j+1] ) ;
             strcpy (name[j+1] , temp) ;
           }
        for ( i=0 ; i<n ; ++i )
    printf ("\n %s" , name[i] ) ;
    }
 

 

0 نظر

نظر محترم شما در مورد مقاله های وب سایت برنامه نویسی و پایگاه داده

نظرات محترم شما در خدمات رسانی بهتر ما را یاری می نمایند. لطفا اگر مایل بودید یک نظر ما را مهمان فرمائید. آدرس ایمیل و وب سایت شما نمایش داده نخواهد شد.

حرف 500 حداکثر