Παμε πάλι τον αλγόριθμο.
Έχουμε τον πίνακα Α[Μ,Ν] και θέλουμε τα κ μικρότερα στοιχεία του.
1)Δημιουργουμε 2 μονοδιαστατους πίνακες τον ΘΕΣΗ και τον ΜΙΝ και οι 2 μεγέθους Μ.
2)Στον πίνακα ΘΕΣΗ στην θέση ΘΕΣΗ[ i ]<--i , για κάθε i
3)Στον πίνακα ΜΙΝ στην θέση ΜΙΝ[ i ]<--το μικρότερο στοιχείο της γραμμής i
4)Ταξινόμησε τον πίνακα ΜΙΝ και παράλληλα εναλλασε και τις θέσεις στον πίνακα ΘΕΣΗ. (Έτσι στο τέλος θα έχουμε στον πίνακα ΘΕΣΗ στις κ πρώτες γραμμες του,τις γραμμές εκείνες που θα έχουν σίγουρα τα κ μικρότερα στοιχεία).
5)Στην συνέχεια ταξινομούμε τις κ γραμμες που αναφέρονται στις κ πρώτες θέσεις του πίνακα, αλλά ταξινομόντας μόνο τα κ μικρότερα στοιχεία τους.
6)Βάζω στον πίνακα ΜΙΝ στις κ πρώτες θέσεις του (οσες και οι γραμμές) 1 (κάθε θέση αυτού του πίνακα κοιτάει στην αντιστοιχη στηλη της γραμμής που βρίσκεται στον ΘΕΣΗ[ i ] και στην αρχη ολοι κοιταν στο μικροτερο στοιχειο της γραμμης τους αφου ειναι ταξινομημένος ανα γραμμή αρα στο 1ο)
7)Συγκρίνεις ΜΟΝΟ τα στοιχεία που σου "δειχνει" ο πινακας Β.
Αλγόριθμος ΤαξινομησηΔισδιάστατου
Δεδομένα // A,Μ,Ν,κ //
! Βήμα 2,3
Για i απο 1 μέχρι Μ
ΘΕΣΗ[ i ]<--i
tmin<--A[i,1]
Για j απο 2 μέχρι Ν
Αν tmin>Α[i,j] τοτε
tmin<--Α[i,j]
Τέλος_Αν
MIN[ i ]<--tmin
Τέλος_επανάληψης
!Βήμα 4
Για i απο 2 μέχρι κ+1
Για j απο Μ μέχρι i με_βήμα -1
Αν ΜΙΝ[ j ]<MIN[ j-1 ] τοτε
Αντιμετάθεσε ΜΙΝ[ j ],MIN[ j-1 ]
Αντιμετάθεσε ΘΕΣΗ[ j ],ΘΕΣΗ[ j-1]
Τέλος_Αν
Τέλος_Επανάληψης
Τέλος_Επανάληψης
!Βήμα 5
Για γρ απο 1 μέχρι κ !το σε ποια γραμμή είμαι το βλέπω απο το ΘΕΣΗ[γρ]
Για i απο 2 μέχρι κ+1 !Πόσες επαναλήψης χρειάζομαι ανα γραμμή
Για j απο Ν μέχρι i με_βήμα -1 !Η στήλη που βρίσκομαι αυτήν την στιγμή
Αν Α[ΘΕΣΗ[ γρ ],j ]<Α[ΘΕΣΗ[ γρ ],j-1 ] τοτε
Αντιμετάθεσε Α[ΘΕΣΗ[ γρ ],j ],Α[ΘΕΣΗ[ γρ ],j-1 ]
Τέλος_Αν
Τέλος_Επανάληψης
Τέλος_Επανάληψης
Τέλος_Επανάληψης
!Βήμα 6
Για i απο 1 μέχρι κ
ΜΙΝ[ i ]<--1
Τέλος_επανάληψης
!Βήμα 7
!Τωρα χρησιμοποιούμε απλά τις κ πρώτες θέσεις του ΜΙΝ για να μας δείχνουν την στήλη που βρισκόμαστε στην γραμμή i
Για i απο 1 μεχρι κ ! όσα νουμερα θέλουμε να εμφανίσει Απαραιτητα <Ν αλλιώς υπαρχει λογικό σφάλμα...
tmin<-- Α[Θεση[ 1 ], MIN[ 1 ]]
γρ<--1 ! Η γραμμή που βρήκαμε το μικρότερο στοιχείο
Για j απο 2 μεχρι κ
Αν tmin>Α[Θέση[ j ],ΜΙΝ[ j ] ] τοτε
tmin<--Α[Θέση[ j ],ΜΙΝ[ j ] ]
γρ<-- j
Τέλος_Αν
Τέλος_επανάληψης
Εμφάνισε Α[ΘΕΣΗ[γρ],MIN[ γρ ]]
MIN[γρ]<--MIN[γρ]+1
Τέλος_επανάληψης
Τέλος_αλγόριθμος
Πολυπλοκότητα:
Βημα 2,3: Μ*Ν
Βημα 4: Μ*κ
Βημα 5: κ^2 * Ν
Βήμα 6: κ
Βήμα 7: κ^2
Συνολικά: Ο(Μ*Ν+Μ*κ+κ^2*Ν+κ+κ^2) και επειδή κ<=Ν και κ<=Μ έχουμε
Ο(Μ*Ν+Ν*κ^2)=Ο(Ν*(Μ+κ^2)) το οποίο είναι καλύτερο από το Ο(Μ*Ν*κ) που δίνει ο απλός αλγόριθμος.
Ουφφφφφφ