Рубрики

Подсчет Сортировка

Подсчет сортировки — это метод сортировки, основанный на ключах между определенным диапазоном. Он работает путем подсчета количества объектов, имеющих различные ключевые значения (вид хеширования). Затем делаем некоторую арифметику, чтобы вычислить положение каждого объекта в выходной последовательности.

Позвольте нам понять это с помощью примера.

For simplicity, consider the data in the range 0 to 9. 
Input data: 1, 4, 1, 2, 7, 5, 2
  1) Take a count array to store the count of each unique object.
  Index:     0  1  2  3  4  5  6  7  8  9
  Count:     0  2  2  0   1  1  0  1  0  0

  2) Modify the count array such that each element at each index 
  stores the sum of previous counts. 
  Index:     0  1  2  3  4  5  6  7  8  9
  Count:     0  2  4  4  5  6  6  7  7  7

The modified count array indicates the position of each object in 
the output sequence.
 
  3) Output each object from the input sequence followed by 
  decreasing its count by 1.
  Process the input data: 1, 4, 1, 2, 7, 5, 2. Position of 1 is 2.
  Put data 1 at index 2 in output. Decrease count by 1 to place 
  next data 1 at an index 1 smaller than this index.

Ниже приведена реализация сортировки отсчетов.

C ++

// C ++ Программа для подсчета сортировки
#include<bits/stdc++.h> 
#include<string.h>

using namespace std; 

#define RANGE 255 

  
// Основная функция такого рода
// заданная строка arr [] в
// алфавитный порядок

void countSort(char arr[]) 

    // Выходной массив символов

    // это будет отсортировано обр

    char output[strlen(arr)]; 

  

    // Создание массива count для хранения счетчика inidividul

    // символы и инициализируем массив count как 0

    int count[RANGE + 1], i; 

    memset(count, 0, sizeof(count)); 

  

    // Сохраняем количество каждого символа

    for(i = 0; arr[i]; ++i) 

        ++count[arr[i]]; 

  

    // Изменить count [i] так, чтобы count [i] теперь содержал фактический

    // положение этого символа в выходном массиве

    for (i = 1; i <= RANGE; ++i) 

        count[i] += count[i-1]; 

  

    // Создаем массив выходных символов

    for (i = 0; arr[i]; ++i) 

    

        output[count[arr[i]]-1] = arr[i]; 

        --count[arr[i]]; 

    

  

    / *

    Для стабильного алгоритма

    для (i = sizeof (arr) -1; i> = 0; --i)

    {

        output [count [arr [i]] - 1] = arr [i];

        --count [обр [I]];

    }

      

    Для логики: см. Реализацию

    * /

  

    // Копируем выходной массив в arr, так что теперь arr

    // содержит отсортированные символы

    for (i = 0; arr[i]; ++i) 

        arr[i] = output[i]; 

  
// Код драйвера

int main() 

    char arr[] = "geeksforgeeks";

  

    countSort(arr); 

  

    cout<< "Sorted character array is " << arr; 

    return 0; 

  
// Этот код предоставлен rathbhupendra

С

// C Программа для подсчета сортировки
#include <stdio.h>
#include <string.h>
#define RANGE 255

  
// Основная функция, которая сортирует заданную строку arr [] в
// алфавитный порядок

void countSort(char arr[])

