Сортировка подсчетом python реализация

Алгоритм сортировки подсчетом — реализация на C, Java и Python

Учитывая коллекцию n элементов, каждый из которых имеет неотрицательный целочисленный ключ, максимальное значение которого не превышает k , эффективно отсортируйте его, используя алгоритм сортировки подсчетом.

Обзор

Сортировка подсчетом — это алгоритм сортировки на основе целых чисел для сортировки массива, ключи которого лежат в определенном диапазоне. Он подсчитывает общее количество элементов с каждым уникальным значением ключа, а затем использует эти подсчеты для определения позиций каждого значения ключа в выходных данных.

Мы можем использовать сортировку подсчетом, чтобы найти наиболее часто встречающуюся букву в файле или эффективно отсортировать массив с ограниченным диапазоном. Он часто используется в качестве подпрограммы в алгоритме сортировки по основанию, поэтому сортировка подсчетом должна быть стабильной.

Алгоритм

Алгоритм циклически перебирает элементы, вычисляя гистограмму количества раз, когда каждый ключ входил во входную коллекцию. Затем он выполняет вычисление суммы префиксов, чтобы определить для каждого ключа начальную позицию в выходном массиве элементов, имеющих этот ключ. Наконец, он снова перебирает элементы, перемещая каждый элемент в его отсортированную позицию в выходном массиве.

Алгоритм может быть реализован, как показано ниже, на C, Java и Python. В приведенном ниже коде:

1. После первого цикла for freq[i] хранит общее количество элементов с ключом, равным i .
2. После второго цикла for он вместо этого сохраняет общее количество элементов с ключом меньше i , который совпадает с первым индексом, по которому элемент с ключом i должны храниться в выходном массиве.
3. На протяжении третьего цикла, freq[i] всегда сохраняет следующую позицию в выходном массиве, в которой элемент с ключом i должны быть сохранены, поэтому каждый элемент перемещается в правильное положение в выходном массиве.

Источник

Сортировка подсчетом на Python

Программа будет сортировать список методом подсчета (Counting sort).

Алгоритм

Подсчитываем, сколько раз в массиве встречается каждое значение, и заполняем массив подсчитанными элементами в соответствующих количествах. Счётчики для всего диапазона чисел создаются заранее (изначально равны нулю).

Сложность сортировки по времени

Шаги к правильному решению

1. Создадим функцию counting_sort , которая принимает на вход список и переменную largest .
2. Внутри функции создадим список c нулями и длиной largest+1 .
3. Для каждого элемента входного списка увеличиваем значение элемента таким образом c[alist[i]] = c[alist[i]] + 1 .
4. Теперь список с содержит частоту каждого элемента входного списка.
5. Каждому элементу от 1 до length(c) -1 добавляем к значению текущего элемента значение предыдущего c[i] = c[i] + c[i — 1] .
6. Создадим result список с таким же размером, как и входной список.
7. Создадим цикл, который итерируется по списку в обратном порядке.
8. В каждой итерации цикла установим result[c[x]] = x , а затем уменьшим c[x] на 1.

def counting_sort(alist, largest): c = [0]*(largest + 1) for i in range(len(alist)): c[alist[i]] = c[alist[i]] + 1 # Find the last index for each element c[0] = c[0] - 1 # to decrement each element for zero-based indexing for i in range(1, largest + 1): c[i] = c[i] + c[i - 1] result = [None]*len(alist) # Though it is not required here, # it becomes necessary to reverse the list # when this function needs to be a stable sort for x in reversed(alist): result[c[x]] = x c[x] = c[x] - 1 return result alist = input('Enter the list of (nonnegative) numbers: ').split() alist = [int(x) for x in alist] k = max(alist) sorted_list = counting_sort(alist, k) print('Sorted list: ', end='') print(sorted_list)

Источник

Counting Sort in Python

Counting sort is a sorting algorithm used to sort elements of an array in linear time. We usually use Counting Sort to sort integer arrays.

Counting Sort a stable, non-comparative algorithm.

Non-comparative sorting algorithms perform sorting without any comparison between elements to be sorted.

Stable sorting algorithms preserve the relative order of elements with the same value in the sorted array. That means that the relative order of two same-value elements in the original array will be the same as their relative order in the sorted array.

Counting sort is not an in-place algorithm, it uses an auxiliary array to sort elements of an input array.

How Does Counting Sort Work?

Let’s first take an intuitive look at how the algorithm works.

Assume that we have the array I = [2, 2, 0, 6, 1, 9, 9, 7] and we want to sort it. We’ll call the array I the input array.

Counting Sort works by counting the number of elements that fit a distinct key value, and then calculates the positions of each key.

First of all, we need to find the element with the highest value, we’ll call it the maximum element — maxElement = 9 .

Then, we’ll create an auxiliary array with maxElement+1 elements, called the count array (C). We’ll use it to store the number of occurrences of each individual element in the input array I . Therefore, all counts should be initialized to 0:

 C = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0] # Count array # indices: 0 1 2 3 4 5 6 7 8 9 

Now, we need to go through the following steps:

