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

question-closed złożoność czasowa i pamięciowa algorytmu inOrder (chyba inaczej sortowanie Stogowe) w drzewie poszukiwań binarnych

Object Storage Arubacloud
+1 głos
1,016 wizyt
pytanie zadane 24 sierpnia 2017 w C i C++ przez Jakub 0 Pasjonat (23,120 p.)
zamknięte 24 sierpnia 2017 przez Jakub 0

hej, ostatnio natknąłem się na bardzo ciekawy algorytm sortowania wykorzystujący drzewo binarne - *a nie kopiec* (nigdy o nim nie słyszałem w kursie Pana Mirosława ani na żadnych stronach) ,mowa tu o inOrder (przynajmniej ja tak to nazwałem :D) . Nie mogłem znaleźć na temat tego algorytmu więcej informacji ,nie wiem czemu bo dla mnie jest bardzo ciekawy (może nawet lepszy od Heap sort którego niezbyt lubię)  . By uniknąć problemów podam cały kod sortowania oraz moją implementacje całego drzewa binarnego - co o niej sądzicie co mogę poprawić ? . Z góry dziękuje za odpowiedzi i komentarze oraz pozdrawiam :)

oto kod samego inOrder:

void inOrder(DataTrees *parent) { //sosrtowaanioe
	if (parent) {
		inOrder(parent->leftChild);
		cout << parent->data << " ";
		inOrder(parent->rightChild);
	}
}

Cały program (napisany w VS więc w pliku stdafx mamy biblioteki):

#include "stdafx.h"

using namespace std;

struct DataTrees {
	int data;
	DataTrees *leftChild;
	DataTrees *rightChild;
};

void add(DataTrees *&parent, int value) { //wstawaianie elementu 
	if (!parent) { //jezeli jest tu puste mijsce
		parent = new DataTrees;
		parent->data = value;
		parent->leftChild = nullptr;
		parent->rightChild = nullptr;
	}
	else { //pezeszukiwanie 
		if (value >= parent->data) add(parent->rightChild, value);
		else add(parent->leftChild, value);
	}
}

void inOrder(DataTrees *parent) { //sosrtowaanioe
	if (parent) {
		inOrder(parent->leftChild);
		cout << parent->data << " ";
		inOrder(parent->rightChild);
	}
}

void find(DataTrees *parent, DataTrees *&element, int value) { //poszukiwanie danej wartosci i ustawianie wskaznika na odpowiedni obiekt 
	if (!parent) { //jezeli nie znaleziono i nie ma juzz wiecej elementow 
		cout << "error" << endl;
	}
	else if (parent->data == value) { //jezeli znaleziono
		element = parent;
		cout << "is good! " << endl;
	}
	else { //poszukiwanie binarne 
		if (value < parent->data) find(parent->leftChild,element,value);
		else find(parent->rightChild, element, value);
	}
}

void deleteTree(DataTrees *&element) { //usowanie drzewa 
		if(element)deleteTree(element->leftChild);
		if(element)deleteTree(element->rightChild);
		element = nullptr;
}


int main()
{
	DataTrees *root = nullptr;
	DataTrees *element = nullptr;

	while (true) {
		cout << "---MENU---" << endl;
		cout << "1. add" << endl;
		cout << "2. inOrder" << endl;
		cout << "3. find" << endl;
		cout << "4. show find element" << endl;
		cout << "5. delete tree" << endl;
		cout << "----------" << endl;

		char z = _getch();

		switch (z) {
		case '1': {
			cout << "value: ";
			int v; cin >> v;
			add(root, v);
			break;
		}
		case '2': {
			if (root) {
				cout << "sort: ";
				if(root) inOrder(root);
				else cout << 0;
			}
			else cout << 0 << endl;

			_getch();
			break;
		}
		case '3': {
			cout << "value: ";
			int v; cin >> v;
			find(root, element, v);
			_getch();
			break;
		}
		case '4': {
			if (element) {
				cout << "value: " << element->data << endl;
			}
			else cout << 0 << endl;
			_getch();
			break;
		}
		case '5': {
			deleteTree(root);
			break;
		}
		}

		system("cls");
	}

    return 0;
}

 

komentarz zamknięcia: już znam odpowiedź
komentarz 24 sierpnia 2017 przez Jakub 0 Pasjonat (23,120 p.)
edycja 24 sierpnia 2017 przez Jakub 0
Aaa, już odkryłem że ten algorytm inaczej nazywa się sortowaniem stogowym ,ale i tak nie znalazłem zbytnio informacji na temat jego złożoności (po za tym wyskakuje mi wtedy w większości przypadków sortowanie przez kopcowanie a nie to)
1
komentarz 24 sierpnia 2017 przez jpacanowski VIP (101,940 p.)

Aaa, już odkryłem że ten algorytm inaczej nazywa się sortowaniem stogowym

O tym już wiedziałeś zakładając temat przecież ;)

komentarz 24 sierpnia 2017 przez Jakub 0 Pasjonat (23,120 p.)
nie wiedziałem ,zmieniłem nazwę tematu już po czasie

3 odpowiedzi

+1 głos
odpowiedź 24 sierpnia 2017 przez TenGumis Gaduła (3,440 p.)
wybrane 24 sierpnia 2017 przez Jakub 0
 
