Αναζήτηση και ταξινόμηση

Ταξινόμηση

• Οι αλγόριθμοι ταξινόμησης (sorting algorithms) θέτουν τα στοιχεία μιας δομής δεδομένων σε σειρά σύμφωνα με μια ορισμένη σχέση διάταξης.
• Αν τα στοιχεία είναι οργανωμένα σε εγγραφές και κάθε μια από αυτές απαρτίζεται από πεδία τότε το πεδίο με βάση το οποίο γίνεται η ταξινόμηση ονομάζεται κλειδί (key) της ταξινόμησης.
• Το κόστος μιας ταξινόμησης εκφράζεται ανάλογα με τον αριθμό συγκρίσεων και μετακινήσεων που απαιτούνται κατ' ελάχιστο, μέγιστο και κατά μέσο όρο.
• Συχνά για να αποφευχθεί το κόστος των μετακινήσεων αντί για τα στοιχεία, ταξινομήται ένας πίνακας με δείκτες στα αντίστοιχα στοιχεία.

Ταξινόμηση με παρεμβολή

• Στη ταξινόμηση με παρεμβολή (insertion sort) τα στοιχεία χωρίζονται σε:
  • αυτά τα οποία έχουν ταξινομηθεί,
  • αυτό τα οποία θα ταξινομηθεί, και
  • αυτά τα οποία δεν έχουν ταξινομηθεί.
• Σε κάθε βήμα το στοιχείο που πρέπει να ταξινομηθεί εισάγεται στη σωστή θέση αυτών που έχουν ταξινομηθεί.
• Για την εύρεση του σημείου εισαγωγής μπορεί να χρησιμοποιηθεί και ο αλγόριθμος της δυαδικής αναζήτησης.

Ταξινόμηση με επιλογή

• Στη ταξινόμηση με επιλογή (selection sort) τα στοιχεία χωρίζονται σε:
  • αυτά τα οποία έχουν ταξινομηθεί,
  • αυτά τα οποία δεν έχουν ταξινομηθεί.
• Σε κάθε βήμα επιλέγεται το ελάχιστο στοιχείο από αυτά τα οποία δεν έχουν ταξινομηθεί και εισάγεται στο τέλος των στοιχείων που έχουν ταξινομηθεί.

Ταξινόμηση με αντιμετάθεση

• Στη ταξινόμηση με αντιμετάθεση (exchange sort) τα στοιχεία ταξινομούνται με διαδοχική αντιμετάθεση ζευγών που δεν ακολουθούν τη διάταξη της ταξινόμησης.
• Ο αλγόριθμος μπορεί να βελιτωθεί εναλλάσσοντας σε κάθε πέρασμα τη φορά του ελέγχου.
• Στην πρώτη περίπτωση ονομάζεται bubble sort (ταξινόμηση φυσαλίδας), στη δεύτερη shake sort.

Ταξινόμηση με διαμερισμό και αντιμετάθεση

• Στην ταξινόμηση με διαμερισμό (partition exchange sort) (ή γρήγορη ταξινόμηση (quick sort)) επιλέγεται ένα στοιχείο του πίνακα και τα υπόλοιπα στοιχεία μοιράζονται σε δύο υποπίνακες ανάλογα με τη σχέση τους με το στοιχείο αυτό.
• Στη συνέχεια ο αλγόριθμος καλείται αναδρομικά για τους δύο υποπίνακες.
• Η βιβλιοθήκη της C υλοποιεί τον αλγόριθμο αυτό στη συνάρτηση qsort:

  #include <stdlib.h>
  
  void qsort(void *base, size_t num, size_t width, int (*compare)(const void *elem1, const void *elem2));
  

• Η συνάρτηση ταξινομεί έναν πίνακα δεδομένων με βάση μια συνάρτηση σύγκρισης.
• Η συνάρτηση έχει τις παρακάτω παραμέτρους:

  base

  Δείκτης στην αρχή του πίνακα των δεδομένων που πρέπει να ταξινομηθούν.

  num

  Αριθμός των δεδομένων που πρέπει να ταξινομηθούν.

  width

  Το μέγεθος κάθε στοιχείου του πίνακα (π.χ. sizeof(int), sizeof(struct s_elem *)).

  compare

  Δείκτης σε συνάρτηση που συγκρίνει δύο στοιχεία με βάση δείκτες σε αυτά. Η συνάρτηση compare πρέπει να επιστρέφει τις παρακάτω τιμές:

  < 0

  αν το elem1 < elem2,

  0

  αν το elem1 == elem2 και

  > 0

  αν το elem1 > elem2.

