Ταξινόμηση πίνακα σε Pascal

Συζητήσεις σχετικές με την Delphi και την πρόγονη της Pascal

Συντονιστές: WebDev Moderators, Super-Moderators

Απάντηση
Άβαταρ μέλους
deninho
Super Moderator
Δημοσιεύσεις: 7066
Εγγραφή: 17 Ιαν 2004 16:01
Τοποθεσία: σ'άλλη διάσταση
Επικοινωνία:

Ταξινόμηση πίνακα σε Pascal

Δημοσίευση από deninho » 28 Μάιος 2009 16:01

Το λεπόν...

Έχουμε μια άσκηση, προς παράδοση στη σχολή. Το θέμα:
Έχεις ένα πίνακα με ταξινομημένα τα δυο μισά του από το μικρότερο στο μεγαλύτερο και τα συγχωνεύεις σε έναν ολόκληρο ταξινομημένο πίνακα
Υπόδειξη από συμφοιτητή
Χρησιμοποιούμε και τη ρουτίνα mergesort αναλόγως με πριν.
Το πριν:
Heap: είναι πίνακας, ο οποίος στο μυαλό μας έχει μορφή δυαδικού δέντρου και ισχύει η σχέση A[parent]>=A (η τιμή κάθε στοιχείου είναι το πολύ ίση με την τιμή του γονικού στοιχείου). Αυτη η συνθήκη διασφαλίζεται από τη ρουτίνα HEAPIFY, που ξεκινά από κάποιο στοιχείο και το μετατρέπει σε heap ώστε να ικανοποιείται η παραπάνω συνθήκη. Η ρουτίνα BUILD_HEAP βρίσκει τη μέση του heap και εξετάζει αν τα στοιχεία κάτω από αυτό ικανοποιούν τη συνθήκη, αλλιώς κάνει HEAPIFY. Αν συμβαίνει, τοτε προχωρά με τον αμέσως μικρότερο κόμβο μέχρι να φτάσει στη ρίζα, όπου τερματίζεται η ρουτίνα.
Η HEAPSORT βρίσκει το τελευταίο στοιχείο και το ανταλλάσσει με τη ρίζα μέχρι να τάσει στην τελευταία προκύπτουσα ρίζα. Κάθε φορά μειώνει κατά 1 το μεγεθος του πίνακα που προκυπτει.


Ο κώδικας, όπως τον έβγαλα:


Κώδικας: Επιλογή όλων

program taksinomisi (input, output);
Var
Pinakas, F:Array[1..15] of integer;
metritis:integer;
con:char;

procedure merge (var A, B: array of integer; x, m, y: integer);
var e, i, stoixeia, k: integer;

begin
	i:=m-1;
	k:=x;
	stoixeia:=y-x+1;
	while &#40;x<=i&#41; and &#40;m<=y&#41; do
		if &#40;a&#91;x&#93;<=a&#91;m&#93;&#41; then
			begin
				B&#91;k&#93;&#58;=A&#91;x&#93;;
				k&#58;=k+1;
				x&#58;=x+1;
			end
		else
			begin
				B&#91;k&#93;&#58;=A&#91;m&#93;;
				k&#58;=k+1;
				m&#58;=m+1;
		end;
		while x<=i do
			begin
			B&#91;k&#93;&#58;=A&#91;x&#93;;
			x&#58;=x+1;
			k&#58;=k+1;
		end;
		while m<=y do
			begin
				B&#91;k&#93;&#58;=A&#91;m&#93;;
				m&#58;=m+1;
				k&#58;=k+1;
		end;
	for e&#58;=1 to stoixeia do
		begin
			A&#91;y&#93;&#58;=B&#91;y&#93;;
			write&#40;A&#91;y&#93;, ' '&#41;;
			y&#58;=y-1;
		end;
	writeln&#40;&#41;;
	readln&#40;&#41;;
end;

Procedure mergesort &#40;var Pin, C&#58; array of integer; x,y&#58;integer&#41;;
Var n&#58; integer;

begin
	if x<y then
		begin
			n&#58;=&#40;x+y&#41;div 2;
			mergesort&#40;Pin, C, x, n&#41;;
			mergesort&#40;Pin, C, n+1, y&#41;;
			merge&#40;Pin, C, x, n+1, y&#41;;
		end;
end;

Begin
	writeln&#40;'Merge'&#41;;
	writeln;
	For metritis&#58;=1 to 15 do
		begin
			writeln &#40;'Please enter the ', metritis,'th value'&#41;;
			readln &#40;Pinakas&#91;metritis&#93;&#41;;
		end;
	con&#58;=&#40;'*'&#41;;
	while &#40;con<>'q'&#41; do
		begin
			writeln&#40;'press q to exit program, m to sort the table, or p to print'&#41;;
			readln&#40;con&#41;;
			If con='m' then
				mergesort&#40;pinakas,F,1,15&#41;;
			If con='p' then
				for metritis&#58;=1 to 15 do
					writeln&#40;pinakas&#91;metritis&#93;&#41;;
			end
end.
Το ερώτημα: Είναι σωστό, με βάση αυτά που ζητάει ο καθηγητής;

Απάντηση

Επιστροφή στο “Delphi, Pascal”

Μέλη σε σύνδεση

Μέλη σε αυτήν τη Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 0 επισκέπτες