Najlepsza
Nie możesz znaleźć informacji o tym sortowaniu ponieważ to nie jest sortowanie. Drzewo binarne z definicji zachowuje porządek na węzłach więc to co robi twoja funkcja inOrder to poprostu wypisuje to w dobrej kolejności.
Algorytmem sortującym można by byo nazwać procedurę która:

1. Tworzy puste drzewo.
2. Dodaje kolejne elementy do drzewa
3. Wypisuje je inOrder.

Wtedy taka procedura ma złożoność zgrubsza O(n log n) gdzie n to liczba elementów co jest porównywalne z quicksortem/ mergesortem i innymi algorytmami o takiej złożoności.

Dlaczego taka złożoność?
Krok drugi działa w czasie O(log n) dla każdego z n elementów co daje nam sumaryczną złożonośc taką jak napisałem.
Krok 3 działa w czasie O(n). NIe należy myśleć że zatem sortuje on w czasie liniowym (bo krok 3 jest liniowo) bo jest tak tylko dlatego że sturuktura ma taką własność że jest w pewien szczególny sposób uporządkowana
komentarz 24 sierpnia 2017 przez Jakub 0 Pasjonat (23,120 p.)
dzięki ,właśnie to miałem na myśli .Podałem cały kod bo właśnie sądziłem że sortowanie stanowi to jako całość .Jestem dość zadowolony z tego wykorzystania drzewa bo jak sam napisałeś złożoność wynosi O(n log n) więc jest dość szybka i po za tym zrobiłem jeszcze testy porównawcze z innymi algorytmami . Dzięki jeszcze raz i pozdrawiam
komentarz 16 września 2018 przez Mariusz M Obywatel (1,670 p.)

Tak te trzy punkty które Gumiś wymienił to sortowanie drzewiaste
i różni się nieco od stogowego 
J
a go używam do sortowania list
(dla listy jednokierunkowej wskaźnik na poprzednika jest używany przez drzewo BST)
Procedura wstawiającą węzły listy do drzewa i
procedurę przekształcającą drzewo w listę przechodząc drzewo w kolejności inOrder
mam napisane rekurencyjnie
Asymptotyczna złożoność czasowa taka sama jak dla sortowania przez podział
O(nlog(n)) w średnim przypadku , O(n^2) w przypadku pesymistycznym
Przypadek pesymistyczny występuje gdy nasze drzewko redukuje się do listy

 

komentarz 17 września 2018 przez Jakub 0 Pasjonat (23,120 p.)
Dzięki za chęć pomocy. Ale to pytanie jest zamknięte od roku... :/
komentarz 3 grudnia 2018 przez Mariusz M Obywatel (1,670 p.)
Tak ale może się przydać też innym
Dziwne  te praktyki zamykania tematów

choć są charakterystyczne dla pewnej grupy osób, szczególnie młodych
0 głosów
odpowiedź 24 sierpnia 2017 przez d0n Mądrala (6,440 p.)
To jest drzewo BST, jego lepsze wersje to drzewo czerwone czarne i AVL
komentarz 24 sierpnia 2017 przez Jakub 0 Pasjonat (23,120 p.)
Dzięki za ważną informację  ,chociaż na start ten rodzaj drzewa powinien mi wystarczyć (no bo co mi na razie przeszkadza że lewe pod drzewo jest większe od prawego) . Wiesz może jeszcze jaka jest albo gdzie można znaleźć informacje na temat złożoności algorytmu sortowania użytego w tym programie ?
komentarz 24 sierpnia 2017 przez Jakub 0 Pasjonat (23,120 p.)
*bo nie wiem czy się opłaca go stosować
0 głosów
odpowiedź 24 sierpnia 2017 przez mokrowski Mędrzec (156,220 p.)
Nigdzie nie można znaleźć informacji? https://pl.wikipedia.org/wiki/Sortowanie_przez_kopcowanie
1
komentarz 24 sierpnia 2017 przez maciek061 Gaduła (4,490 p.)
Autor pisał, że nie o to chodzi
komentarz 24 sierpnia 2017 przez Jakub 0 Pasjonat (23,120 p.)

dzięki za chęć pomocy ale w pytaniu pisze tak:

hej, ostatnio natknąłem się na bardzo ciekawy algorytm sortowania wykorzystujący drzewo binarne - *a nie kopiec*

logiczne że sortowanie przez kopcowanie jest tak znane że sam na nie wpadam :) 

1
komentarz 24 sierpnia 2017 przez maciek061 Gaduła (4,490 p.)
No nie wiem, tak jest napisane w komentarzu do pytania
komentarz 24 sierpnia 2017 przez Jakub 0 Pasjonat (23,120 p.)
no czyli dobrze napisałeś że nie sortowanie dzięki kopcowi miałem na myśli

Podobne pytania

0 głosów
1 odpowiedź 463 wizyt
pytanie zadane 3 grudnia 2018 w Algorytmy przez VinVix Nowicjusz (240 p.)
0 głosów
1 odpowiedź 974 wizyt
0 głosów
1 odpowiedź 696 wizyt

92,757 zapytań

141,677 odpowiedzi

320,429 komentarzy

62,101 pasjonatów

Motyw:

Akcja Pajacyk

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

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...