정렬이란?

이번도 전회와 같이, 기본적인 이야기이므로 배열로 생각합니다. 배열 안에 있는 요소를 크기순으로 정렬할 수 없을까? ... 네, 거기 당신! 그럴 때는 정렬을 사용합시다! !
토마 뉘앙스는 이런 느낌이군요.

주의 : 배열의 머리 -> 요소 번호가 작은 쪽 · 배열의 엉덩이 -> 요소 번호가 큰 쪽으로하십시오.

선택 정렬(selective_sort)

확정되지 않은 배열의 요소에서 가장 작은 요소를 찾아서 배열의 확정되지 않은 부분의 머리로 이동시켜 확인합니다.

이것을 要素の数-1 회 반복하면 할 수 있습니다. (왜 要素の数-1 시간인지 말하면 마지막 하나는 별도로 아무 것도하지 않고 정렬되어 있기 때문입니다)

selective_sort.rb

def selective_sort(nums)
  sorts = nums.clone
  min_index = get_min_index(sorts, 0)
  for i in 0...sorts.size-1
    min_index = get_min_index(sorts, i)
    sorts[i], sorts[min_index] = sorts[min_index], sorts[i]
  end
  return sorts
end

def get_min_index(nums, start)
  return nil if start >= nums.size
  min_index = start
  for check in start...nums.size
    min_index = check if nums[check] < nums[min_index]
  end
  return min_index
end

nums = 10.times.map{rand(100)}
sorted = selective_sort(nums)
p "nums: #{nums}" # "nums: [47, 63, 93, 58, 29, 27, 96, 36, 60, 62]"
p "sorted: #{sorted}" # "sorted: [27, 29, 36, 47, 58, 60, 62, 63, 93, 96]"

버블 정렬(bubble_sort)

배열의 엉덩이에서 보면 두 요소를 비교하여 작은 쪽과 큰 쪽의 순서로 정렬한다.

1을 결정하지 않은 배열의 머리에 올 때까지 반복하여 머리에 오면 선두의 값을 확정시킨다.

2는 전체 배열이 결정될 때까지 반복됩니다.

bubble_sort.rb

def bubble_sort(nums)
  sorts = nums.clone
  for k in 0...sorts.size-1
    # confirm minimum nums from sorts.start
    (sorts.size-1).step(k+1, -1) do |i|
      # comparing 2nums from sorts.last
      sorts[i-1], sorts[i] = sorts[i], sorts[i-1] if sorts[i-1] > sorts[i]
    end
  end
  return sorts
end

nums = 10.times.map{rand(100)}
sorted = bubble_sort(nums)
p "nums: #{nums}" # "nums: [23, 77, 31, 51, 20, 70, 6, 58, 12, 76]"
p "sorted: #{sorted}" # "sorted: [6, 12, 20, 23, 31, 51, 58, 70, 76, 77]"

삽입 정렬(insert_sort)

배열의 머리 중 하나를 확인합니다.

결정되지 않은 배열의 머리 요소를 추출합니다. (어디까지나 이미지입니다)

빼낸 값을 확정하고 있는 배열의 요소의 머리로부터 비교해 간다,

추출 된 값이 요소보다 작 으면 요소 앞에 추출 된 값을 삽입합니다.

이 1 ~ 4를 배열의 요소가 모두 확정 될 때까지 반복합니다.

insert_sort.rb

def insert_sort(nums)
  sorts = nums.clone
  for i in 1...sorts.size
    # confirm minimum nums from sorts.start+1
    check = sorts[i].clone
    k = i
    while k>0 && sorts[k-1]>check
      # shift sorts[k-1] to k if sorts[k-1] greater than check
      sorts[k] = sorts[k-1]
      k -= 1
    end
    sorts[k] = check
  end
  return sorts
end
nums = 10.times.map{rand(100)}
sorted = insert_sort(nums)
p "nums: #{nums}" # "nums: [73, 6, 76, 73, 44, 46, 47, 98, 69, 98]"
p "sorted: #{sorted}" # "sorted: [6, 44, 46, 47, 69, 73, 73, 76, 98, 98]"

빠른 정렬(quick_sort)

이것은 설명이 조금 그림이 없으면 어렵기 때문에 신경이 쓰이는 분은 넷으로 조사해 봐 주시는 것을 추천합니다.
이미지로서는
1. 배열의 머리의 요소를 기준으로 요소를 크고 작은 머리와 엉덩이로 나눕니다.
2. 전부를 나누면 기준의 요소를 크고 작은 경계의 요소로 바꾼다.
3. 기준의 요소였던 요소 이외의 배열(대략이 2개로 나누어진다)을 따로따로 1과 2를 반복한다.

이것을 반복해 나가면 소트 할 수 있습니다.

quick_sort.rb

def quick_sort(nums, left, right)
  i = left + 1
  k = right
  while i<k
    while nums[i]<nums[left] && i<right
      i += 1
    end
    while nums[k]>=nums[left] && k>left
      k -= 1
    end
    nums[i], nums[k] = nums[k], nums[i] if i<k
  end
  nums[left], nums[k] = nums[k], nums[left] if nums[left]>nums[k]
  nums = quick_sort(nums, left, k-1) if left<k-1
  nums = quick_sort(nums, k+1, right) if right>k+1
  return nums
end

nums = 10.times.map{rand(100)}
sorted = quick_sort(nums.clone, 0, nums.size-1)
p "nums: #{nums}" # "nums: [79, 31, 56, 83, 80, 54, 54, 84, 65, 50]"
p "sorted: #{sorted}" # "sorted: [31, 50, 54, 54, 56, 65, 79, 80, 83, 84]"

요약

전회와 같은 정리가 되어 버립니다.
자세한 내용은이 책에 실려 있기 때문에 추천 해요! 언뜻 보면 초보자를위한 일러스트 풍부한 내용이없는 책처럼 보이지만 내용은 확고했습니다. 언어를 정해 코드를 쓰고 있는 것은 아니기 때문에 어느 언어를 사용하는 사람이라도 읽기 쉬운 한권이었습니다.
htps //w w. 아마존. 이. jp/dp/B01CZD 치네/레 f=dp-킨 dぇ-레아레 ct? _엔코엔 g=우 TF8&btkr=1