Printable View
ميشه الگوريتم كوئيك سورت را با عنصر محوري وسط (mid) برام بنويسين
خودم فكر مي كنم كه بايد در قسمت افراز ارايه به جاي يك حلقه for از دو تا for استفاده كنيم يكي براي mid-1 و يكي براي mid+2 ايا درست هست يا نه و ايا اين الگوريتم با قسمتاي سورت ادغام بشه ايا پيچيدگي ميشه 2n^2 يا nlogn
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);
}
}
az zahmati ke keshidin merc vali algoritmeton dar amal kar nemikone va ye jorie
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 ;
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 ) ;
}
بالایی اشتب شده بود برای بازگشتیش