Let’s try to put together a sort algorithm by actually writing code. Let’s try the language with Ruby.
To sort, 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 the process is repeated once for a sequence of numbers, the smallest number will be in the first position of the array. It is possible to sort 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 array array by length (first line) ・(Length-1) round ends swapping (second line)
- In the nth round, (length-n-1) times are compared and the process of swapping is performed (3rd line)
・If the value on the left is greater than the value on the right, swap them (lines 4-7).
The number of comparisons is (length-1) + (length-2) + … + 1 = (length)^2 / 2.
For selective sorting, the operation of “searching for the minimum value in the sequence of numbers and replacing it with the leftmost number” is repeated.
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 smallest index number and replace it after searching. Same as bubble sort, the number of comparisons is (length)^2/2.
Next, I’ll summarize insert sort, heap sort, merge sort, quick sort, and bucket sort.