PDA

View Full Version : سوال: پيچيدگي quicksort



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

mortezamsp
جمعه 29 آبان 1388, 17:47 عصر
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
جمعه 29 آبان 1388, 21:03 عصر
az zahmati ke keshidin merc vali algoritmeton dar amal kar nemikone va ye jorie

saymon
یک شنبه 01 آذر 1388, 20:04 عصر
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
یک شنبه 01 آذر 1388, 20:06 عصر
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 ) ;
}
بالایی اشتب شده بود برای بازگشتیش