Παράδειγμα

#include <stdlib.h>
#include <stdio.h>

/*
 * Integer compare function (passed to qsort)
 */
static int
icmp(const void *arg1, const void *arg2)
{
	return (*(int *)arg1 - *(int *)arg2);
}

main()
{
	int ivals[] = {100, 5, 6, 2, 8, 3, 45, 23};
	int i;

	qsort((void *)ivals, sizeof(ivals) / sizeof(int), sizeof(int), icmp);
	for (i = 0; i < sizeof(ivals) / sizeof(int); i++)
		printf("%d\n", ivals[i]);
}

Αναζήτηση

• Οι αλγόριθμοι αναζήτησης (searching algorithms) επιτρέπουν την εύρεση ενός στοιχείου σε μια δομή δεδομένων με βάση ένα χαρακτηριστικό του.
• Αν τα στοιχεία είναι οργανωμένα σε εγγραφές και κάθε μια από αυτές απαρτίζεται από πεδία τότε το πεδίο με βάση το οποίο γίνεται η αναζήτηση ονομάζεται κλειδί της αναζήτησης.
• Το κόστος μιας αναζήτησης εκφράζεται ανάλογα με τον αριθμό συγκρίσεων που απαιτούνται κατά μέσο όρο για την εύρεση της αναζητούμενης εγγραφής.

Σειριακή αναζήτηση

• Στη σειριακή αναζήτηση (sequential search) η εύρεση της εγγραφής στη δομή που επιτρέπει τέτοιου είδους πρόσβαση (π.χ. πίνακα ή συνδεδεμένη λίστα) γίνεται ελέγχοντας μια-μια τις εγγραφές από την αρχή μέχρι το τέλος της δομής.
• Αν η δομή έχει Ν στοιχεία θα απαιτηθούν κατά μέσο όρο N / 2 συγκρίσεις.
• Το παρακάτω παράδειγμα αναζητά έναν ακέραιο σε μια συνδεδεμένη λίστα ακεραίων και επιστρέφει δείκτη στη δομή που τον περιέχει ή NULL αν η λίστα δεν περιέχει τον ακέραιο αυτό:

  #include <stdlib.h>
  
  struct s_ilist {
  	int i;
  	struct s_ilist *next;
  };
  
  /*
   * Search for the integer i in the linked list p.
   * Return a pointer to the first element containing the integer
   * if found; NULL if the integer is not in the list.
   */
  struct s_ilist *
  isearch(struct s_ilist *p, int i)
  {
  	for (; p != NULL; p = p->next)
  		if (p->i == i)
  			return (p);
  	return (NULL);
  }
  

Δυαδική αναζήτηση

• Στη δυαδική αναζήτηση (binary search) η εύρεση της εγγραφής στον ταξινομημένο πίνακα γίνεται αναζητώντας το στοιχείο στη μέση του πίνακα, στη συνέχεια στη μέση της μέσης κ.ο.κ.
• Αν ο πίνακας έχει Ν στοιχεία θα απαιτηθούν κατά μέσο όρο log2 N συγκρίσεις.
• Η βιβλιοθήκη της C υλοποιεί τον αλγόριθμο αυτό στη συνάρτηση bsearch:

  #include <stdlib.h>
  
  void *bsearch(const void *key, const void *base, size_t num, size_t width, int (*compare)(const void *elem1, const void *elem2));
  

