Sortowanie - jaki to algorytm?

Odpowiedz Nowy wątek
2011-08-16 19:07
0

Witam, jestem aspirującym programistą... Wciągnęło mnie to na maksa i z zadaniami/programami jako tako problemów nie mam. Gorzej w momencie kiedy mam spojrzeć na nie od strony analitycznej/teoretycznej... Mianowicie. Napisałem taki sobie oto program, który ma sortować elementy i ku mojej uciesze działa... Cieszy mnie to bardziej, bo sam do tego doszedłem. Tu pojawia się jednak problem. Działa, ale nie potrafię nazwać tego algorytmu. Czy jest to sortowanie bąbelkowe czy przez wstawianie? I jakie są zasadnicze różnice między dwoma powyższymi? Z góry dziękuję za odpowiedź i pozdrawiam. Oto kod:

#include <iostream>
#include <ctime>
#include <conio.h>
 
using namespace std;
 
int LOSUJ(int min = 1, int max = 20);
void WYPELNIANIE_TABLICY(int tablica[], int rozmiar);
void WYPIS(int tablica[], int rozmiar);
void SORT(int tablica[], int rozmiar);
 
int main()
{
    srand(static_cast<int>(time(NULL)));
    int x; //rozmiar tablicy
 
    int *tablica;
 
    cout << "Podaj rozmiar tablicy: ";
    cin >> x;
 
    tablica = new int [x];
 
    WYPELNIANIE_TABLICY(tablica, x);
 
    cout << "Wypisywanie obecnej zawartosci tablicy. Wcisnij klawisz" << endl;
    getch();
 
    WYPIS(tablica, x);
 
    //Sortowanie
    SORT(tablica, x);
 
    cout << "Wypisywanie obecnej zawartosci tablicy po sortowaniu. Wcisnij klawisz" << endl;
    getch();
    WYPIS(tablica, x);
 
    cout << endl;
    delete[] tablica;
    system("pause");
    return 0;
}
 
int LOSUJ(int min, int max)
{
    return rand() % (max - min + 1) + min;
 
}
 
void WYPELNIANIE_TABLICY(int tablica[], int rozmiar)
{
    for(int i = 0; i < rozmiar; i++)
    {
        tablica[i] = LOSUJ();
    }
}
void WYPIS(int tablica[], int rozmiar)
{
    for(int i = 0; i < rozmiar; i++)
    {
        cout << tablica[i] << " ";
    }
}
 
void SORT(int tablica[], int rozmiar)
{
for(int i =(rozmiar - 2); i >=0; i --)
{
    int j = i;
    int temp;
 
    for(j; j < (rozmiar-1); j ++)
    {
        if(tablica[j] > tablica[j+1])
        {
            temp = tablica[j] ;
            tablica[j] = tablica[j+1];
            tablica[j+1] = temp;
        }
    }
 
}
 
}
edytowany 2x, ostatnio: madmike, 2011-08-16 19:13
Temat wątku powinien opisywać problem... Możesz wstawiać kod w znaczniki <code=cpp></code>, zostanie wtedy ładnie "pokolorowany"... Taguj wątki nazwą języka/środowiska... :) - madmike 2011-08-16 19:13

Pozostało 580 znaków

2011-08-16 19:12
1

To jest sortowanie bąbelkowe. Sortowanie bąbelkowe działa w miejscu, sortowanie przez wstawianie raczej nie(operuje na dodatkowej tablicy) i działa nie przez przestawianie elementów, ale przez wstawianie w odpowiednie miejsca elementów z tablicy źródłowej do tablicy docelowej.


Pozostało 580 znaków

2011-08-16 19:14
0

A mógłbym prosić o przerobienie mojej funkcji sortowania na taką, która po uwzględnieniu jako parametr kolejnej tablicy sortuje przez wstawianie? O wiele prościej zrozumieć mi coś kiedy sam widzę jak to działa. I dzięki za odpowiedź

Pozostało 580 znaków

2011-08-16 19:19
0

Ehhh dawno nie miałem do czynienia z pisaniem takich rzeczy (od tego jest stl). Z tego co widzę sortowanie przez wstawianie też może działać w miejscu. Tu masz kod w różnych językach(Ciebie zainteresuje ten w C): http://pl.wikisource.org/wiki/Sortowanie_przez_wstawianie/kod


Pozostało 580 znaków

2011-08-16 19:22
0

No właśnie też zauważyłem, że może działać w miejscu.. Kupiłem ostatnio książkę, traktującą stricte o algorytmach i tam właśnie widziałem przykład ilustrujący działanie sortowania przez wstawianie tylko i wyłącznie na jednej tablicy. Algorytm ten był jednak dziwnie skonstruowany i ciężko było mi pojąć jego działanie. Dlatego chciałbym zobaczyć jak to działa na przykładzie, najlepiej z użyciem pętli for właśnie.

Od strony praktycznej sporo działałem, wymyślałem sobie łatwiejsze bądź trudniejsze zadania i starałem się podejść do nich od jak najbardziej optymalnej i efektywnej strony... Ale teoria u mnie kuleje, głównie dlatego że bardzo mało czasu dotąd jej poświęcałem. Chciałbym jednak zrozumieć, na chwilę obecną, przynajmniej algorytmy sortowania, powinno ułatwić mi to jakiekolwiek działania w przyszłości :D

