algorytm.org

Implementacja w C/C++

Pomoc
Potrzebujesz algorytmu/kodu źródłowego, którego nie znalazłeś(aś) w serwisie?
Zamów algorytm!
Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Sortowanie szybkie (quicksort) - Implementacja w C/C++
Ocena użytkownikóww: *****  / 94
SłabyŚwietny
Nadesłany przez Marian, 20 lutego 2011 11:57
Kod przedstawiony poniżej przedstawia główną część rozwiązania problemu.
Pobierz pełne rozwiązanie.

Jeżeli nie odpowiada Ci sposób formatowania kodu przez autora skorzystaj z pretty printer'a i dostosuj go automatycznie do siebie.

quick_1_c.cpp:
// sortowanie szybkie (quicksort)
// www.algorytm.org

#include<iostream>
using namespace std;

int partition(int tablica[], int p, int r) // dzielimy tablice na dwie czesci, w pierwszej wszystkie liczby sa mniejsze badz rowne x, w drugiej wieksze lub rowne od x
{
	int x = tablica[p]; // obieramy x 
	int i = p, j = r, w; // i, j - indeksy w tabeli
	while (true) // petla nieskonczona - wychodzimy z niej tylko przez return j
	{
		while (tablica[j] > x) // dopoki elementy sa wieksze od x 
			j--;
		while (tablica[i] < x) // dopoki elementy sa mniejsze od x
			i++;
		if (i < j) // zamieniamy miejscami gdy i < j
		{
			w = tablica[i];
			tablica[i] = tablica[j];
			tablica[j] = w;
			i++;
			j--;
		}
		else // gdy i >= j zwracamy j jako punkt podzialu tablicy
			return j;
	}
}

void quicksort(int tablica[], int p, int r) // sortowanie szybkie
{
	int q;
	if (p < r) 
	{	
		q = partition(tablica,p,r); // dzielimy tablice na dwie czesci; q oznacza punkt podzialu
		quicksort(tablica, p, q); // wywolujemy rekurencyjnie quicksort dla pierwszej czesci tablicy
		quicksort(tablica, q+1, r); // wywolujemy rekurencyjnie quicksort dla drugiej czesci tablicy
	}
}

int main()
{
	int ilosc_liczb, i;
	cout << "Podaj ilosc licz do posortowania: ";
	cin >> ilosc_liczb;
	int *tablica = new int [ilosc_liczb]; // utworzenie dynamicznej tablicy na 'ilosc_liczb' elementow

	for (i = 0; i < ilosc_liczb; i++) // wczytywanie liczb do tablicy
	{
		cout << "Podaj liczba: ";
		cin >> tablica[i];
	}

	quicksort(tablica,0,ilosc_liczb-1); // wywolanie funkcji sortujacej

	for (i = 0; i < ilosc_liczb; i++) // wypisanie posortowanej tablicy
		cout << "tablica[" << i << "] = " << tablica[i] << endl;

	delete [] tablica; // zwolnienie tablicy zaalokowanej dynamicznie

    return 0;
}
Komentarze
photo
+5 # MartaStelm 2012-12-03 00:03
Bardzo dobry i przejrzysty :)
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
+8 # Marysia 2013-03-24 19:56
Potwierdzam. Bardzo dobrze opisany, wszystko można zrozumieć. Jasny i przejrzysty. Oby więcej takich. Dzięki dla autora.
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
0 # Michał111111 2013-04-06 15:12
Polecam, czytelnie i zrozumiale, za duzo kodu tez nie ma takze wszystko git
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
+1 # ThreeXe 2013-05-17 17:06
Nareszcie, (po wielu próbach) zrozumiałem quicksorta, polecam!
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
0 # Bart 2014-01-05 12:59
Bardzo ładny i czytelny algorytm. Mam pytanie, czy można go w prosty sposób przekształcić aby sortował zmienne typu double?
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
0 # Winter 2015-04-10 00:53
Tak wystarczy użyć szablonu czyli zamiast
int funkcja(int tablica[]){}

zapiszesz

template
int funkcja(T tablica[]){}
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-5 # Niurop 2015-04-12 21:48
Wystarczy zmienić rodzaj danych tablicy,x i w na double, powinno działać ;)
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-2 # Mariusz P. 2015-10-12 14:31
Coś jest nie tak z tym algorytmem gdyż - patrz funkcja partition:
jeśli i == p (a tam jest takie przypisanie) to znaczy, że tablica == tablica[p] == x, a z tego wynika, że poniższa pętla nigdy nie zostanie wywołana:
while (tablica
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-5 # Tomasz Lubiński 2015-10-13 09:01
Zwróć uwagę, że te pętle są wewnątrz większej pętli. Przy pierwszej iteracji faktycznie pierwsza pętla zagnieżdżona nigdy nie zostanie wywołana, ale przy kolejnej już niekoniecznie.
Odpowiedz | Odpowiedz z cytatem | Cytować
Dodaj komentarz