Visualisation: https://www.toptal.com/developers/sorting-algorithms
We will go through the array from left to right. If the current item is larger than the next, swap them. We do this until the array is sorted. Note that after the first iteration, the largest element will be at the end of the array, in the right place. After two iterations, the two largest elements will be in the right place, and so on. Obviously, after no more than n iterations, the array will be sorted. Thus, the asymptotic behavior in the worst and middle case is O(n2), in the best case - O(n). Note that bubble sorting works slowly on tests in which small elements are at the end (they are also called “turtles”). Such an element at each step of the algorithm will shift only one position to the left.
Будем идти по массиву слева направо. Если текущий элемент больше следующего, меняем их местами. Делаем так, пока массив не будет отсортирован. Заметим, что после первой итерации самый большой элемент будет находиться в конце массива, на правил
Visualisation: https://www.toptal.com/developers/sorting-algorithms https://www.youtube.com/watch?v=SIrdTFF8-4s
When sorting by inserts, the array is sorted sequentially. Each next element under consideration is placed so as to be between the nearest minimum element and the nearest maximum.
При сортировке вставками, массив перебирается последовательно. Каждый следующий рассматриваемый элемент размещается так, чтобы оказаться между ближайшим минимальным элементом и ближайшим максимальным.
puts 'Please, enter array size'
arr_size = gets.chomp.to_i
Visualisation: https://www.toptal.com/developers/sorting-algorithms
def merge_sort(array)
l = array.length
return array if l <= 1
mid = l/2
left = array[0...mid]
Visualisation: https://www.toptal.com/developers/sorting-algorithms
def quicksort(array, beg_index, end_index)
if beg_index < end_index
p_index = partition(array, beg_index, end_index)
quicksort(array, beg_index, p_index - 1)
quicksort(array, p_index + 1, end_index)
end
Visualisation: https://www.toptal.com/developers/sorting-algorithms
The main idea of this method is to create a sorted sequence by attaching one element after another in the correct order. The selection sorting algorithm consists of several successive steps. At each sorting step, the current array element is interchanged with the element with the smallest value. Thus, an array of values is obtained, sorted in ascending order.
Основная мысль этого метода заключается в том, чтобы создать отсортированную последовательность, присоединяя к ней один элемент за другим в правильном порядке. Алгоритм сортировки выбором состоит из нескольких последовательных шагов. На каждом шаге сортировки текущий элемент массива меняется местами с элементом с наименьшим значением. Таким образом, получается массив значений, отсортированный по возрастанию.
puts 'Please, enter array size'
arr_size = gets.chomp.to_i
array = Array.new(arr_size) { rand(1..100) }
As we already know, a natural greedy strategy for the change problem does not work correctly for any set of denominations. For example, if the available denominations are 1, 3, and 4, the greedy algorithm will change 6 cents using three coins (4 + 1 + 1) while it can be changed using just two coins (3 + 3). Your goal now is to apply dynamic programming for solving the Money Change Problem for denominations 1, 3, and 4.
Integer money.
The minimum number of coins with denominations 1, 3, 4 that changes money.
result = gets.chomp.to_i
coins = [1,3,4]
The edit distance between two strings is the minimum number of operations (insertions, deletions, and substitutions of symbols) to transform one string into another. It is a measure of similarity of two strings. Edit distance has applications, for example, in computational biology, natural language processing, and spell checking. Your goal in this problem is to compute the edit distance between two strings.
The goal of this problem is to implement the algorithm for computing the edit distance between two strings.
You are given a set of bars of gold and your goal is to take as much gold as possible into your bag. There is just one copy of each bar and for each bar you can either take it or not (hence you cannot take a fraction of a bar).
Given 𝑛 gold bars, find the maximum weight of gold that fits into a bag of capacity 𝑊.
The first line of the input contains the capacity 𝑊 of a knapsack and the number 𝑛 of bars
You and two of your friends have just returned back home after visiting various countries. Now you would like to evenly split all the souvenirs that all three of you bought.
The first line contains an integer 𝑛. The second line contains integers 𝑣1, 𝑣2, . . . , 𝑣𝑛 separated by spaces.
1 ≤ 𝑛 ≤ 20, 1 ≤ 𝑣𝑖 ≤ 30 for all 𝑖.