Sortowanie - jaki to algorytm?

Witam, jestem aspirującym programistą... Wciągnęło mnie to na maksa i z zadaniami/programami jako tako problemów nie mam. Gorzej w momencie kiedy mam spojrzeć na nie od strony analitycznej/teoretycznej... Mianowicie. Napisałem taki sobie oto program, który ma sortować elementy i ku mojej uciesze działa... Cieszy mnie to bardziej, bo sam do tego doszedłem. Tu pojawia się jednak problem. Działa, ale nie potrafię nazwać tego algorytmu. Czy jest to sortowanie bąbelkowe czy przez wstawianie? I jakie są zasadnicze różnice między dwoma powyższymi? Z góry dziękuję za odpowiedź i pozdrawiam. Oto kod:

#include <iostream>
#include <ctime>
#include <conio.h>

using namespace std;

int LOSUJ(int min = 1, int max = 20);
void WYPELNIANIE_TABLICY(int tablica[], int rozmiar);
void WYPIS(int tablica[], int rozmiar);
void SORT(int tablica[], int rozmiar);

int main()
{
	srand(static_cast<int>(time(NULL)));
	int x; //rozmiar tablicy

	int *tablica;

	cout << "Podaj rozmiar tablicy: ";
	cin >> x;

	tablica = new int [x];

	WYPELNIANIE_TABLICY(tablica, x);

	cout << "Wypisywanie obecnej zawartosci tablicy. Wcisnij klawisz" << endl;
	getch();

	WYPIS(tablica, x);

	//Sortowanie
	SORT(tablica, x);

	cout << "Wypisywanie obecnej zawartosci tablicy po sortowaniu. Wcisnij klawisz" << endl;
	getch();
	WYPIS(tablica, x);



	cout << endl;
	delete[] tablica;
	system("pause");
	return 0;
}


int LOSUJ(int min, int max)
{
	return rand() % (max - min + 1) + min;

}

void WYPELNIANIE_TABLICY(int tablica[], int rozmiar)
{
	for(int i = 0; i < rozmiar; i++)
	{
		tablica[i] = LOSUJ();
	}
}
void WYPIS(int tablica[], int rozmiar)
{
	for(int i = 0; i < rozmiar; i++)
	{
		cout << tablica[i] << " ";
	}
}

void SORT(int tablica[], int rozmiar)
{
for(int i =(rozmiar - 2); i >=0; i --)
{
	int j = i;
	int temp;

	for(j; j < (rozmiar-1); j ++)
	{
		if(tablica[j] > tablica[j+1])
		{
			temp = tablica[j] ;
			tablica[j] = tablica[j+1];
			tablica[j+1] = temp;
		}
	}

}

}

To jest sortowanie bąbelkowe. Sortowanie bąbelkowe działa w miejscu, sortowanie przez wstawianie raczej nie(operuje na dodatkowej tablicy) i działa nie przez przestawianie elementów, ale przez wstawianie w odpowiednie miejsca elementów z tablicy źródłowej do tablicy docelowej.

A mógłbym prosić o przerobienie mojej funkcji sortowania na taką, która po uwzględnieniu jako parametr kolejnej tablicy sortuje przez wstawianie? O wiele prościej zrozumieć mi coś kiedy sam widzę jak to działa. I dzięki za odpowiedź

Ehhh dawno nie miałem do czynienia z pisaniem takich rzeczy (od tego jest stl). Z tego co widzę sortowanie przez wstawianie też może działać w miejscu. Tu masz kod w różnych językach(Ciebie zainteresuje ten w C): http://pl.wikisource.org/wiki/Sortowanie_przez_wstawianie/kod

No właśnie też zauważyłem, że może działać w miejscu.. Kupiłem ostatnio książkę, traktującą stricte o algorytmach i tam właśnie widziałem przykład ilustrujący działanie sortowania przez wstawianie tylko i wyłącznie na jednej tablicy. Algorytm ten był jednak dziwnie skonstruowany i ciężko było mi pojąć jego działanie. Dlatego chciałbym zobaczyć jak to działa na przykładzie, najlepiej z użyciem pętli for właśnie.

