• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Problem z Sortowaniem - Guardian Sort

0 głosów
55 wizyt
pytanie zadane 13 października 2021 w C i C++ przez KageNoYami Nowicjusz (190 p.)
otwarte ponownie 13 października 2021 przez KageNoYami

Dzień Dobry.
Postanowiłem stworzyć nowy (chyba) system sortowania, który nazwałem Guardian Sort. Jest w budowie podobny do Bubble Sort, ale łatwiejszy. Jest jednak problem - nie działa, pomimo iż logicznie jest prawidłowy.

#include <iostream>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include <conio.h>
#include <new>

using namespace std;

//GUARDIAN-SORT
int main()
{
    srand((unsigned)time(NULL));
    int n = 5;
    int *tab = new int[n];
    
    cout<<"Random number: "<<endl;
    for(int i = 0; i < n; i++)
    {
        tab[i] = rand()%99+1;
        cout<<tab[i]<<endl;
    }
    
    int helper;
    bool guardian = true;
    
    cout<<"Sorted number: "<<endl;
    while(guardian)
    {
        guardian = true;
        for(int i = 1; i < n; i++)
        {
            if(tab[i] < tab[i-1])
            {
                helper = tab[i];
                tab[i] = tab[i-1];
                tab[i-1] = helper;
                guardian = false;
                cout<<"IMPROVE"<<endl;
            }
        }
    }
    
    for(int i = 0; i < n; i++)
    {
        cout<<tab[i]<<endl;
    }

    return 0;
}

 

komentarz 13 października 2021 przez tkz Nałogowiec (41,420 p.)
Udowodnisz słowami, że ma to logiczny sens? Póki co, wygląda to na sortowanie bąbelkowe, tylko z deczko upośledzone. Ten while pasuje jak pięść do nosa... Nie masz prawidłowego warunku stopu dla założenia.
komentarz 13 października 2021 przez KageNoYami Nowicjusz (190 p.)
edycja 13 października 2021 przez KageNoYami
Otóż bez while, te sortowanie nie miało by sensu. Założenie jest takie: Jeśli w pętli wszystko jest posortowane i już nic nie trzeba sortować, automatycznie się przerwie. Guardian właśnie tego pilnuje.

Jeśli cokolwiek zostanie posortowane,Guardian nie pozwoli do zamknięcia pętli. Powie: "Hola, nie mamy pewności, czy wszystko jest git. Trzeba zrobić pętle raz jeszcze".
Jeśli zaś if nie wykona się ani razu (nic nie zostało już posortowane, znakiem tego że już wszystko jest na miejscu), Guardian już nie powie, że coś jest nie tak - pętla zrobi się raz jeszcze dla upewnienia i się przerwie.

(edit)

Albo żeby jeszcze lepiej to zobrazować, wyobraź sobie że Guardian z każdym wykonaniem pętli, daje ci przepustkę. Przepustkę, która umożliwia ci wyjście z pętli.
Jednak jeśli ciąg liczb będzie niedobry, zabierze ją i każe się poprawić.
Tak w kółko i w kółko, aż w końcu ciąg liczb będzie dobry.
Wtedy nie zabierze ci przepustki i będziesz mógł spokojnie odejść z dobrym ciągiem.
1
komentarz 13 października 2021 przez tkz Nałogowiec (41,420 p.)
#include <iostream>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include <conio.h>
#include <new>
 
using namespace std;
 
//GUARDIAN-SORT
int main()
{
    srand((unsigned)time(NULL));
    int n = 5;
    int *tab = new int[n];
     
    cout<<"Random number: "<<endl;
    for(int i = 0; i < n; i++)
    {
        tab[i] = rand()%99+1;
        cout<<tab[i]<<endl;
    }
     
    int helper;
    bool guardian = true;
     
    cout<<"Sorted number: "<<endl;
// mamy 43 23 12 54 23
    while(guardian)
    {
        guardian = true;
        for(int i = 1; i < n; i++)
        {
            //tab[i]=23 tab[i-1]=43
            //czyli wchodzimy
            if(tab[i] < tab[i-1])
            {
                helper = tab[i];
                tab[i] = tab[i-1];
                tab[i-1] = helper;
                guardian = false; //po tym petla nie powtorzy sie ani razu
                cout<<"IMPROVE"<<endl;
            }
        }
    }
     
    for(int i = 0; i < n; i++)
    {
        cout<<tab[i]<<endl;
    }
 
    return 0;
}

cpp.sh/4gk65 Twój kod nie działa według założeń. 