edytowany 1x, ostatnio: Patryk1992bdg, 2011-08-16 19:24

Pozostało 580 znaków

2011-08-16 19:29
:)
0

to ładnie, że wciągnęło cie programowanie :] Ładniej by jeszcze było gdybyś wyrobił sobie nawyk odpytywania najpierw internetu, a następnie dopiero (i ostatecznie) ludzi na forum. Chodzi mi głównie o drugą prośbę, a nie sam temat

Patryk1992bdg napisał(a)

A mógłbym prosić o przerobienie mojej funkcji sortowania na taką, która po uwzględnieniu jako parametr kolejnej tablicy sortuje przez wstawianie?ź
Dlaczego ktoś za ciebie ma korzystać z google'a skoro sam możesz to zrobić?
Niech ci będzie... czepiam się :)

Pozostało 580 znaków

2011-08-16 19:36
0

Fakt, z tymże ja wolę mieć wszystko w jednym miejscu i o wiele wygodniej byłoby mi zobaczyć drobną modyfikację w moim przykładzie, najlepiej z pętlą for i koniecznie z działaniem na dwóch tablicach aby zrozumieć różnice pomiędzy poprzednią wersją a obecną. W internecie owszem, znalazłem kilka gotowych rozwiązań w C++, ale albo jestem dzisiaj przyćmiony, albo żadne z tych rozwiązań nie rozwiało moich wątpliwości dotyczących różnic pomiędzy tymi dwoma algorytmami sortowania :P

To nawet nie musi być kod, po prostu chcę zrozumieć tą różnicę. Jeżeli ktoś ma zdolności dydaktyczne i wyjaśni mi to bez zobrazowania jakimkolwiek przykładem, to również będę bardzo wdzięczny.

PS2. Przerobiłem funkcję, aby korzystała z nieszczęsnego algorytmu sortowania przez wstawianie. Nadal jednak działa ona tylko na jednej tablicy....

 
void SORT(int tablica[], int rozmiar)
{
 
   int temp;
    int i;
    int j;
 
    for (i = 1; i < rozmiar; ++i) 
    {
       temp= tablica[i];
 
        for (j = i - 1; j >= 0 && tablica[j] > temp; --j) 
        {
            tablica[j + 1] = tablica[j];
        }
 
        tablica[j + 1] = temp;
    }
}
 
edytowany 3x, ostatnio: Patryk1992bdg, 2011-08-16 19:53

Pozostało 580 znaków

2011-08-16 19:55
0

No bez kitu, ale wszystkie podstawowe typy sortowania są w jednym miejscu, na wikisources.

Pozostało 580 znaków

2011-08-16 20:03
2

Co zaglądam do newbie to jestem coraz bardziej wdzięczny, że zaczynałem zabawę z programowaniem, kiedy nie wiedziałem, że istnieje coś takiego jak internet. Siedziało się nad jakimś(nawet błahym) problemem kilka godzin, szło spać, wstawało i takie Aha! w głowie i rozwiązanie jest. Jak można się nauczyć rozwiązywania problemów skoro tylko się wyszukuje gotowe rozwiązania, czy leci na forum z tekstem pokażcie mi, wytłumaczcie mi?
Chyba jednak nie o to chodzi w tej dziedzinie... Potem dostaniesz za zadanie zrobić coś trochę inaczej, coś zmodyfikować i powiesz wykładowcy/pracodawcy "zapytam na forum"?

Argument, że najlepiej się komuś uczy na przykładach też jest do niczego. Bo co? Nauczysz się na pamięć jakiegoś algorytmu? Jak przyjdzie Ci coś wymyślić, zmienić, poprawić to się wyłożysz...


Pozostało 580 znaków

2011-08-16 20:11
0

Gdybym liczył na gotowe rozwiązania, to bym się zadowolił Twoim linkiem z gotowym kodem. Problem był. I był on następujący: posortować elementy. Sam doszedłem do tego w jaki sposób i udało mi się. Więc problem rozwiązałem. Wiem jednak, że są też alternatywy jego rozwiązania i na podstawie porównania dwóch metod chcę wyłuskać najlepsze cechy obu, aby wiedzieć którą stosować. Ale żeby tak postąpić, muszę w pełni zrozumieć metodę przez wstawianie, a gotowe kody mi tu nie pomogą. Rozumiem intuicyjnie na czym ona polega, jak działa, ale jakoś nie mogę sobie tego przełożyć na implementację kodu.

Powiem tak: ja byłem przekonany, że moja metoda, zaprezentowana w pierwszym poście jest właśnie według algorytmu sortowania przez wstawianie. Bo przecież, działając na jednej tablicy, nie da się "wstawić" czegoś, bez naruszania struktury już wpisanych danych, więc naturalna była dla mnie zamiana miejscami pól. Ale jeżeli jest to sortowanie bąbelkowe, to nadal nie wiem jak działa algorytm ze wstawianiem...

edytowany 1x, ostatnio: Patryk1992bdg, 2011-08-16 20:18

Pozostało 580 znaków

2011-08-16 20:30
1

http://www.sorting-algorithms.com/

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0