Od strony praktycznej sporo działałem, wymyślałem sobie łatwiejsze bądź trudniejsze zadania i starałem się podejść do nich od jak najbardziej optymalnej i efektywnej strony... Ale teoria u mnie kuleje, głównie dlatego że bardzo mało czasu dotąd jej poświęcałem. Chciałbym jednak zrozumieć, na chwilę obecną, przynajmniej algorytmy sortowania, powinno ułatwić mi to jakiekolwiek działania w przyszłości :D

to ładnie, że wciągnęło cie programowanie :] Ładniej by jeszcze było gdybyś wyrobił sobie nawyk odpytywania najpierw internetu, a następnie dopiero (i ostatecznie) ludzi na forum. Chodzi mi głównie o drugą prośbę, a nie sam temat

Patryk1992bdg napisał(a)

A mógłbym prosić o przerobienie mojej funkcji sortowania na taką, która po uwzględnieniu jako parametr kolejnej tablicy sortuje przez wstawianie?ź
Dlaczego ktoś za ciebie ma korzystać z google'a skoro sam możesz to zrobić?
Niech ci będzie... czepiam się :)

Fakt, z tymże ja wolę mieć wszystko w jednym miejscu i o wiele wygodniej byłoby mi zobaczyć drobną modyfikację w moim przykładzie, najlepiej z pętlą for i koniecznie z działaniem na dwóch tablicach aby zrozumieć różnice pomiędzy poprzednią wersją a obecną. W internecie owszem, znalazłem kilka gotowych rozwiązań w C++, ale albo jestem dzisiaj przyćmiony, albo żadne z tych rozwiązań nie rozwiało moich wątpliwości dotyczących różnic pomiędzy tymi dwoma algorytmami sortowania :P

To nawet nie musi być kod, po prostu chcę zrozumieć tą różnicę. Jeżeli ktoś ma zdolności dydaktyczne i wyjaśni mi to bez zobrazowania jakimkolwiek przykładem, to również będę bardzo wdzięczny.

PS2. Przerobiłem funkcję, aby korzystała z nieszczęsnego algorytmu sortowania przez wstawianie. Nadal jednak działa ona tylko na jednej tablicy....

 

void SORT(int tablica[], int rozmiar)
{

   int temp;
    int i;
    int j;
 
    for (i = 1; i < rozmiar; ++i) 
	{
       temp= tablica[i];
 
        for (j = i - 1; j >= 0 && tablica[j] > temp; --j) 
		{
            tablica[j + 1] = tablica[j];
        }
 
        tablica[j + 1] = temp;
    }
}

No bez kitu, ale wszystkie podstawowe typy sortowania są w jednym miejscu, na wikisources.

Co zaglądam do newbie to jestem coraz bardziej wdzięczny, że zaczynałem zabawę z programowaniem, kiedy nie wiedziałem, że istnieje coś takiego jak internet. Siedziało się nad jakimś(nawet błahym) problemem kilka godzin, szło spać, wstawało i takie Aha! w głowie i rozwiązanie jest. Jak można się nauczyć rozwiązywania problemów skoro tylko się wyszukuje gotowe rozwiązania, czy leci na forum z tekstem pokażcie mi, wytłumaczcie mi?
Chyba jednak nie o to chodzi w tej dziedzinie... Potem dostaniesz za zadanie zrobić coś trochę inaczej, coś zmodyfikować i powiesz wykładowcy/pracodawcy "zapytam na forum"?

Argument, że najlepiej się komuś uczy na przykładach też jest do niczego. Bo co? Nauczysz się na pamięć jakiegoś algorytmu? Jak przyjdzie Ci coś wymyślić, zmienić, poprawić to się wyłożysz...

Gdybym liczył na gotowe rozwiązania, to bym się zadowolił Twoim linkiem z gotowym kodem. Problem był. I był on następujący: posortować elementy. Sam doszedłem do tego w jaki sposób i udało mi się. Więc problem rozwiązałem. Wiem jednak, że są też alternatywy jego rozwiązania i na podstawie porównania dwóch metod chcę wyłuskać najlepsze cechy obu, aby wiedzieć którą stosować. Ale żeby tak postąpić, muszę w pełni zrozumieć metodę przez wstawianie, a gotowe kody mi tu nie pomogą. Rozumiem intuicyjnie na czym ona polega, jak działa, ale jakoś nie mogę sobie tego przełożyć na implementację kodu.