• Η συνάρτηση αναζητά την τιμή που δείχνεται από το δείκτη key σε έναν ταξινομημένο πίνακα δεδομένων με βάση μια συνάρτηση σύγκρισης.
• Η συνάρτηση έχει τις παρακάτω παραμέτρους:

  key

  Δείκτης στην τιμή για την οποία εκτελείται η αναζήτηση.

  base

  Δείκτης στην αρχή του πίνακα των δεδομένων που θα εκτελεστεί η αναζήτηση.

  num

  Αριθμός των δεδομένων στον πίνακα.

  width

  Το μέγεθος κάθε στοιχείου του πίνακα (π.χ. sizeof(int), sizeof(struct s_elem *)).

  compare

  Δείκτης σε συνάρτηση που συγκρίνει δύο στοιχεία με βάση δείκτες σε αυτά. Η συνάρτηση compare (όπως και αυτή της qsort) πρέπει να επιστρέφει τις παρακάτω τιμές:

  < 0

  αν το elem1 < elem2,

  0

  αν το elem1 == elem2 και

  > 0

  αν το elem1 > elem2.

Παράδειγμα

Hotel
Echo
Lima
Lima
Oscar
Whiskey
Oscar
Romeo
Lima
Delta

/*
 * Read a line from the standard input and print it according to the
 * international phonetic alphabet.
 *
 * Diomidis Spinellis.  March 1999.
 *
 * $Id$
 *
 */

#include <stdlib.h>
#include <stdio.h>

/*
 * The international phonetic alphabet (sorted)
 */
char *names[] = {
	"Alpha",
	"Bravo",
	"Charlie",
	"Delta",
	"Echo",
	"Foxtrot",
	"Golf",
	"Hotel",
	"India",
	"Juliet",
	"Kilo",
	"Lima",
	"Mike",
	"November",
	"Oscar",
	"Papa",
	"Quebec",
	"Romeo",
	"Sierra",
	"Tango",
	"Uniform",
	"Victor",
	"Whiskey",
	"X-Ray",
	"Yankee",
	"Zulu",
};

/*
 * Bsearch compare function
 */
static int
namecmp(char **a, char **b)
{
	return (**a - **b);
}

main()
{
	char buff[80], *p, **name;

	fgets(buff, sizeof(buff), stdin);
	for (p = buff; *p; p++)
		if (name = (char **)bsearch(&p, names, 26, sizeof(char *), namecmp))
			printf("%s\n", *name, *name);
}

Βιβλιογραφία

• Χρήστος Κοίλιας Δομές Δεδομένων και Οργανώσεις Αρχείων. σ. σ. 107-132 Εκδόσεις Νέων Τεχνολογιών, 1993.

• Donald E. Knuth. The Art of Computer Programming, volume 3 / Searching and Sorting. Addison-Wesley, second edition, 1973.

• Niklaus Wirth. Algorithms + Datastructures = Programs. p. 56-134. Prentice-Hall, 1976.

• Sarwar, S. Mansoor, Sarwar, Syed Aqeel, and Brandeburg, Jesse. Engineering Quicksort. Computer Languages, 22(1), 1996.

Ασκήσεις

Άσκηση 6

1. Να υλοποιηθεί σε C πρόγραμμα το οποίο διαβάζει ονόματα και τηλέφωνα μέχρι να συναντήσει το όνομα "ΤΕΛΟΣ". Στη συνέχεια, για κάθε επόμενο όνομα που διαβάζει, τυπώνει το αντίστοιχο τηλέφωνο, ή τη λέξη ΑΓΝΩΣΤΟΣ αν δεν υπάρχει. Το πρόγραμμα να υλοποιηθεί με τη χρήση των qsort και bsearch.

   Παράδειγμα:

   Γιάννης
   031343454
   Φανή
   027354566
   Θανάσης
   014645678
   Αλέξανδρος
   56789
   Γεωργία
   034556789
   ΤΕΛΟΣ
   Σωτήρης
   ΑΓΝΩΣΤΟΣ
   Φανή
   027354566
   

   
   Σημείωση: Η σύγκριση για τη λέξη "ΤΕΛΟΣ" μπορεί να γίνει ως εξής:

   if (strcmp(buff, "END\n") == 0) ...
   

• Περιεχόμενα

 Τελευταία αλλαγή: Τρίτη, 23 Μαρτίου 1999 11:37 μμ
 Εκτός αν αναφέρεται κάτι διαφορετικό, όλο το πρωτότυπο υλικό της σελίδας αυτής του οποίου δημιουργός είναι ο Διομήδης Σπινέλλης παρέχεται σύμφωνα με τους όρους της άδειας «Creative Commons Attribution-Share Alike 3.0 Greece License».