Logo filler
Skip Navigation Links
Αρχική σελίδα
EXAMSExpand EXAMS
ΕκπαίδευσηExpand Εκπαίδευση
Ποιοι είμαστε
Σύνδεσμοι
Επικοινωνία

Αλγόριθμοι ταξινόμησης και αναζήτησης

 

  • Quicksort.
  • Mergesort.
  • Bucketsort.
  • Insertionsort.

Υλοποίηση σε C των περισσότερο χρησιμοποιούμενων αλγορίθμων ταξινόμησης.

Ο Quicksort χρειάζεται κατά μέσο όρο O(nlogn) συγκρίσεις και στην χειρότερη περίπτωση O(n^2).

Ο Mergesort χρειάζεται O(nlogn) (σχεδόν βέλτιστος).

Ο Bucketsort χρειάζεται O(nlog(n/k), όπου k είναι το μέγεθος του κάδου.

Ο Insertionsort χρειάζεται O(n^2) συγκρίσεις.

Εφαρμογή επίδειξης της λειτουργίας των αλγορίθμων. Σαν είσοδο μπορεί να λάβει είτε ένα αρχείο που τα δεδομένα (αριθμοί κινητής υποδιαστολής) διαχωρίζονται με ; ή με κενό, είτε τα δεδομένα να δίνονται από το πληκτρολόγιο.
Η ταξινομημένη έξοδος αποθηκεύεται στο αρχείο out.srt.

Το πακέτο περιλαμβάνει τα ακόλουθα αρχεία:

algosort.cpp - Το κύριο αρχείο (οι υλοποιήσεις των αλγορίθμων).
algoutil.cpp - Μια συλλογή από βοηθητικές συναρτήσεις που χρησιμοποιούνται από τους αλγορίθμους.
algorithms.h - Δηλώσεις των συναρτήσεων / δομών.
reverse.cpp - Ένα δεύτερο βοηθητικό πρόγραμμα που αντιστρέφει τα στοιχεία ενός αρχείου (κατάλληλο για την παραγωγή εισόδων χειρότερης περίπτωσης στους αλγορίθμους).
algosort.exe - Windows binary.
reverse.exe - Windows binary.

Download Algosort.

  • Binary search.
  • Interpolation search (με εκθετικά και δυαδικά βήματα).
 Υλοποίηση σε C των πιο χρησιμοποιούμενων αλγορίθμων αναζήτησης.

Το Binary search κάνει στην χειρότερη περίπτωση O(log(n)) συγκρίσεις.

Το Interpolation search (με εκθετικά και δυαδικά βήματα) χρειάζεται O(loglog(n)) συγκρίσεις στην μέση περίπτωση και O(log(n)) στην χειρότερη.

Εφαρμογή επίδειξης των αλγορίθμων που επιτρέπει στον χρήστη να πειραματιστεί με τους αλγορίθμους της του binary search και του interpolation search. Σαν είσοδος μπορεί να δοθεί είτε ένα διαταγμένο αρχείο με αριθμούς που διαχωρίζονται με , ή με κενό, ή να δημιουργήσει το ίδιο το πρόγραμμα μια τυχαία είσοδο από τυχαίους αριθμούς σε διάταξη. Χρησιμοποιώντας έναν από τους αλγορίθμους μπορείται να βρείτε ένα στοιχείο στη λίστα.

Το πακέτο περιλαμβάνει τα ακόλουθα αρχεία: algosearch.cpp - Το κύριο αρχείο (οι υλοποιήσεις των αλγορίθμων).
algoutil.cpp - Μια συλλογή από βοηθητικές συναρτήσεις που χρησιμοποιούνται από τους αλγορίθμους.
algorithms.h - Δηλώσεις των συναρτήσεων / δομών.
algosearch.exe - Windows binary.

Download Algosearch.

  • Linear median algorithm.
Ο γραμμικός median αλγόριθμός μπορεί να βρει το ι-οστό μικρότερο στοιχεό σε ένα διάνυσμα κάνοντας μόνο Ο(n) συγκρίσεις.

Εφαρμογή για τον πειραματισμό του γραμμικού median αλγορίθμου. Ο χρήστης μπορεί να τροφοδοτήσει την είσοδο είτε με αρχείο δεδομένων ή να αφήσει το πρόγραμμα να δημιουργήσει τυχαία δεδομένα εισόδου. Δίνοντας το ι-οστό μικρότερο στοιχείο προς αναζήτηση (αρχίζοντας να μετράμε από το 1), το πρόγραμμα επιστρέφει το στοιχείο (αν υπάρχει).

Το πακέτο περιλαμβάνει τα ακόλουθα αρχεία:
select.cpp - Το κύριο αρχείο (η υλοποίηση του αλγορίθμου).
algoutil.cpp - Μια συλλογή από βοηθητικές συναρτήσεις που χρησιμοποιούνται από τους αλγορίθμους.
algorithms.h - Δηλώσεις των συναρτήσεων / δομών.
select.exe - Windows binary.

Download Select.

 

Δομές δεδομένων

 

  • BB[a] tree.

Το ΒΒ[a] δένδρο είναι ένα βαροζυγισμένο δένδρο. Χρησιμοποιώντας την παράμετρο a μπορούμε να ρυθμίσουμε τη ζύγιση του δένδρου.

Το ΒΒ[a], είναι το μόνο δένδρο που έχει την ιδιότητα βάρους: Ένας κόμβος v θα χρειάστει πάλι ζύγιση μόνο μετά από την ένθεση / διαγραφή Ω(|Τv|) κόμβων στο υποδένδρο Tv που τον έχει ρίζα.

Διαδραστική εφαρμογή που επιτρέπει στον χρήση να πειραματιστεί με τις λειτουργίες του BB[a] δένδρου. Η είσοδος μπορεί να τεθεί είτε με το χέρι, είτε ως μια σειρά από τυχαίες ενθέσεις/ διαγραφές.

Το πακέτο περιλαμβάνει τα ακόλουθα αρχεία:
bba.cpp - Το κύριο αρχείο (η υλοποίηση του δένδρου).
algoutil.cpp - Μια συλλογή από βοηθητικές συναρτήσεις που χρησιμοποιούνται από τους αλγορίθμους.
algorithms.h - Δηλώσεις των συναρτήσεων / δομών.
bba.exe - Windows binary.

Download BB[a].

  • Union Find.

Το πρόβλημα του union-find είναι να αναπτυχθεί μια δομή πυ θα υποστηρίζει τις λειτουργίες εύρεσης και ένωσης σε ένα σύνολο συνόλων.

Η συγκεκριμένη υλοποίηση χρησιμοποιεί τον κάνονα weighted-union (βαροζυγισμένη ένωση) με την τεχνική του path compression. Έτσι μια ακολουθία από n-1 ενώσεις και m ερεύσεις στοιχίζει O(m*a(m,n)), όπου a(m,n) είναι η αντίστροφη συνάρητηση του Ackermann's (δηλαδή μια συνάρτηση που αυξάνεται με πάρα πολύ αργό ρυθμό).

Διαδραστική εφαρμογή που υλοποιεί τις λειτουργίες του union find σε ένα σύμπαν συνόλων. Ο χρήστης αρχικά δίνει το σύνολο του σύμπαντος, οπότε και δημιουγούνται τα αντίστοιχα αρχικά μονοσύνολα. Το κάθε σύνολο αναπαρίσταται από ένα κομβοπροσανατολιζόμενο δένδρο. Οι λειτουργίες μπορούν να γίνουν είτε με το χέρι, είτε να επιτραπεί στο πρόγραμμα να εκτελέσει ένα τυχαίο σύνολο από λειτουργίες στα σύνολα.

Το πακέτο περιλαμβάνει τα ακόλουθα αρχεία:

unionfind.cpp - Το κύριο αρχείο (η υλοποίηση του δένδρου).
algoutil.cpp - Μια συλλογή από βοηθητικές συναρτήσεις που χρησιμοποιούνται από τους αλγορίθμους.
algorithms.h - Δηλώσεις των συναρτήσεων / δομών.
unionfind.exe - Windows binary.

Download UnionFind.