Powiem tak: ja byłem przekonany, że moja metoda, zaprezentowana w pierwszym poście jest właśnie według algorytmu sortowania przez wstawianie. Bo przecież, działając na jednej tablicy, nie da się "wstawić" czegoś, bez naruszania struktury już wpisanych danych, więc naturalna była dla mnie zamiana miejscami pól. Ale jeżeli jest to sortowanie bąbelkowe, to nadal nie wiem jak działa algorytm ze wstawianiem...

http://www.sorting-algorithms.com/

Dzięki, trochę mi to rozjaśniło ;)

Patryk1992bdg napisał(a)

Gdybym liczył na gotowe rozwiązania, to bym się zadowolił Twoim linkiem z gotowym kodem. Problem był. I był on następujący: posortować elementy. Sam doszedłem do tego w jaki sposób i udało mi się. Więc problem rozwiązałem. Wiem jednak, że są też alternatywy jego rozwiązania i na podstawie porównania dwóch metod chcę wyłuskać najlepsze cechy obu, aby wiedzieć którą stosować. (ciach)

Sortowanie bąbelkowe jest najłatwiejsze do zrozumienia i... najwolniejsze.
W realnym świecie nikt tego nie stosuje.

Inną skrajnością jest shellsort - wydajny, łatwy do zakodowania ale wyjątkowo trudny w analizie:
http://cppgm.blogspot.com/2008/02/shell-sort.html
http://en.wikipedia.org/wiki/Shell_sort

(działa w miejscu)

Tu jeszcze trochę do poczytania na temat algorytmów sortowania: http://edu.i-lo.tarnow.pl/inf/alg/003_sort/index.php

Dzięki wielkie, teraz wszystkie te algorytmy stały się dla mnie jasne! :) Najbardziej przydatny okazał się dla mnie post wyżej, ale pozostałym również dziękuję za mniejszą bądź większą pomoc :) Pozdrawiam.

Tak dla formalności pochwalę się jeszcze napisanym kodem, z funkcją zarówno sortującą bąbelkowo jak i przez wstawianie ;)

//Dwie funkcje sortujące - jedna bąbalkowo, druga przez wstawianie

#include <iostream>
#include <conio.h>
#include <ctime>

using namespace std;

int x, odpowiedz;

void POKAZ(int tablica[], int rozmiar = x);
int LOSUJ(int min = 1, int max = 100);
void WPISZ(int tablica[], int rozmiar =x );
void SORTOWANIE_BABELKOWE_MALEJACO(int tablica[], int rozmiar = x);
void SORTOWANIE_BABELKOWE_ROSNACO(int tablica[], int rozmiar = x);
void SORTOWANIE_PRZEZ_WSTAWIANIE_MALEJACO(int tablica[], int rozmiar = x);
void SORTOWANIE_PRZEZ_WSTAWIANIE_ROSNACO(int tablica[], int rozmiar = x);

enum SORTOWANIE
{
	BABELKOWE, PRZEZ_WSTAWIANIE

};
enum KOLEJNOSC
{
	ROSNACO, MALEJACO
};


