Let's actually write the code and summarize the sorting algorithm. I will try the language in Ruby.
Sorting is to sort the numbers given as input in ascending order.
Bubble sort repeats the operation of "comparing and swapping two adjacent numbers from right to left in the sequence". If you perform one round of processing for a sequence, the smallest number will be in the first of the array. It can be sorted by going around the number of elements.
def bubble_sort(array) length = array.length (length - 1).times do |round| (length - 1 - round).times do |n| if array[length - n - 1] < array[length - n - 2] smaller = array[length - n - 1] array[length - n - 1] = array[length - n - 2] array[length - n - 2] = smaller end end end array end array = [2, 3, 13, 7, 8, 9, 11, 1, 5] bubble_sort(array) #=> [1, 2, 3, 5, 7, 8, 9, 11, 13]
Contents of bubble sort function -Get the length of the array array as length (1st line) ・ (Length -1) The replacement is completed in the round (2nd line) ・ In the nth round, compare (length --n --1) times and replace (3rd line). ・ If the value on the left is larger than the value on the right, replace it (lines 4 to 7). The number of magnitude comparisons is (length -1) + (length -2) + ・ ・ ・ + 1 = (length) ^ 2/2.
The selection sort repeats the operation of "searching for the minimum value in the sequence and replacing it with the leftmost number".
def selection_sort(array) length = array.length (length - 1).times do |round| min = round + 1 round.upto(length - 1) do |n| if array[n] < array[min] min = n end end min_number = array[min] array[min] = array[round] array[round] = min_number end array end
Get the minimum index number, search for it, and then replace it. Same as bubble sort, the number of size comparisons is (length) ^ 2/2.
Next, I will also summarize insertion sort, heapsort, merge sort, quicksort, and bucket sort.