• 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
48 wizyt
pytanie zadane 13 października w C i C++ przez KageNoYami Nowicjusz (190 p.)
otwarte ponownie 13 października 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 przez tkz Nałogowiec (40,840 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 przez KageNoYami Nowicjusz (190 p.)
edycja 13 października 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 przez tkz Nałogowiec (40,840 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 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 przez tkz Nałogowiec (40,840 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 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 przez Wiciorny Mędrzec (186,250 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 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 przez Wiciorny Mędrzec (186,250 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 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
0 odpowiedzi 29 wizyt
pytanie zadane 6 maja 2020 w Java przez danielo665 Obywatel (1,030 p.)
0 głosów
1 odpowiedź 73 wizyt
pytanie zadane 27 czerwca 2018 w C i C++ przez Piotr Lis Obywatel (1,330 p.)

85,802 zapytań

134,588 odpowiedzi

298,790 komentarzy

56,697 pasjonatów

Advent of Code 2021

Top 15 użytkowników

  1. 494p. - rucin93
  2. 482p. - CC PL
  3. 463p. - nidomika
  4. 385p. - Whistleroosh
  5. 379p. - ScriptyChris
  6. 372p. - adrian17
  7. 340p. - TheLukaszNs
  8. 339p. - WhiskeyTaster
  9. 321p. - Argeento
  10. 318p. - Dagohar
  11. 287p. - Anonim 1794483
  12. 281p. - Klaudia
  13. 278p. - B4mbus
  14. 269p. - b0mbix
  15. 246p. - tokox
Szczegóły i pełne wyniki

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.

...