int main()
{
	KOLEJNOSC decyzja;
	SORTOWANIE decyzja2;

	srand(static_cast<unsigned>(time(NULL)));

	//Ustalanie rozmiaru tablicy
	cout << "Podaj ilosc liczb ktore mam wylosowac: " << endl;
	cin >> x;

	//Zdefiniowanie tablicy o okreslonym rozmiarze
	int *tablica;
	tablica = new int[x];

	//Wylosowanie liczb i wpisanie ich do tablicy
	cout << "Teraz wylosujemy liczby i wyswietlimy je na ekranie. Wcisnij dowolny klawisz" << endl;
	getch();
	WPISZ(tablica);
	POKAZ(tablica);
	cout << endl;

	//Wybór metody sortowania i kolejności elementów
	do{
		cout << "Wybierz kolejnosc wedlug ktorej mam posortowac:\n1. Rosnaco\n2. Malejaco" << endl;
		cin >> odpowiedz;
	}while((odpowiedz!=1) && (odpowiedz != 2));

	if(odpowiedz == 1) decyzja = ROSNACO;
	else decyzja = MALEJACO;
	
	cout << endl;

	do{
		cout << "Wybierz typ algorytmu sortowania ktore chcesz zastosowac:\n1. Babelkowe \n2. Przez wstawianie" << endl;
		cin >> odpowiedz;
	}while((odpowiedz!=1) && (odpowiedz != 2));

	if(odpowiedz == 1) decyzja2 = BABELKOWE;
	else decyzja2 = PRZEZ_WSTAWIANIE;


	switch(decyzja)
	{
		case ROSNACO:
		switch(decyzja2)
		{
			case BABELKOWE:
			SORTOWANIE_BABELKOWE_ROSNACO(tablica);
			break;
				

			case PRZEZ_WSTAWIANIE:
			SORTOWANIE_PRZEZ_WSTAWIANIE_ROSNACO(tablica);	
			break;

		}
		break;


		case MALEJACO:
		switch(decyzja2)
		{
			case BABELKOWE:
			SORTOWANIE_BABELKOWE_MALEJACO(tablica);
			break;

			case PRZEZ_WSTAWIANIE:
			SORTOWANIE_PRZEZ_WSTAWIANIE_MALEJACO(tablica);
			break;
		}
		break;


	}

	//Wyświetlenie wyników pracy programu

	cout << "Teraz wyswietlimy liczby posortowane " << endl;
	getch();
	POKAZ(tablica);



	cout << endl;
	delete[] tablica;
	system("pause");
	return 0;
}
void POKAZ(int tablica[], int rozmiar)
{
	for(int i = 0; i < rozmiar; i++)
	{
		cout << tablica[i] << " ";
	}
}

int LOSUJ(int min, int max)
{
	return rand() % (max - min + 1) + min;
}

void WPISZ(int tablica[], int rozmiar)
{
	for(int i = 0; i < rozmiar; i ++)
	{
		tablica[i] = LOSUJ();
	}
}


/***************Sortowanie bąbelkowe*********************************/
void SORTOWANIE_BABELKOWE_ROSNACO(int tablica[], int rozmiar)
{
	for(int i = 1; i < rozmiar; i ++)
	{
		for(int j = i; j > 0; j --)
		{
			if(tablica[j] < tablica[j-1])
			{
				int temp = tablica[j];
				tablica[j] = tablica[j-1];
				tablica[j-1] = temp;
			}
		}

	}

}


void SORTOWANIE_BABELKOWE_MALEJACO(int tablica[], int rozmiar)
{
	for(int i = 1; i < rozmiar; i ++)
	{
		for(int j = i; j > 0; j --)
		{
			if(tablica[j] > tablica[j-1])
			{
				int temp = tablica[j];
				tablica[j] = tablica[j-1];
				tablica[j-1] = temp;
			}
		}

	}

}

//*******************************************************************

/***************Sortowanie przez wstawianie*********************************/
                                                                           
void SORTOWANIE_PRZEZ_WSTAWIANIE_ROSNACO(int tablica[], int rozmiar)		   
{
	for(int i = 1; i < rozmiar; i++)
	{
		int element = tablica[i];
		int j = i - 1;
		while((j>=0) && (element < tablica[j]))
		{
			tablica[j+1] = tablica[j];
			j--;
		}
		tablica[j+1] = element;


	}


}

void SORTOWANIE_PRZEZ_WSTAWIANIE_MALEJACO(int tablica[], int rozmiar)		   
{
	for(int i = 1; i < rozmiar; i++)
	{
		int element = tablica[i];
		int j = i - 1;
		while((j>=0) && (element > tablica[j]))
		{
			tablica[j+1] = tablica[j];
			j--;
		}
		tablica[j+1] = element;


	}


}
//*************************************************************************