موضوعات وبسایت : برنامه نویسی
سوالات امتحان آیین نامه رانندگی

مرتب سازی حبابی در c++

مرتب سازی حبابی در c++

نویسنده : محمد پارسایی | زمان انتشار : 10 اسفند 1399 ساعت 22:12

جهت انجام پروژه های دانشجویی و یا تمرین‌های برنامه نویسی رشته کامپیوتر میتوانید به آی دی تلگرام زیر پیام دهید

@AlirezaSepand



در این پست یک مطلب با عنوان مرتب سازی حبابی در c++ را مطالعه خواهید کرد.

«مرتب‌سازی حبابی» (Bubble Sort)، یکی از انواع الگوریتم‌های مرتب‌سازی محسوب می‌شود. این الگوریتم مرتب‌سازی از جمله الگوریتم‌های مبتنی بر مقایسه است که در آن، جفت عنصرهای هم‌جوار با یکدیگر مقایسه شده و در صورتی که دارای ترتیب صحیحی نباشند، با یکدیگر جا به جا می‌شوند. الگوریتم مرتب سازی حبابی برای مجموعه داده‌های بزرگ مناسب نیست، زیرا پیچیدگی زمانی آن در حالت میانگین و بدترین حالت برابر با (Ο(n2 است، که در آن n تعداد کل عناصر مجموعه داده محسوب می‌شود. در این مطلب، ابتدا یک مثال از الگوریتم مرتب‌سازی حبابی ارائه و سپس، «روندنما» (Flow Chart)، شبه کد و پیاده‌سازی آن در زبان‌های «پایتون» (Python)، «جاوا» (Java)، «سی» (C) و «سی‌پلاس‌پلاس» (++C)، «پی‌اچ‌پی» (PHP) و «سی‌شارپ» (#C) ارائه شده است. شایان توجه است که الگوریتم‌های مرتب‌سازی از جمله مباحث بسیار مهم در «ساختمان داده» (Data Structure) هستند.

سوالات امتحان آیین نامه رانندگی

الگوریتم مرتب سازی حبابی چطور کار می‌کند؟

برای تشریح چگونگی عملکرد الگوریتم مرتب سازی حبابی، از یک مثال استفاده شده است. در این مثال، یک آرایه غیر مرتب در نظر گرفته شده است. با توجه به اینکه الگوریتم مرتب سازی حبابی از مرتبه (Ο(n2 است، آرایه انتخاب شده کوچک در نظر گرفته می‌شود. آرایه در نظر گرفته شده: ( ۴ ۲ ۸ ۱ ۵ ) است. مرتب‌سازی حبابی برای این آرایه، به صورت زیر انجام می‌شود.

۱. ابتدا، دو عنصر اول آرایه با یکدیگر مقایسه می‌شوند و با توجه به آنکه ۵ از ۱ بزرگتر است (۱<۵)، این دو عنصر با یکدیگر جا به جا می‌شوند.

5 1 4 2 8 ) –> ( 1 5 4 2 8 )

۲. در اینجا، عناصر دوم و سوم آرایه مقایسه می‌شوند و با توجه به اینکه ۵ از ۴ بزرگ‌تر است (۴<۵)، این دو عنصر با یکدیگر جا به جا می‌شوند.

( 1 5 4 2 8 ) –> ( 1 4 5 2 8 )

۳. اکنون، عنصر سوم و چهارم آرایه مقایسه می‌شوند و با توجه به اینکه ۲ از ۵ کوچک‌تر است (۲<۵)، این دو عنصر با یکدیگر جا به جا می‌شوند.

( 1 4 5 2 8 ) –>  ( 1 4 2 5 8 )

۴. در اینجا، عنصر چهارم و پنجم آرایه مقایسه می‌شود و چون ۵ از ۸ کوچک‌تر است (۵<۸) دو عنصر در جای خود بدون هر گونه جا به جایی باقی می‌مانند؛ چون در واقع، ترتیب (صعودی) در آن‌ها رعایت شده است.

( 1 4 2 5 8 ) –> ( 1 4 2 5 8 )

اکنون یک دور کامل در آرایه زده شد. دومین دور نیز به شیوه بیان شده در بالا انجام می‌شود.

۱. جا به جایی اتفاق نمی‌افتد.

1 4 2 5 8 ) –> ( 1 4 2 5 8 )

۲. با توجه به بزرگ‌تر بودن ۴ از ۲ (۲<۴)، این دو عنصر با یکدیگر جا به جا می‌شوند.

( 1 4 2 5 8 ) –> ( 1 2 4 5 8 )

۳. جا به جایی اتفاق نمی‌افتد.

( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )

۴. جا به جایی اتفاق نمی‌افتد.

( 1 2 4 5 8 ) –>  ( 1 2 4 5 8 )

در حال حاضر، آرایه مرتب شده است، اما الگوریتم نمی‌داند که آیا کار به پایان رسیده یا خیر؛ بنابراین، به یک دور کامل دیگر بدون انجام هرگونه جا به جایی نیاز دارد تا بفهمد که مرتب‌سازی با موفقیت به پایان رسیده است.

1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )

فلوچارت الگوریتم مرتب‌سازی حبابی

شبه کد الگوریتم مرتب سازی حبابی

Bubble Sort(a[],n)

Fori=0ton-1

Swap=false

Forj=i+1ton

ifa[j-1]>a[j]

Swap(a[j-1],a[j])

Swap=true

Breakifnotswapped

در ادامه، پیاده‌سازی الگوریتم مرتب سازی حبابی در زبان‌های برنامه‌نویسی گوناگون انجام شده و آرایه {۹۰ ,۱۱ ,۲۲ ,12 ,۲۵ ,۳۴ ,۶۴} به عنوان ورودی به قطعه کدها داده شده است. بنابراین، خروجی نهایی همه قطعه کدها، به صورت زیر خواهد بود.

پیاده‌سازی الگوریتم مرتب سازی حبابی در پایتون

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

# Python program for implementation of Bubble Sort

defbubbleSort(arr):

    n=len(arr)

    # Traverse through all array elements

    foriinrange(n):

        # Last i elements are already in place

        forjinrange(0,n-i-1):

            # traverse the array from 0 to n-i-1

            # Swap if the element found is greater

            # than the next element

            ifarr[j]>arr[j+1]:

                arr[j],arr[j+1]=arr[j+1],arr[j]

# Driver code to test above

arr=[64,34,25,12,22,11,90]

bubbleSort(arr)

print("Sorted array is:")

foriinrange(len(arr)):

    print("%d"%arr[i]),

پیاده‌سازی الگوریتم مرتب سازی حبابی در جاوا

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

// Java program for implementation of Bubble Sort

classBubbleSort

{

    voidbubbleSort(intarr[])

    {

        intn=arr.length;

        for(inti=0;i<n-1;i++)

            for(intj=0;j<n-i-1;j++)

                if(arr[j]>arr[j+1])

                {

                    // swap arr[j+1] and arr[i]

                    inttemp=arr[j];

                    arr[j]=arr[j+1];

                    arr[j+1]=temp;

                }

    }

    /* Prints the array */

    voidprintArray(intarr[])

    {

        intn=arr.length;

        for(inti=0;i<n;++i)

            System.out.print(arr[i]+" ");

        System.out.println();

    }

    // Driver method to test above

    publicstaticvoidmain(Stringargs[])

    {

        BubbleSort ob=newBubbleSort();

        intarr[]={64,34,25,12,22,11,90};

        ob.bubbleSort(arr);

        System.out.println("Sorted array");

        ob.printArray(arr);

    }

}

/* This code is contributed by Rajat Mishra */

پیاده‌سازی الگوریتم مرتب سازی حبابی در C و ++C

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

// C program for implementation of Bubble sort

#include <stdio.h>

voidswap(int*xp,int*yp)

{

    inttemp=*xp;

    *xp=*yp;

    *yp=temp;

}

// A function to implement bubble sort

voidbubbleSort(intarr[],intn)

{

   inti,j;

   for(i=0;i<n-1;i++)      

       // Last i elements are already in place    

       for(j=0;j<n-i-1;j++)  

           if(arr[j]>arr[j+1])

              swap(&arr[j], &arr[j+1]);

}

/* Function to print an array */

voidprintArray(intarr[],intsize)

{

    inti;

    for(i=0;i<size;i++)

        printf("%d ",arr[i]);

    printf("n");

}

// Driver program to test above functions

intmain()

{

    intarr[]={64,34,25,12,22,11,90};

    intn=sizeof(arr)/sizeof(arr[0]);

    bubbleSort(arr,n);

    printf("Sorted array: \n");

    printArray(arr,n);

    return0;

}

پیاده‌سازی الگوریتم مرتب سازی حبابی در PHP

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

<?php  

// PHP program for implementation  

// of Bubble Sort

functionbubbleSort(&$arr)

{

    $n = sizeof($arr);

    // Traverse through all array elements

    for($i=0;$i<$n;$i++)  

    {

        // Last i elements are already in place

        for($j=0;$j<$n-$i-1;$j++)  

        {

            // traverse the array from 0 to n-i-1

            // Swap if the element found is greater

            // than the next element

            if($arr[$j]>$arr[$j+1])

            {

                $t=$arr[$j];

                $arr[$j]=$arr[$j+1];

                $arr[$j+1]=$t;

            }

        }

    }

}

// Driver code to test above

$arr=array(64,34,25,12,22,11,90);

$len=sizeof($arr);

bubbleSort($arr);

echo"Sorted array : \n";

for($i=0;$i<$len;$i++)

    echo$arr[$i]." ";  

// This code is contributed by ChitraNayal.

?>

پیاده‌سازی الگوریتم مرتب سازی حبابی در سی شارپ

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

// C# program for implementation  

// of Bubble Sort

usingSystem;

classGFG

{  

    staticvoidbubbleSort(int[]arr)

    {

        intn=arr.Length;

        for(inti=0;i<n-1;i++)

            for(intj=0;j<n-i-1;j++)

                if(arr[j]>arr[j+1])

                {

                    // swap temp and arr[i]

                    inttemp=arr[j];

                    arr[j]=arr[j+1];

                    arr[j+1]=temp;

                }

    }

    /* Prints the array */

    staticvoidprintArray(int[]arr)

    {

        intn=arr.Length;

        for(inti=0;i<n;++i)

            Console.Write(arr[i]+" ");

        Console.WriteLine();

    }

    // Driver method

    publicstaticvoidMain()

    {

        int[]arr={64,34,25,12,22,11,90};

        bubbleSort(arr);

        Console.WriteLine("Sorted array");

        printArray(arr);

    }

}

// This code is contributed by Sam007

پیاده سازی بهینه الگوریتم مرتب سازی حبابی

تابع معرفی شده در بالا در حالت متوسط و بدترین حالت، برابر با (O(n*n است. بدترین حالت تنها هنگامی به وقوع می‌پیوندد که آرایه به ترتیب معکوسی مرتب شده باشد. پیچیدگی زمانی تابع مذکور در بهترین حالت برابر با (O(n است و این حالت تنها هنگامی اتفاق می‌افتد که آرایه مرتب شده باشد. تابع بالا را می‌توان به این شکل بهینه کرد که اگر حلقه داخلی منجر به هیچ جا به جایی نشود، فرایند متوقف شود. در ادامه، نمونه کد مربوط به تابع بهینه شده، در زبان‌های برنامه‌نویسی گوناگون از جمله پایتون (نسخه ۳) ارائه شده است.

پیاده‌سازی بهینه الگوریتم مرتب سازی حبابی در پایتون

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

# Python3 Optimized implementation

# of Bubble sort

# An optimized version of Bubble Sort

defbubbleSort(arr):

    n=len(arr)

    # Traverse through all array elements

    foriinrange(n):

        swapped=False

        # Last i elements are already

        #  in place

        forjinrange(0,n-i-1):

            # traverse the array from 0 to

            # n-i-1. Swap if the element  

            # found is greater than the

            # next element

            ifarr[j]>arr[j+1]:

                arr[j],arr[j+1]=arr[j+1],arr[j]

                swapped=True

        # IF no two elements were swapped

        # by inner loop, then break

        ifswapped==False:

            break

# Driver code to test above

arr=[64,34,25,12,22,11,90]

bubbleSort(arr)

print("Sorted array :")

foriinrange(len(arr)):

    print("%d"%arr[i],end=" ")

# This code is contributed by Shreyanshi Arun

پیاده‌سازی بهینه الگوریتم مرتب سازی حبابی در جاوا

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

// Optimized java implementation

// of Bubble sort

importjava.io.*;

classGFG  

{

    // An optimized version of Bubble Sort

    staticvoidbubbleSort(intarr[],intn)

    {

        inti,j,temp;

        booleanswapped;

        for(i=0;i<n-1;i++)  

        {

            swapped=false;

            for(j=0;j<n-i-1;j++)  

            {

                if(arr[j]>arr[j+1])  

                {

                    // swap arr[j] and arr[j+1]

                    temp=arr[j];

                    arr[j]=arr[j+1];

                    arr[j+1]=temp;

                    swapped=true;

                }

            }

            // IF no two elements were  

            // swapped by inner loop, then break

            if(swapped==false)

                break;

        }

    }

    // Function to print an array  

    staticvoidprintArray(intarr[],intsize)

    {

        inti;

        for(i=0;i<size;i++)

            System.out.print(arr[i]+" ");

        System.out.println();

    }

    // Driver program

    publicstaticvoidmain(Stringargs[])

    {

        intarr[]={64,34,25,12,22,11,90};

        intn=arr.length;

        bubbleSort(arr,n);

        System.out.println("Sorted array: ");

        printArray(arr,n);

    }

}

// This code is contributed  

// by Nikita Tiwari.

پیاده‌سازی بهینه الگوریتم مرتب سازی حبابی در ++C

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

//Optimized implementation of Bubble sort

#include <stdio.h>

void swap(int*xp,int*yp)

{

    inttemp=*xp;

    *xp=*yp;

    *yp=temp;

}

//An optimized version of Bubble Sort

void bubbleSort(intarr[],intn)

{

   inti,j;

   boolswapped;

   for(i=0;i<n-1;i++)

   {

     swapped=false;

     for(j=0;j<n-i-1;j++)

     {

        if(arr[j]>arr[j+1])

        {

           swap(&arr[j], &arr[j+1]);

           swapped=true;

        }

     }

     //IFno two elements were swapped by inner loop,then break

     if(swapped==false)

        break;

   }

}

/*Function to printan array*/

void printArray(intarr[],intsize)

{

    inti;

    for(i=0;i<size;i++)

        printf("%d ",arr[i]);

    printf("n");

}

//Driver program to testabove functions

intmain()

{

    intarr[]={64,34,25,12,22,11,90};

    intn=sizeof(arr)/sizeof(arr[0]);

    bubbleSort(arr,n);

    printf("Sorted array: \n");

    printArray(arr,n);

    return0;

}

پیاده‌سازی بهینه الگوریتم مرتب سازی حبابی در PHP

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

<?php  

// PHP Optimized implementation

// of Bubble sort

// An optimized version of Bubble Sort

functionbubbleSort(&$arr)

{

    $n = sizeof($arr);

    // Traverse through all array elements

    for($i=0;$i<$n;$i++)

    {

        $swapped=False;

        // Last i elements are already

        // in place

        for($j=0;$j<$n-$i-1;$j++)

        {

            // traverse the array from 0 to

            // n-i-1. Swap if the element  

            // found is greater than the

            // next element

            if($arr[$j]>$arr[$j+1])

            {

                $t=$arr[$j];

                $arr[$j]=$arr[$j+1];

                $arr[$j+1]=$t;

                $swapped=True;

            }

        }

        // IF no two elements were swapped

        // by inner loop, then break

        if($swapped==False)

            break;

    }

}

// Driver code to test above

$arr=array(64,34,25,12,22,11,90);  

$len=sizeof($arr);

bubbleSort($arr);

echo"Sorted array : \n";

for($i=0;$i<$len;$i++)

    echo$arr[$i]." ";

// This code is contributed by ChitraNayal.

?>

پیاده‌سازی بهینه الگوریتم مرتب سازی حبابی در #C

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

// Optimized C# implementation

// of Bubble sort

usingSystem;

classGFG

{  

    // An optimized version of Bubble Sort

    staticvoidbubbleSort(int[]arr,intn)

    {

        inti,j,temp;

        boolswapped;

        for(i=0;i<n-1;i++)  

        {

            swapped=false;

            for(j=0;j<n-i-1;j++)  

            {

                if(arr[j]>arr[j+1])  

                {

                    // swap arr[j] and arr[j+1]

                    temp=arr[j];

                    arr[j]=arr[j+1];

                    arr[j+1]=temp;

                    swapped=true;

                }

            }

            // IF no two elements were  

            // swapped by inner loop, then break

            if(swapped==false)

                break;

        }

    }

    // Function to print an array  

    staticvoidprintArray(int[]arr,intsize)

    {

        inti;

        for(i=0;i<size;i++)

            Console.Write(arr[i]+" ");

        Console.WriteLine();

    }

    // Driver method  

    publicstaticvoidMain()

    {

        int[]arr={64,34,25,12,22,11,90};

        intn=arr.Length;

        bubbleSort(arr,n);

        Console.WriteLine("Sorted array");

        printArray(arr,n);

    }

}

// This code is contributed by Sam007

جمع‌بندی

الگوریتم مرتب‌سازی حبابی با توجه به سادگی که دارد، معمولا برای معرفی مفهوم مرتب‌سازی مورد استفاده قرار می‌گیرد. در گرافیک کامپیوتری، این الگوریتم مرتب‌سازی با توجه به توانایی که برای تشخیص خطاهای خیلی کوچک (مانند جا به جایی تنها دو عنصر) در آرایه‌های تقریبا مرتب شده و رفع آن با پیچیدگی خطی (2n) دارد، از محبوبیت زیادی برخوردار است. برای مثال، در الگوریتم «پر کردن چند ضلعی» (Polygon Filling Algorithm) که خط‌های محدود کننده به وسیله مختصات x در یک خط اسکن مشخص مرتب‌سازی شده‌اند (خطی موازی محور x) و با افزایش y ترتیب آن‌ها در تقاطع دو خط تغییر می‌کند (دو عنصر جا به جا می‌شوند)، مورد استفاده قرار می‌گیرد.

^^

الهام حصارکی (+)

«الهام حصارکی»، فارغ‌التحصیل مقطع کارشناسی ارشد مهندسی فناوری اطلاعات، گرایش سیستم‌های اطلاعات مدیریت است. او در زمینه هوش مصنوعی و داده‌کاوی، به ویژه تحلیل شبکه‌های اجتماعی، فعالیت می‌کند.

بر اساس رای 18 نفر

آیا این مطلب برای شما مفید بود؟

آیا این مطلب برای شما مفید بود؟


منبع: blog.faradars.org



ارسال نظر

نام


ایمیل


نظر