Jak wykonać to ćwiczenie? ( matura próbna teoria rozsz )

Question

c) Zaproponuj algorytm zgodny z podaną poniżej specyfikacją (w postaci listy kroków, schematu
blokowego lub w wybranym języku programowania) realizujący nierosnące porządkowanie
ciągu liczbowego.
Wybierz metodę, która stosuje iterację, ale nie wykorzystuje techniki dziel i zwyciężaj.

Specyfikacja
Dane:
n – liczba naturalna większa od 0 równa liczbie elementów tablicy T
T[0..n–1] – n-elementowa tablica jednowymiarowa zawierająca liczby rzeczywiste (ciąg liczb do
posortowania)
Wynik:
T[0..n–1] – posortowana nierosnąco n-elementowa tablica jednowymiarowa zawierająca liczby
rzeczywiste (posortowany nierosnąco ciąg liczb) metodą, która stosuje iterację, ale nie wykorzystuje
techniki dziel i zwyciężaj

.

. (tutaj miejsce na sposób rozwiązania)

.

Podaj nazwę i złożoność czasową wraz z określeniem operacji dominującej zaproponowanej w tym punkcie metody sortowania.
...................................................................................................................................................................
...................................................................................................................................................................
...................................................................................................................................................................

 

Zdaje sobie sprawę, iż pewnie stosunek wkładu pracy i straconego czasu do uzyskania korzyści jest niesatysfakcjonujący, lecz proszę również o wytłumaczenie, ponieważ przygotowuje sie do matury z inf w tym roku i chciałbym wyciągnąć najwięcej punktów jak to tylko możliwe ( celuje głównie w mat, ale inf też myślę, że się przyda ).

 

Z góry dziękuję i pozdrawiam

Answer 1

Wszelkiego rodzaju algorytmy sortujące.  Np przez wstawianie, bąbelkowe, przez wybór. Tak mi się przynajmniej wydaje.

A to już na wikipedii jest wytłumaczone

Answer 2

Jeżeli dobrze rozumiem pierwsze, to masz posortować  pewny zbiór losowych liczb malejąco ?

Skoro nie dziel i zwyciężaj to odpadają mergersort, quick sort i pewnie jeszcze kilka oparte o tą zasadę.

Możesz wykorzystać sortowanie bombelkowe- złożonosć  O(n^2)

 

Jeżeli chodzi o opis to złożoność jak wyżej, operacja dominująca- nie wiem jak to nazwać, ale w każdym razie  sprawdzenie każdego  elementu tablicy i wykonanie na nim operacji zamiany.

Czy o to chodzi? to tylko klucz wie.

Answer 3

może ten program pomoże ci zrozumieć to zadanie 

​#include <iostream>
#include <string>
#include <cstdlib>
#include <ctime>


void uporzadkujTablice(int *table, int tableSize)
{

	bool czyNastapilaZmiana = false;

	for (int i1 = 0; i1 < tableSize; i1++)
	{
		czyNastapilaZmiana = false;
		for (int i2 = 1; i2 < tableSize; i2++)
		{
			if (table[i2 - 1] < table[i2])
			{
				czyNastapilaZmiana = true;
				int tmp = table[i2 - 1];
				table[i2 - 1] = table[i2];
				table[i2] = tmp;
			}

		}

		if (czyNastapilaZmiana == false)
		{
			break;
		}
	}
}

void wypiszTablice(int* table,int tableSize)
{
	for (int i = 0; i < tableSize; i++)
	{
		std::cout << table[i] <<" ";
	}
	std::cout << std::endl;
}

int main()
{
	srand(time(NULL));

	int tableSize = rand() % 50;

	int* table;
	table = new int[tableSize];

	for (int i = 0; i < tableSize;i++)
	{
		table[i] = rand() % 50;
	}

	std::cout << "tablica przed uporzadkowaniem" << std::endl;
	wypiszTablice(table,tableSize);

	uporzadkujTablice(table, tableSize);

	std::cout << "tablica po uporzadkowaniu" << std::endl;
	wypiszTablice(table, tableSize);

	
	std::string smt;
	std::cin>>smt;

	delete table;

	return 0;
}