پيچيدگي quicksort

[taher64]

ميشه الگوريتم كوئيك سورت را با عنصر محوري وسط (mid) برام بنويسين
خودم فكر مي كنم كه بايد در قسمت افراز ارايه به جاي يك حلقه for از دو تا for استفاده كنيم يكي براي mid-1 و يكي براي mid+2 ايا درست هست يا نه و ايا اين الگوريتم با قسمتاي سورت ادغام بشه ايا پيچيدگي ميشه 2n^2 يا nlogn

[mortezamsp]

int quick_sort(int*A,int L,int u)

{

int pivot,i,j;

    if( L < u )

    {

        pivot=A[L];

        i=L;

        j=u;

        while(i>=j)

        {

            while(A[i]>pivot)

                i++;

            while(A[j]<pivot)

                j--;

            if(i<j)

                swap(A[i],A[j]);

        }

        swap(A[L],A[j]);

        quick_sort(A,L,j-1);

        quick_sort(A,j+1,u);

    }

 

}

[taher64]

az zahmati ke keshidin merc vali algoritmeton dar amal kar nemikone va ye jorie

[saymon]

ArrayList x = new ArrayList();

        ArrayList y = new ArrayList();

 private void quicksort()

        {

            int i, j,pivot,ind;

            

            do

            {

                int temp = 0;

                bool t = false;

                ind=(int)x[0];

                pivot = a[ind];

                i = (int)x[0]+1;

                 j = (int)y[0];

                 if (i == j)

                 {

                     if (a[i] < a[i - 1])

                     {

                         temp = a[i-1];

                         a[i-1] = a[i];

                         a[i] = temp;

                     }

                 }

                while (i < j)

                {

                    t=true;

                    while (pivot > a[i])

                    {

                        i++;

                    }

                    while (pivot < a[j])

                    {

                        j--;

                    }

                   

                   if (i < j)

                    {

                        temp = a[j];

                        a[j] = a[i];

                        a[i] = temp;

                    }

                    else

                    {

                        temp = a[j];

                        a[j] = a[ind];

                        a[ind] = temp;

                    }

                }

                if (t)

                {

                    x.Add(x[0]);

                    y.Add(j - 1);

                    x.Add(j + 1);

                    y.Add(y[0]);

                }

                x.RemoveAt(0);

                y.RemoveAt(0);

            } while (x.Count != 0);

        }

این البته بدون بازگشتیه اما برای باز گشتیش

Void insert ( int x , node * start )
{
node * p , * q , * new node ;
q = start → next ;
p = start ; new node = new ( node ) ; new node → data = x ;
while ( q → data < )datanewnodex4434421→
{
p = q ;
q = q → next ;
}
new node → next = p → next ;
p → next = new node ;

[saymon]

Void quicksort (int L , int U )

{

int i , j , pivot ;

if ( L < U )

{

i = L + 1 ; j = U ; pivot = A[L] ;

while ( i < j )

{

while ( A [i] < pivot ) i + + ;

while ( A[j] > pivot ) j - - ;

if ( i < j ) swap ( A[i] , A[j]) ;

}

swap ( A[L] , A[j] ) ;

quicksort ( L , j – 1 ) ;

quicksort ( j + 1 , U ) ;

}

بالایی اشتب شده بود برای بازگشتیش