Aktív témák
-
bazs
aktív tag
A probléma a következő
Adott egy n elemű tömb ami 0-tól k-ig rendezett és k+1-től n-1-ig is ezt kéne rendezni n lépésben.
pl
1,5,9,12,3,4,7,8,11,20 -> 1,3,4,5,7,8,9,11,12,20
előre is köszPont most fogyott el...
-
Flashy
veterán
helyben rendezés alatt azt érted hogy semmi segédtömb semmi segédváltozó?
-
-
bazs
aktív tag
Szerintem te még nem érted a feladatot.
1,5,9,12,3,4,7,8,11,20 -> 1,3,4,5,7,8,9,11,12,20
Nézd a példát a kiindulási tömbben 1,5,9,12 rendezett, majd 3,4,7,8,11,20 is rendezett és ezeket kell ''összefésülni'' a feladatban pedig az a poén, hogy O(n) lépésben kell megcsinálni.Pont most fogyott el...
-
bazs
aktív tag
A könyvet én is néztem, de ha ez a feladat alg. elm. órára...
Pont most fogyott el...
-
corm
senior tag
Az O(n)-ben az ''O'' az ordo akar lenni vagy teta?
Y N W A
-
corm
senior tag
akkor teta. vagy nem?(mamint mink igy tanultuk)
:))Y N W A
-
corm
senior tag
amugy ezt hol mondta a tanar?(hova jarsz) :))
Y N W A
-
corm
senior tag
nemis mondtam hogy van :)
Y N W A
-
Terminus_
aktív tag
Ez Perlben van, de elég jól kommentezett.
#!/usr/local/bin/perl
# A test array
@sort_array = (4,7,12,3,15,28,1,3,44,13,18);
# Get the ball rolling
&do_merge_sort(@sort_array, $#sort_array);
#print out the results.
$end_result = join('', '',@sort_array);
print $end_result.'' '';
exit;
sub do_merge_sort {
&merge_sort(shift, 0, shift);
}
# Merge sort expects 3 parameters
# A reference to an array
# A start index of where to start sorting
# An end index of where to stop sorting
sub merge_sort {
my ($array_ref, $start_index, $end_index) = @_;
# Only do merge sort if there's a 1 element or greater sized array. No use for empty arrays.
if ($start_index <; $end_index) {
# Calculate the middle of the array
my $mid_index = int(($start_index + $end_index) / 2);
# Call the merge sort on the left half of the array
&merge_sort($array_ref, $start_index, $mid_index);
# Call merge sort on the right half of the array
&merge_sort($array_ref, $mid_index+1, $end_index);
# Merge these two arrays together since they will be in order by now
&merge($array_ref, $start_index, $end_index);
}
}
sub merge {
my ($array_ref, $start_index, $end_index) = @_;
# calculate the middle of the array
my $right_index = int(($start_index + $end_index) / 2) + 1;
my $max_val = $end_index;
my $left_index = $start_index;
# While we don't exceed the bounds of the merge keep going.
while ($right_index <;= $max_val && $left_index <;= $max_val) {
# If the current item in the right array is bigger than the current
# item in the left array, we need to move the right item to the current
# position in the left array and shift the left array to the right by
# one.
if ($array_ref->;[$right_index] <; $array_ref->;[$left_index]) {
# Store the right index value that needs to be brought to the front
my $tmp = $array_ref->;[$right_index];
# Shift the left array over by 1 to the right to make room for the
# smaller value
for ($i = $right_index; $i >;= $left_index; $i--) {
$array_ref->;[$i] = $array_ref->;[$i-1];
}
# Swap in the value and change where the array indexes are located
$array_ref->;[$left_index] = $tmp;
$left_index++;
$right_index++;
} else {
# If the left item is greater than the right item you don't need to
# do any swapping since it's already keeping the sort order correct
# just make sure that the left index doesn't catch up to the right
# index or you're already done sorting this level!
$left_index++;
if ($left_index >;= $right_index) { return; }
}
}
}
Kár, hogy a struktúráltságát elvesztette :(
[Szerkesztve]-
-
bazs
aktív tag
Köszönöm a segítséget, egy másik fórumon tökéletes megoldást kaptam. Ha valaki gondolja szívesen felrakom ide is.
Pont most fogyott el...
Aktív témák
Állásajánlatok
Cég: Alpha Laptopszerviz Kft.
Város: Pécs
Cég: Ozeki Kft.
Város: Debrecen