c++ Metis: Jak najefektywniej uporządkować liczby w tablicy C++ ? Kod: http://pastebin.com/7LeR3yqC Teraz chcę wszystkie liczby zawarte w tablicy wyświetlić w kolejności np. malejącej. Słuzy do tego jakaś funkcja? Mogę umieścić to w pętli i używać warunków if else, ale nie podoba mi się to wyjście.

Metis: Dodatkowo, czy mogę obejść się bez komunikatu "Ile liczb chcesz wpisać" Chciałbym by program zapisywał do tablicy coraz to kolejne wpisane liczby, do pewnego momentu np void close() { exit(0); } char close; if (close=='T' && close=='t') close();

Benny: Nie mogę odpalić tego linku, ale żeby wyświetlić w kolejności malejącej możesz skorzystać z jakiegokolwiek sortowania. Wystarczy zamienić kolejność sortowania na ciąg malejący.

Metis: #include "stdafx.h" #include <iostream> #include <conio.h> using namespace std; int ilosc, *tab; int main() { cout << "Podaj ilosc liczb chcesz wpisac" << endl << ">"; cin >> ilosc; tab = new int[ilosc]; for (int i = 0; i < ilosc; i++) { cout << "Podaj " << i + 1 << " liczbe: "; cin >> tab[i]; } _getch(); }

Mariusz: Benny kiedyś pisałeś sortowanie stogowe myślę że tutaj byłoby dobre bo 1 Nie mamy rekurencji 2 Mamy gwarancję czasu nlogn 3 Sortujemy w miejscu Niestety wada takiego rozwiązania to brak stabilności tzn oryginalna kolejność kluczy może nie być zachowana

jakubs: Mariusz W dodatku złożoność pamięciowa jest liniowa. Polecam: http://www.cplusplus.com/reference/algorithm/sort/

Metis: Benny chodzi mi o najefektywniejsze; Co jeśli uzytkownik wpisze 100 liczb, petla bedzie mało efektywna. Chodzi o to, że gdy tablica bedzie już zapełniona np.: 1,4,5,10,2,3, 5, 2, 1 to program jak najszybciej posortuje te liczby.

Mariusz: Jak tak to brać to złożoność pamięciowa zawsze jest liniowa Z tym sortowaniem w miejscu chodzi o to że nie potrzebujemy dodatkowej pamięci jak w przypadku sortowania przez scalanie Benny pamiętasz numer tego wątku w którym dałeś te sortowanie stogowe do sprawdzenia bo ta szukajka forumowa kiepsko działa

Mariusz: Szukajka forumowa kiepsko działa ale tu masz kod Bennego w C #include<stdio.h> #include<stdlib.h> #include<time.h> #include<conio.h> void Przesiewanie(int ,int ,int* ); void BudujStog(int ,int* ); void SortowanieStogowe(int ,int* ); int main() { int k,n; int* A; char esc; do { printf("Podaj rozmiar tablicy\n"); scanf("%d",&n); A=(int*)malloc(n*sizeof(int)); srand(time(NULL)); for(k=0;k<n;k++) A[k]=rand()%100; printf("Przed sortowaniem\n"); for(k=0;k<n;k++) printf("%d ",A[k]); printf("\n"); SortowanieStogowe(n,A); printf("Po sortowaniu\n"); for(k=0;k<n;k++) printf("%d ",A[k]); printf("\n"); esc=getch(); } while(esc!=27); return 0; } void Przesiewanie(int l,int p,int* A) { int i,j; int x; int b; x=A[l]; i=l; j=2*i+1; b=1; while(j<=p&&b==1) { if(j<p&&A[j]<A[j+1]) j++; if(x<A[j]) { A[i]=A[j]; i=j; j=2*i+1; } else { b=0; } } A[i]=x; } void BudujStog(int n,int* A) { int i; for(i=(n−2)/2;i>=0;i−−) Przesiewanie(i,n−1,A); } void SortowanieStogowe(int n,int * A) { BudujStog(n,A); int i; int x; for(i=n−1;i>=1;i−−) { x=A[0]; A[0]=A[i]; A[i]=x; Przesiewanie(0,i−1,A); } }

Metis: To jest za trudne Mariusz Użyłem sortowania bąbelkowego Ale zalezało mi na lepszym sposobie. http://pastebin.com/QU6s2eZM

Benny: Ja w tej wyszukiwarce nic teraz nie potrafię znaleźć

Metis: Bo nie działa

Saizou : w sortowaniu tablic o długości n, nie zejdziemy z złożonością poniżej nlg(n) jeśli sortujemy na zasadzie porównań, w innych przypadkach nie wiem

Mariusz: Wg mnie dla tablic najlepsze jest sortowanie stogowe W przypadku list sortowanie przez scalanie byłoby lepsze bo listy sortujesz ustawiając wskaźniki Jeżeli chcesz aby lista była stale posortowana to musisz przeliczyć czy bardziej ci się opłaca napisanie procedury wstawiającej węzeł w odpowiednie miejsce Jeśli chodzi o sortowanie plików to tutaj też sortowanie przez scalanie będzie dobrym pomysłem Jak się zastanowisz nad implementacją to etap dzielenia można pominąć

Mariusz: Jeśli zależy ci na stabilności to zastanów się czy jesteś gotów poświęcić dodatkową pamięć aby uzyskać złożoność nlogn i czy nie wystarczy ci jakieś sortowanie n² np przez wstawianie

Mariusz: https://matematykaszkolna.pl/forum/333816.html Google prędzej mi znalazło temat Bennego niż forumowa szukajka