Jan 2021
1 / 9
Jan 2021
Jan 2021
coding_amator1
Jan '21
4

Witajcie,
ostatnio po zapoznaniu się z algorytmami sortowania, nabrałem chęci na stworzenie własnego algorytmu w języku C++. Zacząłem pisać, mineła godzinka i udało się. Nie należy do najszybszych ale na pewno jest szybszy od sortowania bąbelkowego. Link do kodu mierzącego czas sortowania tym algorytmem: https://ideone.com/Auh6T810
Biblioteki windows.h i time.h zostały dodane tylko po to, aby moc wylosowac liczby i sprawdzic szybkosc algorytmu.

Chciałbym żebyście go ocenili, oraz zachęcam was do stworzenia włansego algorytmu, i podzielenia się nim. Zróbmy challange na najszybszy, customowy algorytm sortujący (nie wykorzystujcie już stworzonych algorytmów, np quicksorta)

PS: Moj algorytm sortuje od najmniejszej do najwiekszej, ale da sie go latwo przestawic.

  • created

    Jan '21

  • last reply

    Jan '21
  • 8

    replies

  • 655

    views

  • 4

    users

  • 4

    likes

  • 3

    links

macbon
Jan '21

Naprawdę szacunek za podjęcie próby stworzenia własnego algorytmu sortowania. Niestety Twój algorytm nie jest szybszy od sortowania bąbelkowego, a wręcz przeciwnie w pesymistycznym przypadku jest zdecydowanie wolniejszy. Spowodowane jest to tym, że czas sortowania uzależniony jest od wielkości największej liczby jaka znajdzie się w tablicy. Im większa będzie ta liczba tym wolniejszy staje się Twój algorytm. Poniżej masz link do kodu, który generuje elementy tablicy z przedziału [1000000000, 1000001000). Posortowanie zaledwie 4 elementów zabrało mu ponad 3s na serwerze ideone, który jest bardzo wydajny.

macbon
Jan '21

Zawsze próbuj bo w ten sposób się możesz najwiecej nauczyć!

coding_amator1
Jan '21

Poprawilem nieco swoj kod, wprowadzajac poprawki w samej petli procedury oraz w funkcji main. Petla zawsze zaczynala sie od zera, co powodowalo brak funkcjonalnosci w przypadku tablicy z liczbami ujemnymi, naprawilem to dodajac obliczanie najmniejszej liczby w tablicy, od ktorej petla w procedurze bedzie sie zaczynac. Poza tym dzieki temu zmniejszylem czas sortowania, zacislajac zakres liczb w petli. Link do kodu: https://ideone.com/Auh6T82

macbon
Jan '21

Kilka uwag dla Ciebie:

  1. W tym programie plik nagłówkowy windows.h nie jest Ci do niczego potrzebny
  2. Jeżeli kodujesz w C++ to pliki nagłówkowe z języka C jak np. time.h powinieneś dołączać usuwając z nazwy .h i dodając c z przodu czyli ctime zamiast time.h, cstdio zamiast stdio.h itd.
  3. Liczenie najmniejszej i największej liczby możesz zrobić bez tego warunku na 0 element. Robisz to w następujący sposób zmienną najmniejszy ustawiasz na maksymalną wartość jaką jest w stanie przechować typ int. Następnie w pętli aktualizujesz ją za pomocą funkcji min. Analogicznie robisz dla zmiennej największa. Wygląda to mniej więcej tak:
    #include < limits >
    …
    int najmniejsza = numeric_limits::max(); // Możesz też użyć stałej INT_MAX z pliku climits
    int najwieksza = numeric_limits::min(); // Możesz też użyć stałej INT_MIN z pliku climits
    for (int i = 0; i < n; ++i) {
    …
    najmniejsza = min(najmniejsza, tablica[i]);
    najwieksza = max(najwieksza, tablica[i]);
    …
    }
coding_amator1
Jan '21

Gdybym zrozumial chociaz troche z twojego kodu to bym moze skomentowal, narazie widze tylko ze dziala, ale kod to prawdziwa enigma! Przynajmniej dla mnie.

pwojszepielak
Jan '21

Program @hipcia to żart.
ultra_hipcio_sort ma niewiele linijek, więc łatwo wygooglować co robi każda instrukcja.