komentarz 13 października 2021 przez KageNoYami Nowicjusz (190 p.)
#include <iostream>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include <conio.h>
#include <new>

using namespace std;

//GUARDIAN-SORT
int main()
{
    srand((unsigned)time(NULL));
    int n = 5;
    int *tab = new int[n];
    
    cout<<"Random number: "<<endl;
    for(int i = 0; i < n; i++)
    {
        tab[i] = rand()%99+1;
        cout<<tab[i]<<endl;
    }
    
    int helper;
    bool guardian = true;
    
    cout<<"Sorted number: "<<endl;
    while(guardian)
    {
        guardian = false;
        for(int i = 1; i < n; i++)
        {
            if(tab[i] < tab[i-1])
            {
                helper = tab[i];
                tab[i] = tab[i-1];
                tab[i-1] = helper;
                guardian = true;
                cout<<"IMPROVE"<<endl;
            }
        }
    }
    
    for(int i = 0; i < n; i++)
    {
        cout<<tab[i]<<endl;
    }

    return 0;
}

Masz absolutną racje, zrobiłem okropny błąd xD
Nie wiem czemu odwrotnie napisałem, ale teraz działa jak należy.

Dzięki za pomoc.

komentarz 13 października 2021 przez tkz Nałogowiec (41,420 p.)
I czym różni się to od sortowania bąbelkowego? Złożoność jest taka sam, w zasadzie kod również, masz po prostu inną pętlę.
komentarz 13 października 2021 przez KageNoYami Nowicjusz (190 p.)
Łatwiej jest mi go sobie wyobrazić, zrozumieć. Złożoność jest podobna, ale napisanie i wytłumaczenie jego jest moim zdaniem prostsze.
komentarz 13 października 2021 przez Wiciorny Mędrzec (197,420 p.)

Łatwiej jest mi go sobie wyobrazić, zrozumieć. 

dobr ale bubble sory jak i inne algorytmy można zaimplementować na 30 sposobów np? I wiele z nich jest prostych jak układanie klocków przez dziecko, to nie ma podstawy żeby nazwać algorytm "nową nazwa" tylko dlatego że go lepiej rozumiesz, jeśli nie zmienia złożoności, działa w analogiczny sposób. 
 


class BubbleSort
{
    void bubbleSort(int arr[])
    {
        int n = arr.length;
        for (int i = 0; i < n-1; i++)
            for (int j = 0; j < n-i-1; j++)
                if (arr[j] > arr[j+1])
                {
                    // swap arr[j+1] and arr[j]
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
 }
// juz pomijam fakt na bazie skrócenia, ale dodawanie  pętli while i twojego "guardian" nie ma sensu 
// to sztuka dla sztuki i taki zabieg nic nie wnosi 

 

komentarz 13 października 2021 przez KageNoYami Nowicjusz (190 p.)
Jakby nie patrzeć różni się on lekko od Bubble Sorta, przynajmniej tych podręcznikowych wersji z użyciem dwóch forów. Jako podtyp zaklasyfikowałbym go w takim razie jako Bubble Sort Guardian, aby jakoś odróżnić te "30 sposobów".
komentarz 13 października 2021 przez Wiciorny Mędrzec (197,420 p.)

podstawowa wersja Bubble Sort jest oparta o while... :) 

procedure bubbleSort(A : list of sortable items)
    n := length(A)
    repeat
        swapped := false
        for i := 1 to n - 1 inclusive do
            if A[i - 1] > A[i] then
                swap(A[i - 1], A[i])
                swapped := true
            end if
        end for
        n := n - 1
    until not swapped
end procedure
komentarz 14 października 2021 przez KageNoYami Nowicjusz (190 p.)
To ciekawe bo mnie uczyli na forach :p
Ameryki widocznie nie odkryłem (nie zamierzałem nawet), zauważyłem po prostu że na while się łatwiej robi.

Zaloguj lub zarejestruj się, aby odpowiedzieć na to pytanie.

Podobne pytania

0 głosów
1 odpowiedź 123 wizyt
0 głosów
1 odpowiedź 41 wizyt
pytanie zadane 11 stycznia w C i C++ przez HUBSON2912 Początkujący (490 p.)
0 głosów
0 odpowiedzi 30 wizyt
pytanie zadane 6 maja 2020 w Java przez danielo665 Obywatel (1,030 p.)

86,483 zapytań

135,239 odpowiedzi

300,480 komentarzy

57,230 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto dwie polecane książki warte uwagi. Pełną listę znajdziesz tutaj.

...