مرتب سازی سریع یا Quick Sort

برنامه: مرتب سازی یک آرایه با الگوریتم quick Sort 

الگوریتم:

برای این کار از دو تابع استفاده می کنیم

1 - تابع پارتیشن

int Partition(int arr[],int Lobj,int Robj)

* که یک آرایه ( arr[] ) و سمت چپ ترین اندیس آرایه ( Lobj ) و سمت راست ترین اندیس آرایه ( Robj ).

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

\\.......................................................//

2- تابع کویک سورت

void quicksort(int arr[],int Lobj,int Robj)

 

تابع کویک سورت هر بار آرایه را به دو قسمت تقسیم می کند

قسمت اول شامل خانه های سمت چپ ترین خانه (Lobj) تا عنصر محوری  (Pivot)

قسمت دوم شامل خانه های عنصر محوری  (Pivot)  تا سمت راست ترین خانه  (Robj)

 

 برنامه مرتب سازی سریع به زبان++C

  #include
#include

#define size 21
//.................................................................
int Partition(int arr[],int Lobj,int Robj)
{
    int pivot = Lobj;
    int temp;
    while(Lobj < Robj)
    {
        while(arr[Lobj] <= arr[pivot])
        Lobj++;  

        while(arr[Robj] > arr[pivot])
        Robj--;

        if(Lobj < Robj)
       {
           temp = arr[Lobj];
           arr[Lobj] = arr[Robj];
           arr[Robj] = temp;
        }
     }
if( arr[Robj] < arr[pivot])
{
    temp = arr[pivot];
    arr[pivot] = arr[Robj];
    arr[Robj] = temp;
}
    return Robj;
}
//.................................................................
void quicksort(int arr[],int Lobj,int Robj)
{
    if(Lobj < Robj)
    {  
       int pivot = Partition(arr,Lobj,Robj);
       quicksort(arr,Lobj,pivot-1);
       quicksort(arr,pivot+1,Robj);
    }
}
//.................................................................
main()
{

    int test[size]={15,20,10,19,11,18,12,17,13,16,14,5,9,0,8,1,7,2,6,3,4};

    quicksort(test,0,size-1);

    for(int i=0;i<size;i++)
    cout<<"\ntest["<<i<<"] = "<<test[i];

    getch();
return 0;
}

 

   برنامه مرتب سازی سریع به زبان #C 

 using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;

namespace WindowsFormsApplication1
{
public partial class Form1 : Form
{
public Form1()
{
InitializeComponent();
}
int Partition(int[] arr, int Lobj, int Robj)
{
    int pivot = Lobj;
    int temp;
    while(Lobj < Robj)
    { 
       while(arr[Lobj] <= arr[pivot])
            Lobj++;

       while(arr[Robj] > arr[pivot])
           Robj--;

       if(Lobj < Robj)
       {
           temp = arr[Lobj];
           arr[Lobj] = arr[Robj];
           arr[Robj] = temp;
       }
    }
if( arr[Robj] < arr[pivot])
{
    temp = arr[pivot];
    arr[pivot] = arr[Robj];
    arr[Robj] = temp;
} return Robj;
}
//.................................................................
void quicksort(int[] arr,int Lobj,int Robj)
{
    if(Lobj < Robj)
    {  
        int pivot = Partition(arr,Lobj,Robj);
        quicksort(arr,Lobj,pivot-1);
        quicksort(arr,pivot+1,Robj);
    }

}

//.......................................................................

private void button1_Click(object sender, EventArgs e)
{
lbl1.Text = "Sorting ...";
int[] test = { 15, 20, 10, 19, 11, 18, 12, 17, 13, 16, 14, 5, 9, 0, 8, 1, 7, 2, 6, 3, 4 };
quicksort(test, 0, test.Length - 1);
lbl1.Text = "";
for (int i = 0; i < test.Length; i++)
lbl1.Text = lbl1.Text + test[i]+",";
}
}
}