{

    // Выходной массив символов, который будет отсортирован

    char output[strlen(arr)];

  

    // Создание массива count для хранения счетчика inidividul

    // символы и инициализируем массив count как 0

    int count[RANGE + 1], i;

    memset(count, 0, sizeof(count));

  

    // Сохраняем количество каждого символа

    for(i = 0; arr[i]; ++i)

        ++count[arr[i]];

  

    // Изменить count [i] так, чтобы count [i] теперь содержал фактический

    // положение этого символа в выходном массиве

    for (i = 1; i <= RANGE; ++i)

        count[i] += count[i-1];

  

    // Создаем массив выходных символов

    for (i = 0; arr[i]; ++i)

    {

        output[count[arr[i]]-1] = arr[i];

        --count[arr[i]];

    }

  

    / *

     Для стабильного алгоритма

     для (i = sizeof (arr) -1; i> = 0; --i)

    {

        output [count [arr [i]] - 1] = arr [i];

        --count [обр [I]];

    }

     

    Для логики: см. Реализацию

    * /

  

    // Копируем выходной массив в arr, так что теперь arr

    // содержит отсортированные символы

    for (i = 0; arr[i]; ++i)

        arr[i] = output[i];

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

    char arr[] = "geeksforgeeks";// "applepp";

  

    countSort(arr);

  

    printf("Sorted character array is %sn", arr);

    return 0;

}

Джава

// Java-реализация Counting Sort

class CountingSort

{

    void sort(char arr[])

    {

        int n = arr.length;

  

        // Выходной массив символов, который будет отсортирован

        char output[] = new char[n];

  

        // Создание массива count для хранения счетчика inidividul

        // символы и инициализируем массив count как 0

        int count[] = new int[256];

        for (int i=0; i<256; ++i)

            count[i] = 0;

  

        // сохранить количество каждого символа

        for (int i=0; i<n; ++i)

            ++count[arr[i]];

  

        // Изменить count [i] так, чтобы count [i] теперь содержал фактический

        // положение этого символа в выходном массиве

        for (int i=1; i<=255; ++i)

            count[i] += count[i-1];

  

        // Создаем массив выходных символов

        // Чтобы сделать его стабильным, мы работаем в обратном порядке.

        for (int i = n-1; i>=0; i--)

        {

            output[count[arr[i]]-1] = arr[i];

            --count[arr[i]];

        }

  

        // Копируем выходной массив в arr, так что теперь arr

        // содержит отсортированные символы

        for (int i = 0; i<n; ++i)

            arr[i] = output[i];

    }

  

    // Метод драйвера

    public static void main(String args[])

    {

        CountingSort ob = new CountingSort();

        char arr[] = {'g', 'e', 'e', 'k', 's', 'f', 'o',

                    'r', 'g', 'e', 'e', 'k', 's'

                    };

  

        ob.sort(arr);

  

        System.out.print("Sorted character array is ");

        for (int i=0; i<arr.length; ++i)

            System.out.print(arr[i]);

    }

}
/ * Этот код предоставлен Раджатом Мишрой * /

питон

# Python программа для подсчета сортировки

  
# Основная функция, которая сортирует заданную строку arr [] в
# Алфавитный порядок

def countSort(arr):

  

    # Выходной массив символов, который будет иметь отсортированный обр

    output = [0 for i in range(256)]

  

    # Создайте массив count для хранения счетчика inidividul

    # символов и инициализировать массив count как 0

    count = [0 for i in range(256)]

  

    # Для хранения полученного ответа, так как

    # строка неизменна

    ans = ["" for _ in arr]

  

    # Хранить количество каждого персонажа

    for i in arr:

        count[ord(i)] += 1

  

    # Измените count [i] так, чтобы count [i] теперь содержал фактический

    # позиция этого символа в выходном массиве

    for i in range(256):

        count[i] += count[i-1]

  

    # Построить выходной массив символов

    for i in range(len(arr)):

        output[count[ord(arr[i])]-1] = arr[i]

        count[ord(arr[i])] -= 1

  

    # Скопируйте выходной массив в arr, так что теперь arr

    # содержит отсортированные символы

    for i in range(len(arr)):

        ans[i] = output[i]

    return ans 

  
# Программа драйвера для проверки вышеуказанной функции

arr = "geeksforgeeks"

ans = countSort(arr)

print "Sorted character array is %s"  %("".join(ans))

  
# Этот код предоставлен Nikhil Kumar Singh

C #

// C # реализация Counting Sort

