Ταξινόμηση (sorting) στην java

Ταξινόμηση (sorting)

Όλοι οι αλγόριθμοι ταξινόμησης βασίζονται σε δύο θεμελιώδεις λειτουργίες:

• τη σύγκριση και
• τη μετακίνηση (swapping).

Η σύγκριση είναι απλή. Το swapping είναι λίγο πιο πολύπλοκο. Θεωρείστε το ακόλουθο πρόβλημα. Θέλουμε να μεταφέρουμε την τιμή από το a στο b. Οι πιο πολλοί θα πρότειναν μια λύση σαν την ακόλουθη:

class Swap1 {
  public static void main(String args[]) {
    int a = 1;
    int b = 2;

    System.out.println("a = "+a);
    System.out.println("b = "+b);

    // αντάλλαξε (swap) a και b
    a = b;
    b = a;

    System.out.println("a = "+a);
    System.out.println("b = "+b);
 }
}

Αυτή θα δημιουργούσε την παρακάτω έξοδο:
a = 1
b = 2
a = 2
b = 2

Δεν περιμέναμε όμως αυτό! Το πρόβλημα είναι ότι χάσαμε την τιμή 1 καθώς βάλαμε την τιμή του b στο a. Για να διορθωθεί αυτό πρέπει να εισάγουμε μια τρίτη μεταβλητή, έστω την temp, η οποία θα κρατάει την αρχική τιμή του a.

class Swap2 {
  public static void main(String args[]) {
    int a = 1;
    int b = 2;
    int temp;

    System.out.println("a = "+a);
    System.out.println("b = "+b);
 
    // swap a και b

    temp = a;
    a = b;
    b = temp;

    System.out.println("a = "+a);
    System.out.println("b = "+b);
  }
}

Aυτός ο κώδικας παράγει το αποτέλεσμα που περιμέναμε.
a = 1
b = 2
a = 2
b = 1

Ταξινόμηση: Bubble Sort

Tώρα που είδαμε πώς να μετακινούμε τις τιμές 2 μεταβλητών, ας προχωρήσουμε στην ταξινόμηση. Υπάρχουν πολλοί διαφορετικοί αλγόριθμοι ταξινόμησης.

Ένας από τους πιο απλούς και δημοφιλής αλγόριθμους είναι ο bubble sort.

Η έννοια του bubble sort είναι να ξεκινήσουμε από την κορυφή του πίνακα. Συγκρίνουμε κάθε στοιχείο με το επόμενο στοιχείο. Αν είναι μεγαλύτερο από αυτό τότε τα μεταθέτουμε. Αυτή τη διαδικασία την κάνουμε όσες φορές χρειαστεί. Η μικρότερη τιμή εμφανίζεται στην κορυφή του πίνακα ενώ η μεγαλύτερη στο τέλος.

Ακολουθεί ο κώδικας:

import java.util.*;

class BubbleSort {
  public static void main(String args[]) {
    int[] n;
    n = new int[10];
    Random myRand = new Random();

    // initialize the array
    for (int i = 0; i < 10; i++) {
       n[i] = myRand.nextInt();
    }

    // print the array's initial order
    System.out.println("Before sorting:");
    for (int i = 0; i < 10; i++) {
      System.out.println("n["+i+"] = " + n[i]);
    }

    boolean sorted = false;
    // sort the array
    while (!sorted) {
      sorted = true;
      for (int i=0; i < 9; i++) { 
         if (n[i] > n[i+1]) {
            int temp = n[i];
            n[i] = n[i+1];
            n[i+1] = temp;
            sorted = false;
         }
      }
    }

    // print the sorted array
    System.out.println();
    System.out.println("After sorting:");
    for (int i = 0; i < 10; i++) {
      System.out.println("n["+i+"] = " + n[i]);
    }
  }
}

Σ’ αυτήν την περίπτωση ταξινομήσαμε έναν πίνακα με αύξουσα σειρά. Το μικρότερο στοιχείο μπαίνει πρώτο. Θα ήταν εύκολο να το αλλάξουμε σε ταξινόμηση με φθίνουσα σειρά.