Τι Είναι το Counting Sort;

Σκέψου το Counting Sort σαν να προσπαθείς να μετρήσεις πόσα από κάθε είδους μπισκότο έχεις σε μια μεγάλη σακούλα. Για παράδειγμα, έχεις μπισκότα σοκολάτας, μπισκότα βανίλιας και μπισκότα φράουλας. Θέλεις να τα βάλεις σε σειρά, από το λιγότερο στο περισσότερο.

Για να το κάνεις αυτό, δεν χρειάζεται να τα συγκρίνεις το ένα με το άλλο. Αντίθετα, θα μετρήσεις πόσα μπισκότα έχεις από κάθε είδος και θα χρησιμοποιήσεις αυτές τις μετρήσεις για να φτιάξεις μια νέα σειρά.

Πώς Λειτουργεί το Counting Sort;

  1. Μετράμε Κάθε Είδος:
    • Φτιάχνουμε μια λίστα (ή πίνακα) όπου καταγράφουμε πόσα μπισκότα έχουμε από κάθε είδος. Για παράδειγμα, αν έχουμε 3 μπισκότα σοκολάτας, 2 μπισκότα βανίλιας και 1 μπισκότο φράουλας, η λίστα μας θα το δείχνει αυτό.
  2. Δημιουργούμε Νέα Σειρά:
    • Χρησιμοποιούμε τις μετρήσεις μας για να φτιάξουμε μια νέα λίστα με όλα τα μπισκότα σε σειρά. Δηλαδή, πρώτα θα βάλουμε όλα τα μπισκότα σοκολάτας, μετά τα μπισκότα βανίλιας και τέλος τα μπισκότα φράουλας.

Ας δούμε ένα παράδειγμα για να το καταλάβεις καλύτερα.

Παράδειγμα με Αριθμούς

Ας πούμε ότι έχουμε την εξής λίστα αριθμών:

[4, 2, 2, 8, 3, 3, 1]

Θέλουμε να τα βάλουμε σε αύξουσα σειρά.

  1. Μετράμε Πόσα Υπάρχουν:
    • Φτιάχνουμε μια λίστα με τις μετρήσεις των αριθμών: πόσα 1, 2, 3, 4, 8 έχουμε.
    • Ο αριθμός 1 εμφανίζεται 1 φορά, ο αριθμός 2 εμφανίζεται 2 φορές, ο αριθμός 3 εμφανίζεται 2 φορές, ο αριθμός 4 εμφανίζεται 1 φορά και ο αριθμός 8 εμφανίζεται 1 φορά.
  2. Δημιουργούμε Νέα Σειρά:
    • Χρησιμοποιούμε αυτές τις μετρήσεις για να φτιάξουμε τη νέα ταξινομημένη λίστα: [1, 2, 2, 3, 3, 4, 8]

Πώς Το Κάνουμε στην C#;

Ακολουθεί ο κώδικας για να το κάνουμε αυτό στην C#:

using System;

class CountingSortExample
{
    static void Main()
    {
        int[] numbers = { 4, 2, 2, 8, 3, 3, 1 };
        int[] sortedNumbers = CountingSort(numbers);

        Console.WriteLine("Ταξινομημένοι αριθμοί:");
        foreach (int num in sortedNumbers)
        {
            Console.Write(num + " ");
        }
    }

    static int[] CountingSort(int[] array)
    {
        int max = FindMax(array);
        int[] count = new int[max + 1];

        // Μετράμε κάθε αριθμό
        foreach (int num in array)
        {
            count[num]++;
        }

        int index = 0;
        // Δημιουργούμε τη νέα ταξινομημένη λίστα
        for (int i = 0; i < count.Length; i++)
        {
            while (count[i] > 0)
            {
                array[index++] = i;
                count[i]--;
            }
        }

        return array;
    }

    static int FindMax(int[] array)
    {
        int max = array[0];
        for (int i = 1; i < array.Length; i++)
        {
            if (array[i] > max)
                max = array[i];
        }
        return max;
    }
}

Εξηγώντας τον Κώδικα

  1. Μετράμε Κάθε Αριθμό:
    • Στη μέθοδο CountingSort, πρώτα βρίσκουμε τον μέγιστο αριθμό (FindMax).
    • Στη συνέχεια, δημιουργούμε ένα πίνακα count για να μετρήσουμε πόσες φορές εμφανίζεται κάθε αριθμός.
  2. Δημιουργούμε Νέα Σειρά:
    • Χρησιμοποιούμε τις μετρήσεις μας για να δημιουργήσουμε τη νέα ταξινομημένη λίστα με τους αριθμούς.

Αυτό είναι το Counting Sort! Είναι ένας απλός και γρήγορος τρόπος για να ταξινομήσεις αριθμούς αν γνωρίζεις τα όριά τους.

Counting SortDownload