using System;

  

class GFG {

      

    static void countsort(char []arr)

    {

        int n = arr.Length;

  

        // Выходной массив символов, который

        // будет отсортирован обр

        char []output = new char[n];

  

        // Создаем массив count для хранения

        // количество символов inidividul

        // и инициализируем массив count как 0

        int []count = new int[256];

          

        for (int i=0; i<256; ++i)

            count[i] = 0;

  

        // сохранить количество каждого символа

        for (int i=0; i<n; ++i)

            ++count[arr[i]];

  

        // Изменим count [i] так, чтобы count [i]

        // теперь содержит актуальную позицию

        // этот символ в выходном массиве

        for (int i=1; i<=255; ++i)

            count[i] += count[i-1];

  

        // Создаем массив выходных символов

        // Чтобы сделать его стабильным, мы работаем в обратном порядке.

        for (int i = n-1; i>=0; i--)

        {

            output[count[arr[i]]-1] = arr[i];

            --count[arr[i]];

        }

  

        // Копируем выходной массив в arr, так

        // этот arr теперь содержит отсортированный

        // персонажи

        for (int i = 0; i<n; ++i)

            arr[i] = output[i];

    }

  

    // Метод драйвера

    public static void Main()

    {

          

        char []arr = {'g', 'e', 'e', 'k', 's', 'f', 'o',

                    'r', 'g', 'e', 'e', 'k', 's'

                    };

  

        countsort(arr);

  

        Console.Write("Sorted character array is ");

        for (int i=0; i<arr.Length; ++i)

            Console.Write(arr[i]);

    }

}

  
// Этот код предоставлен Sam007.

PHP

<?php
// PHP программа для подсчета сортировки

  

$RANGE = 255;

  
// Основная функция такого рода
// заданная строка arr [] в
// алфавитный порядок

function countSort($arr)

{

    global $RANGE;

      

    // Выходной массив символов

    // это будет отсортировано обр

    $output = array(strlen($arr));

    $len = strlen($arr);

      

    // Создаем массив count для

    // сохраняем количество inidividul

    // символы и инициализация

    // считать массив как 0

    $count = array_fill(0, $RANGE + 1, 0);

  

    // Сохранить количество

    // каждый символ

    for($i = 0; $i < $len; ++$i)

        ++$count[ord($arr[$i])];

  

    // Изменим count [i] так, чтобы

    // count [i] теперь содержит

    // фактическая позиция этого

    // символ в выходном массиве

    for ($i = 1; $i <= $RANGE; ++$i)

        $count[$i] += $count[$i - 1];

  

    // Построить вывод

    // массив символов

    // Чтобы сделать его стабильным, мы работаем

    // в обратном порядке.

    for ($i = $len-1; $i >= 0 ; $i--)

    {

        $output[$count[ord($arr[$i])] - 1] = $arr[$i];

        --$count[ord($arr[$i])];

    }

  

    // Копируем выходной массив в

    // обр, так что обр

    // содержит отсортированные символы

    for ($i = 0; $i < $len; ++$i)

        $arr[$i] = $output[$i];

return $arr;

}

  
// Код драйвера

$arr = "geeksforgeeks"; // "applepp";

  

$arr = countSort($arr);

  

echo "Sorted character array is " . $arr;

  
// Этот код предоставлен mits
?>


Выход:

Sorted character array is eeeefggkkorss

Сложность времени: O (n + k), где n — количество элементов во входном массиве, а k — диапазон входных данных.
Вспомогательное пространство: O (n + k)

Проблема с предыдущей сортировкой была в том, что мы не могли отсортировать элементы, если в них есть отрицательные числа. Потому что нет отрицательных индексов массива. Итак, что мы делаем, мы находим минимальный элемент и будем хранить количество этого минимального элемента при нулевом индексе.

C ++

// Считаем сортировку, которая также принимает отрицательные числа
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

  

