- Jesteś tutaj: Portal -> Artykuły -> Podstawy -> Quicksort (N log N)
Wykonamy strony dla firm, osób prywatnych, klubów sportowych, itp. Od prostej wizytówki dla firmy, przez hobbystyczny wortal po bardziej skomplikowane portale, choćby społecznościowe. Oferumy również wykonanie profesjonalnej grafiki. Kontakt gg: 6025719, email: lukiradom@gmail.com. Portfolio: freelancemedia.pl.
Quicksort (N log N)
Witam w pierwszym artykule na tej stronie. Jest on czescia wstepu do dzialu algorytmiki ktory bedziemy rozwijac na naszym portalu. Art traktuje o prostym i zdecydowanie najszybszym algorytmie sortowania jakim jest quicksort. Pokaze Wam tutaj prosta implementacje, ktora dziala w 100%, nie jest to implementacja najszybsza ze wzgledu na rekurencje ale jak wspomnialem chodzi tutaj nie tylko o szybkosc ale tez i o prostote zapisu.
Zanim jednak przejdziemy do rzeczy omowie po krotce zasade dzialania quicksorta. Jest to algorytm klasy O(N log N). Pierwsze co robimy, to odczytujemy wartosc tzw. elementu osiowego, ktorym zazwyczaj jest pierwszy element tablicy. Nastepnie dzielimy tablice wzgledem elementu osiowego, tzn 'przesuwamy' na lewa strone elementy mniejsze od osi a na prawa elementy wieksze od osi. Nastepnie analogicznie kolejne fragmenty traktujemy rekurencja. Tyle z teorii, przejdzmy do praktyki. Ponizej prezentuje przykladowa implementacje algorytmu:
void qsort(int *tab,int lewa,int prawa) //wskaznik na tablice, lewy indeks tablicy, prawy indeks tablicy
{
if(lewa<prawa)
{
int m=lewa;
for(int i=lewa;i<=prawa;i++)
{
if(tab[i]<tab[lewa])
{
swap(tab[++m],tab[i]);
swap(tab[lewa],tab[m]);
}
qsort(tab,lewa,m-1);
qsort(tab,m+1,prawa);
}
}
}
mysle ze nie trzeba tu nic wyjasniac bo kod jest banalny. Nastepnie przyklad uzycia algorytmu:
int tablica[10];
for(int j=0;j<10;j++)
{
cin>>tablica[j];
}
qsort(tablica,0,9);
for(int j=0;j<10;j++)
{
cout<<tablica[j]<<" ";
}
To wszystko :) Jakby byly jakies niejasnosci/bledy zapraszam do komentowania.
luki, [23.11.2009 14:10] Czytań: 110
Zaloguj się, aby komentować artykuły.
luki [27.10.2009 21:58]
przypomina mi sie pierwsze kolko z programowania :]
- Jesteś tutaj: Portal -> Artykuły -> Podstawy -> Quicksort (N log N)
Witam w pierwszym artykule na tej stronie. Jest on czescia wstepu do dzialu algorytmiki ktory bedziemy rozwijac na naszym portalu. Art traktuje o prostym i zdecydowanie najszybszym algorytmie sortowania jakim jest quicksort. Pokaze Wam tutaj prosta implementacje, ktora dziala w 100%, nie jest to implementacja najszybsza ze wzgledu na rekurencje ale jak wspomnialem chodzi tutaj nie tylko o szybkosc ale tez i o prostote zapisu. Zanim jednak przejdziemy do rzeczy omowie po krotce zasade dzialania quicksorta. Jest to algorytm klasy O(N log N). Pierwsze co robimy, to odczytujemy wartosc tzw. elementu osiowego, ktorym zazwyczaj jest pierwszy element tablicy. Nastepnie dzielimy tablice wzgledem elementu osiowego, tzn 'przesuwamy' na lewa strone elementy mniejsze od osi a na prawa elementy wieksze od osi. Nastepnie analogicznie kolejne fragmenty traktujemy rekurencja. Tyle z teorii, przejdzmy do praktyki. Ponizej prezentuje przykladowa implementacje algorytmu:
void qsort(int *tab,int lewa,int prawa) //wskaznik na tablice, lewy indeks tablicy, prawy indeks tablicy
{
if(lewa<prawa)
{
int m=lewa;
for(int i=lewa;i<=prawa;i++)
{
if(tab[i]<tab[lewa])
{
swap(tab[++m],tab[i]);
swap(tab[lewa],tab[m]);
}
qsort(tab,lewa,m-1);
qsort(tab,m+1,prawa);
}
}
}
mysle ze nie trzeba tu nic wyjasniac bo kod jest banalny. Nastepnie przyklad uzycia algorytmu:
int tablica[10];
for(int j=0;j<10;j++)
{
cin>>tablica[j];
}
qsort(tablica,0,9);
for(int j=0;j<10;j++)
{
cout<<tablica[j]<<" ";
}
To wszystko :) Jakby byly jakies niejasnosci/bledy zapraszam do komentowania. luki, [23.11.2009 14:10] Czytań: 110
Zaloguj się, aby komentować artykuły.
| luki [27.10.2009 21:58] |
| przypomina mi sie pierwsze kolko z programowania :] |