1. Go over each element of the input array and increase its corresponding count by 1

For example, if we come across an element with the value of 2 in the input array ( I ), we add 1 to the element with the index 2 in the count array:

 I = [2, 2, 0, 6, 1, 9, 9, 7] # The first element is 2 ^ C = [0, 0, 1, 0, 0, 0, 0, 0, 0, 0] # We increase count of 2nd element by 1 #indices: 0 1 2 3 4 5 6 7 8 9 

After this step, the count array will store the number of occurrences of each element in the input array:

 C = [1, 1, 2, 0, 0, 0, 1, 1, 0, 2] #indices: 0 1 2 3 4 5 6 7 8 9 # Element 0 has 1 occurrence # Element 1 has 1 occurrence # Element 2 has 2 occurrences # Element 3 has no occurrences. 

2. For each element in the count array, sum up its value with the value of all its previous elements, and store that value as the value of the current element:

 C = [1, 2, 4, 4, 4, 4, 5, 6, 6, 8] #indices: 0 1 2 3 4 5 6 7 8 9 # Element 0 = 1 # Element 1 = 1 + 1 # Element 2 = 1 + 1 + 2 # Element 3 = 1 + 1 + 2 + 0 #. 

This way, we are storing the cumulative sum of the elements of the count array, on each step.

3. Calculate element position based on the count array values:

To store this sorted sequence, we’ll need to create a new array. Let’s call it the output array ( O ), and initialize it with k zeros, where k is the number of elements in the input array:

 O = [0, 0, 0, 0, 0, 0, 0, 0] // Initialized output array #indices: 0 1 2 3 4 5 6 7 

For each element I[i] (starting from the end) in the input array:

Free eBook: Git Essentials

Check out our hands-on, practical guide to learning Git, with best-practices, industry-accepted standards, and included cheat sheet. Stop Googling Git commands and actually learn it!

1. Find the index in the count array that is equal to the value of the current element I[i]
   • That’s the element C[j] where j=I[i]
2. Subtract 1 from the value of the C[i]
   • Now we have newValue = C[i]-1
3. Store the I[i] to the O[newValue]
4. Update the C[i] with the newValue

In the end, the output array contains the sorted elements of the input array!

Counting Sort — Python Implementation

Now, with all that out of the way — let’s go ahead and implement Counting Sort in Python:

def countingSort(inputArray): # Find the maximum element in the inputArray maxElement= max(inputArray) countArrayLength = maxElement+1 # Initialize the countArray with (max+1) zeros countArray = [0] * countArrayLength # Step 1 -> Traverse the inputArray and increase # the corresponding count for every element by 1 for el in inputArray: countArray[el] += 1 # Step 2 -> For each element in the countArray, # sum up its value with the value of the previous # element, and then store that value # as the value of the current element for i in range(1, countArrayLength): countArray[i] += countArray[i-1] # Step 3 -> Calculate element position # based on the countArray values outputArray = [0] * len(inputArray) i = len(inputArray) - 1 while i >= 0: currentEl = inputArray[i] countArray[currentEl] -= 1 newPosition = countArray[currentEl] outputArray[newPosition] = currentEl i -= 1 return outputArray inputArray = [2,2,0,6,1,9,9,7] print("Input array = ", inputArray) sortedArray = countingSort(inputArray) print("Counting sort result = ", sortedArray) 

Running the code above will produce the following output:

Input array = [2, 2, 0, 6, 1, 9, 9, 7] Counting sort result = [0, 1, 2, 2, 6, 7, 9, 9] 

The Complexity of the Counting Sort Algorithm

The Counting sort algorithm uses only simple for and while loops without any complex recursions and subroutine calls, therefore, its complexity analysis is a pretty straightforward process.

Before we dive into the complexity analysis, let’s label the length of the input array as n and the value of the maximum element in the input array as k .

Time Complexity

The first step of the algorithm iterates over the input array n times in order to initialize the count array, so it has the complexity of O(n).

The second step iterates over the count k times in order to calculate the cumulative sum of each element, so it has the complexity of O(k).

The third step performs the sorting based on the counting array, so it has to iterate in a while loop n times, therefore it has the complexity of O(n).

Collectively, the time complexity of the Counting Sort algorithm is O(n+k).

Space Complexity

Counting sort uses input and output array, both of length n and one count array of length (k+1) .

Therefore, the total space that this algorithm uses is O(n+k).

Conclusion

All in all, Counting Sort is a great and efficient, yet simple sorting algorithm. In ideal circumstances, it is really easy to understand and learn but still manages to maintain linear complexity.

The real problem occurs when the value of the largest element k exceeds the number of elements in the input array n . As the k approaches n² , the time complexity of counting sort gets closer to O(n²) , which is a horrible time complexity for a sorting algorithm. Therefore, it’s not recommended to use counting sort if the input array has a large range of values.

Ideally, we will use Counting Sort to sort some integer arrays with a small range of values or as a subroutine for some other sorting algorithm, such as Radix Sort. That way, we will ensure maximizing the full potential of the counting sort, while still avoiding all of the suboptimal use cases.

Источник