Зміст курсу
Sorting Algorithms
Sorting Algorithms
Counting Sort
Counting Sort algorithm based on using keys of a specific range. It works by counting the number of values in given array with a key value and storing it in an array or map by this key.
Lets understand it with example:
arr = [4, 3, 1, 6, 9, 0, 1, 0, 2, 2]
indexes = [0 1 2 3 4 5 6 7 8 9] – key values, indexes of array
counts => [2 2 2 1 1 0 1 0 0 1] – number of elements with index value in array arr.
So you create additional array [2, 2, 2, 1, 1, 0, 1, 0, 0, 1].
Then, you can traverse it and get all elements in sorted order, since array indexes are sorted already.
Counting sort works only for arrays with non-negative integer values. For other cases, you can use dict() or any other ordered data structure.
Time complexity: O(max(N, max(arr)) - to traverse two arrays: first one of size N and second array of size max(arr).
Space complexity: O(max(arr)) - to create additional array.
Завдання
Implement the countingSort() function. Then call it for the given arrays arr1 and arr2 and output the sorted arrays separately. Do not change the arr1 and arr2.
Завдання
Implement the countingSort() function. Then call it for the given arrays arr1 and arr2 and output the sorted arrays separately. Do not change the arr1 and arr2.
Перейдіть на комп'ютер для реальної практикиПродовжуйте з того місця, де ви зупинились, використовуючи один з наведених нижче варіантівВсе було зрозуміло?
Counting Sort
Counting Sort algorithm based on using keys of a specific range. It works by counting the number of values in given array with a key value and storing it in an array or map by this key.
Lets understand it with example:
arr = [4, 3, 1, 6, 9, 0, 1, 0, 2, 2]
indexes = [0 1 2 3 4 5 6 7 8 9] – key values, indexes of array
counts => [2 2 2 1 1 0 1 0 0 1] – number of elements with index value in array arr.
So you create additional array [2, 2, 2, 1, 1, 0, 1, 0, 0, 1].
Then, you can traverse it and get all elements in sorted order, since array indexes are sorted already.
Counting sort works only for arrays with non-negative integer values. For other cases, you can use dict() or any other ordered data structure.
Time complexity: O(max(N, max(arr)) - to traverse two arrays: first one of size N and second array of size max(arr).
Space complexity: O(max(arr)) - to create additional array.
Завдання
Implement the countingSort() function. Then call it for the given arrays arr1 and arr2 and output the sorted arrays separately. Do not change the arr1 and arr2.
Завдання
Implement the countingSort() function. Then call it for the given arrays arr1 and arr2 and output the sorted arrays separately. Do not change the arr1 and arr2.
Перейдіть на комп'ютер для реальної практикиПродовжуйте з того місця, де ви зупинились, використовуючи один з наведених нижче варіантівВсе було зрозуміло?
Counting Sort
Counting Sort algorithm based on using keys of a specific range. It works by counting the number of values in given array with a key value and storing it in an array or map by this key.
Lets understand it with example:
arr = [4, 3, 1, 6, 9, 0, 1, 0, 2, 2]
indexes = [0 1 2 3 4 5 6 7 8 9] – key values, indexes of array
counts => [2 2 2 1 1 0 1 0 0 1] – number of elements with index value in array arr.
So you create additional array [2, 2, 2, 1, 1, 0, 1, 0, 0, 1].
Then, you can traverse it and get all elements in sorted order, since array indexes are sorted already.
Counting sort works only for arrays with non-negative integer values. For other cases, you can use dict() or any other ordered data structure.
Time complexity: O(max(N, max(arr)) - to traverse two arrays: first one of size N and second array of size max(arr).
Space complexity: O(max(arr)) - to create additional array.
Завдання
Implement the countingSort() function. Then call it for the given arrays arr1 and arr2 and output the sorted arrays separately. Do not change the arr1 and arr2.
Завдання
Implement the countingSort() function. Then call it for the given arrays arr1 and arr2 and output the sorted arrays separately. Do not change the arr1 and arr2.
Перейдіть на комп'ютер для реальної практикиПродовжуйте з того місця, де ви зупинились, використовуючи один з наведених нижче варіантівВсе було зрозуміло?
Counting Sort algorithm based on using keys of a specific range. It works by counting the number of values in given array with a key value and storing it in an array or map by this key.
Lets understand it with example:
arr = [4, 3, 1, 6, 9, 0, 1, 0, 2, 2]
indexes = [0 1 2 3 4 5 6 7 8 9] – key values, indexes of array
counts => [2 2 2 1 1 0 1 0 0 1] – number of elements with index value in array arr.
So you create additional array [2, 2, 2, 1, 1, 0, 1, 0, 0, 1].
Then, you can traverse it and get all elements in sorted order, since array indexes are sorted already.
Counting sort works only for arrays with non-negative integer values. For other cases, you can use dict() or any other ordered data structure.
Time complexity: O(max(N, max(arr)) - to traverse two arrays: first one of size N and second array of size max(arr).
Space complexity: O(max(arr)) - to create additional array.
Завдання
Implement the countingSort() function. Then call it for the given arrays arr1 and arr2 and output the sorted arrays separately. Do not change the arr1 and arr2.
Перейдіть на комп'ютер для реальної практикиПродовжуйте з того місця, де ви зупинились, використовуючи один з наведених нижче варіантівПерейдіть на комп'ютер для реальної практикиПродовжуйте з того місця, де ви зупинились, використовуючи один з наведених нижче варіантів