void countSort(vector <int>& arr)

{

    int max = *max_element(arr.begin(), arr.end());

    int min = *min_element(arr.begin(), arr.end());

    int range = max - min + 1;

      

    vector<int> count(range), output(arr.size());

    for(int i = 0; i < arr.size(); i++)

        count[arr[i]-min]++;

          

    for(int i = 1; i < count.size(); i++)

           count[i] += count[i-1];

    

    for(int i = arr.size()-1; i >= 0; i--)

    

         output[ count[arr[i]-min] -1 ] = arr[i]; 

              count[arr[i]-min]--; 

    }

      

    for(int i=0; i < arr.size(); i++)

            arr[i] = output[i];

}

  

void printArray(vector <int> & arr) 

    for (int i=0; i < arr.size(); i++) 

        cout << arr[i] << " "

    cout << "\n"

}

  

int main()

{

    vector<int> arr = {-5, -10, 0, -3, 8, 5, -1, 10};

    countSort (arr);

    printArray (arr);

    return 0;

}

Джава

// Считаем сортировку, которая также принимает отрицательные числа

import java.util.*;

  

class GFG 

{

  

    static void countSort(int[] arr) 

    {

        int max = Arrays.stream(arr).max().getAsInt();

        int min = Arrays.stream(arr).min().getAsInt();

        int range = max - min + 1;

        int count[] = new int[range];

        int output[] = new int[arr.length];

        for (int i = 0; i < arr.length; i++) 

        {

            count[arr[i] - min]++;

        }

  

        for (int i = 1; i < count.length; i++) 

        {

            count[i] += count[i - 1];

        }

  

        for (int i = arr.length - 1; i >= 0; i--) 

        {

            output[count[arr[i] - min] - 1] = arr[i];

            count[arr[i] - min]--;

        }

  

        for (int i = 0; i < arr.length; i++)

        {

            arr[i] = output[i];

        }

    }

  

    static void printArray(int[] arr) 

    {

        for (int i = 0; i < arr.length; i++) 

        {

            System.out.print(arr[i] + " ");

        }

        System.out.println("");

    }

  

    // Код драйвера

    public static void main(String[] args)

    {

        int[] arr = {-5, -10, 0, -3, 8, 5, -1, 10};

        countSort(arr);

        printArray(arr);

    }

  
// Этот код предоставлен princiRaj1992


Выход:

-10 -5 -3 -1 0 5 8 10 

Очки, которые следует отметить:
1. Подсчет сортировки эффективен, если диапазон входных данных не намного превышает количество сортируемых объектов. Рассмотрим ситуацию, когда входная последовательность находится в диапазоне от 1 до 10K, а данные — 10, 5, 10K, 5K.
2. Это не сортировка на основе сравнения. Его сложность во время выполнения составляет O (n) с пространством, пропорциональным диапазону данных.
3. Он часто используется как подпрограмма для другого алгоритма сортировки, такого как сортировка по основанию.
4. Подсчет сортировки использует частичное хеширование для подсчета вхождения объекта данных в O (1).
5. Счетная сортировка может быть расширена для работы и для отрицательных входных данных.

Упражнение:
1. Измените приведенный выше код, чтобы отсортировать входные данные в диапазоне от M до N.
2. Является ли счет сортировки стабильным и онлайн?
3. Мысли о распараллеливании алгоритма сортировки отсчетов.

Фотосъёмка:






Тест на подсчет сортировки

Практика кодирования для сортировки

Другие алгоритмы сортировки на GeeksforGeeks / GeeksQuiz
Выбор сортировки , Bubble Сортировка , вставка Сортировка , Merge Сортировка , Heap Сортировка , QuickSort , Radix Сортировка , Counting Сортировка , Bucket Sort , ShellSort , расческа Сортировка , PegionHole Сортировка

Эта статья составлена Aashish Barnwal . Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Подсчет Сортировка

0.00 (0%) 0 votes