Tytuł: Sortowanie Wiadomość wysłana przez: admin Listopad 28, 2012, 08:56:44 Sortowanie bąbelkowe.
Algorytm ten polega na porównywaniu i ewentualnej zamianie miejscami par sąsiadujących ze sobą elementów. Sortowanie rozpoczyna się od końca lub początku tablicy. Jeżeli sortujemy rosnąco, to ostatni element tablicy porównywany jest z tym stojącym przed nim. Jeżeli ostatni jest mniejszy od przedostatniego następuje zamiana miejscami. Jeżeli przedostatni jest mniejszy od ostatniego, to on staje się bąbelkiem i jest porównywany z kolejnymi. Poszczególne elementy zmieniają miejsce w tablicy o jedną pozycje i powoli wędrują na swoje miejsce. Algorytm jest dobry dla małych tablic częściowo już posortowanych. Jest to algorytm klasy O(N2) #include <cstdlib> #include <iostream> using namespace std; int main(int argc, char *argv[]) { int i,j,x,tmp; int tablica[5]; /* wczytywanie liczb z klawiatury */ cout << "Podaj 5 liczb : \n"; for (i=0; i<=4; i++) cin >>tablica[ i ]; /*wyświetlenie liczb w podanej kolejności*/ for (i=0; i<=4; i++) {cout.width(3);cout << tablica[ i ]; } cout << "\n\n"; /* sortowanie bąbelkowe */ for (i=0;i<=3; i++) for (j=0;j<=3; j++) if (tablica[j]>tablica[j+1]) {tmp = tablica[j]; tablica[j] = tablica[j+1]; tablica[j+1] = tmp; } cout << "\n"; /* wyświetlanie posortowanych liczb */ for (i=0; i<=4; i++) {cout.width(3);cout << tablica[ i ]; } cout<<endl; system("PAUSE"); return EXIT_SUCCESS; } Tytuł: Odp: Sortowanie Wiadomość wysłana przez: admin Listopad 28, 2012, 09:33:37 Sortowanie szybkie
Algorytm sortowania szybkiego jest uważany za najszybszy algorytm dla danych losowych. Zasada jego działania opiera się o metodę dziel i zwyciężaj. Na początku wybiera się tzw. element osiowy (pewien element tablicy np. jej środek nazywany pivot), po czym na początek tablicy przenoszone są wszystkie elementy mniejsze od niego, na koniec większe, a w powstałe między tymi obszarami puste miejsca trafia wybrany element. Następnie sortuje się osobno początkową i końcową część tablicy. Zbiór danych zostaje podzielony na dwa podzbiory i każdy z nich jest sortowany niezależnie od drugiego. Dla zadanej tablicy A[1..p] wybieramy element p=A[l] i przeszukujemy resztę tablicy (tzn. A[l+1..p]) tak długo, aż nie znajdziemy elementu większego niż A[l]. Następnie przeszukujemy tą tablicę od strony prawej póki nie znajdziemy elementu nie większego niż A[l]. Gdy to osiągniemy, zamieniamy miejscami te dwa elementy i zaczynamy cały proces od początku. Algorytm działa tak długo, aż wskaźnik poruszający się w lewo i wskaźnik poruszający się w prawo spotkają się. Należy wówczas zamienić element p=A[l] z ostatnim elementem lewej części tablicy. Tytuł: Odp: Sortowanie Wiadomość wysłana przez: admin Listopad 28, 2012, 10:06:08 Sortowanie przez kopcowanie ( kubełkowe).
|