Black and White Dark Minimalist Food Photography Talking Presentation

[Audio] Counting Sort Algorithm. Counting Sort Algorithm.

[Audio] CREATE A COUNT ARRAY TO STORE THE COUNT OF EACH UNIQUE OBJECT. MODIFY COUNT ARRAY BY ADDING THE PREVIOUS NUMBER. CREATE OUTPUT ARRAY BY DECRESE COUNT ARRAY. COUNTING SORT 02.

[Audio] The input to counting sort consists of a collection of n items, each of which has a non negative integer key whose maximum value is at most k The input to be sorted is assumed to be more simply a sequence of integers itself, but this simplification does not accommodate many applications of counting sort. For instance, when used as a subroutine in radix sort, the keys for each call to counting sort are individual digits of larger item keys; it would not suffice to return only a sorted list of the key digits, separated from the items. • The output is an array of the items, in order by their keys. Because of the application to radix sorting, it is important for counting sort to be a stable sort: if two items have the same key as each other, they should have the same relative position in the output as they did in the input INPUT AND OUTPUT.

[Audio] Let the Array in range 0 to 5 input 1 4 3 2 3 5 2 Create an array that will hold the count of each number, with index ranges from 0 to 5 [0] [1] [2] [3] [4] [5] count 0 1 2 2 1 1.

[Audio] Modify count array by adding the previous number: input 1 4 3 2 3 5 2 [0] [1] [2] [3] [4] [5] sum count 0 1 3 5 6 7.

[Audio] Output each object from the input sequence followed by decreasing count by 1: input 1 4 3 2 3 5 2 [0] [1] [2] [3] [4] [5] sum count 0 1 3 5 6 7 [1] [2] [3] [4] [5] [6] [7] output.

[Audio] Output each object from the input sequence followed by decreasing count by 1: input 1 4 3 2 3 5 2 [0] [1] [2] [3] [4] [5] sum count 0 1 3 5 1 1 [1] [2] [3] [4] [5] [6] [7] output 1.

[Audio] input 1 4 3 2 3 5 2 [0] [1] [2] [3] [4] [5] sum count 0 0 3 5 6 7 [1] [2] [3] [4] [5] [6] [7] output 1 4.

[Audio] input 1 4 3 2 3 5 2 [0] [1] [2] [3] [4] [5] sum count 0 0 3 5 5 7 [1] [2] [3] [4] [5] [6] [7] output 1 3 4.

[Audio] input 1 4 3 2 3 5 2 [0] [1] [2] [3] [4] [5] sum count 0 0 3 4 5 7 [1] [2] [3] [4] [5] [6] [7] output 1 2 3 4.

[Audio] input 1 4 3 2 3 5 2 [0] [1] [2] [3] [4] [5] sum count 0 0 2 4 5 7 [1] [2] [3] [4] [5] [6] [7] output 1 2 3 3 4.

[Audio] input 1 4 3 2 3 5 2 [0] [1] [2] [3] [4] [5] sum count 0 0 2 3 5 7 [1] [2] [3] [4] [5] [6] [7] output 1 2 3 3 4 5.

[Audio] input 1 4 3 2 3 5 2 [0] [1] [2] [3] [4] [5] sum count 0 0 2 3 5 6 [1] [2] [3] [4] [5] [6] [7] output 1 2 2 3 3 4 5.

[Audio] input 1 4 3 2 3 5 2 [0] [1] [2] [3] [4] [5] sum count 0 0 1 3 5 6 [1] [2] [3] [4] [5] [6] [7] output 1 2 2 3 3 4 5.

[Audio] ARRAY IS NOW SORTED [1] [2] [3] [4] [5] [6] [7] output 1 2 2 3 3 4 5.

[Audio] So the counting sort takes a total time of: O(n + k) Counting sort is called stable sort. A sorting algorithm is stable when numbers with the same values appear in the output array in the same order as they do in the input array. Time Complexity.

[Audio] It uses arrays of length k + 1 and n, the total space usage of the algorithm is also O(n + k). For problem instances in which the maximum key value is significantly smaller than the number of items, counting sort can be highly space-efficient, as the only storage it uses other than its input and output arrays is the Count array which uses space O(k). SPACE COMPLEXITY.

[Audio] If the range of input data is not much bigger than the number of objects to be sorted, counting sort is efficient. Consider the following scenario: the data is 10, 5, 10K, 5K, and the input sequence is 1 to 10K. It isn't a sorting system based on comparisons. It has an O(n) running time complexity, with space proportional to the data range. It's frequently used as a subroutine in other sorting algorithms, such as radix sort. Counting sort counts the occurrences of the data object in O using partial hashing (1). The counting sort can also be used with negative inputs. Applications of Counting Sort Algorithm 1. 2. 3. 4. 5..

[Audio] CountingSort(A) //A[]-- Initial Array to Sort //Complexity: O(k) for i = 0 to k do c[i] = 0 //Storing Count of each element //Complexity: O(n) for j = 0 to n do c[A[j]] = c[A[j]] + 1 // Change C[i] such that it contains actual //position of these elements in output array ////Complexity: O(k) for i = 1 to k do c[i] = c[i] + c[i-1] //Build Output array from C[i] //Complexity: O(n) for j = n-1 downto 0 do B[ c[A[j]]-1 ] = A[j] c[A[j]] = c[A[j]] - 1 end func Pseudo code:.

[Audio] THANK YOU. THANK YOU.