Cookie Consent by Free Privacy Policy Generator ๐Ÿ“Œ Sorting Algorithms with Ruby

๐Ÿ  Team IT Security News

TSecurity.de ist eine Online-Plattform, die sich auf die Bereitstellung von Informationen,alle 15 Minuten neuste Nachrichten, Bildungsressourcen und Dienstleistungen rund um das Thema IT-Sicherheit spezialisiert hat.
Ob es sich um aktuelle Nachrichten, Fachartikel, Blogbeitrรคge, Webinare, Tutorials, oder Tipps & Tricks handelt, TSecurity.de bietet seinen Nutzern einen umfassenden รœberblick รผber die wichtigsten Aspekte der IT-Sicherheit in einer sich stรคndig verรคndernden digitalen Welt.

16.12.2023 - TIP: Wer den Cookie Consent Banner akzeptiert, kann z.B. von Englisch nach Deutsch รผbersetzen, erst Englisch auswรคhlen dann wieder Deutsch!

Google Android Playstore Download Button fรผr Team IT Security



๐Ÿ“š Sorting Algorithms with Ruby


๐Ÿ’ก Newskategorie: Programmierung
๐Ÿ”— Quelle: dev.to

Sorting algorithms are algorithms that put elements of a list or array in a particular order. There are various sorting algorithms, each with their own advantages and disadvantages in terms of time and space complexity. Here are some of the most common sorting algorithms:

  1. Bubble Sort: Bubble sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order.

  2. Selection Sort: Selection sort is a sorting algorithm that selects the smallest element from an unsorted list in each iteration and places it at the beginning of the list.

  3. Insertion Sort: Insertion sort is a sorting algorithm that builds the final sorted list one item at a time. It iterates through an input array and removes one element per iteration, finds the location it belongs within the sorted list, and inserts it there.

  4. Merge Sort: Merge sort is a divide and conquer algorithm that divides the input array into two halves, sorts each half, and then merges the two sorted halves.

  5. Quick Sort: Quick sort is a divide and conquer algorithm that selects a "pivot" element from the array and partitions the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. It then recursively sorts the sub-arrays.

  6. Heap Sort: Heap sort is a comparison-based sorting algorithm that uses a binary heap data structure. First, it builds a heap from the input data, and then it repeatedly extracts the maximum element from the heap, which results in a sorted array.

  7. Radix Sort: Radix Sort is a sorting algorithm that sorts data by digit positions. It sorts the data by comparing digits in the same position from each item to be sorted.

Each of these algorithms has its own time and space complexity and may be more or less suited to different types of data and input sizes. Choosing the appropriate algorithm for a particular use case can be important for performance reasons.

Bubble sort

Bubble sort, sometimes referred to as sinking sort, is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted.

def bubble_sort(array)
  n = array.length
  loop do
    swapped = false

    (n-1).times do |i|
      if array[i] > array[i+1]
        array[i], array[i+1] = array[i+1], array[i]
        swapped = true
      end
    end

    break if not swapped
  end

  array
end

Selection sort

Selection sort is an in-place comparison sort algorithm that divides the input list into two parts: the sublist of items already sorted, which is built up from left to right at the front of the list, and the sublist of items remaining to be sorted that occupy the rest of the list. The algorithm finds the minimum value in the unsorted sublist and swaps it with the leftmost unsorted element, moving the sublist boundaries one element to the right.

def selection_sort(array)
  n = array.length
  for i in 0...n
    min_idx = i
    for j in (i+1)...n
      if array[j] < array[min_idx]
        min_idx = j
      end
    end
    array[i], array[min_idx] = array[min_idx], array[i]
  end

  array
end

Insertion sort

Insertion sort is a simple sorting algorithm that builds the final sorted array one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort.

def insertion_sort(array)
  n = array.length
  for i in 1...n
    key = array[i]
    j = i - 1

    while j >= 0 && array[j] > key
      array[j+1] = array[j]
      j -= 1
    end

    array[j+1] = key
  end

  array
end

Merge sort

Merge sort is an efficient, general-purpose, comparison-based sorting algorithm. Most implementations produce a stable sort, which means that if two elements have the same value, they will retain their relative order in the sorted sequence.

def merge_sort(array)
  if array.length <= 1
    return array
  end

  mid = array.length / 2
  left = array[0...mid]
  right = array[mid...array.length]

  left = merge_sort(left)
  right = merge_sort(right)

  merge(left, right)
end

def merge(left, right)
  result = []
  while left.length > 0 && right.length > 0
    if left[0] <= right[0]
      result << left.shift
    else
      result << right.shift
    end
  end

  while left.length > 0
    result << left.shift
  end

  while right.length > 0
    result << right.shift
  end

  result
end

Quick sort

Quick Sort is a sorting algorithm that uses the divide-and-conquer technique to sort an array. It is one of the most efficient sorting algorithms with an average time complexity of O(n*log(n)). The basic idea of Quick Sort is to pick a pivot element, partition the array around the pivot, and then recursively sort the left and right subarrays.

Here are the detailed steps to perform Quick Sort:

  1. Choose a pivot element from the array. Typically, the pivot element is chosen as the last element in the array.

  2. Partition the array into two subarrays: the left subarray contains all elements smaller than the pivot, and the right subarray contains all elements greater than or equal to the pivot.

  3. Recursively apply the Quick Sort algorithm to the left and right subarrays.

def quicksort(arr)
  return arr if arr.size <= 1

  # Pick the pivot element
  pivot = arr.last

  # Partition the array into two subarrays
  left = []
  right = []
  arr[0...-1].each do |x|
    if x < pivot
      left << x
    else
      right << x
    end
  end

  # Recursively apply quicksort to the left and right subarrays
  return quicksort(left) + [pivot] + quicksort(right)
end

# Example usage
arr = [7, 2, 9, 4, 1, 8, 5, 6, 3]
sorted_arr = quicksort(arr)
puts sorted_arr.inspect
# Output: [1, 2, 3, 4, 5, 6, 7, 8, 9]

In the above code, the quicksort function takes an array arr as input and returns a sorted array. If the array size is less than or equal to 1, it returns the input array as it is. Otherwise, it picks the last element in the array as the pivot, partitions the array into two subarrays using the pivot, and then recursively applies the Quick Sort algorithm to the left and right subarrays. Finally, it concatenates the sorted left subarray, pivot, and sorted right subarray, and returns the sorted array.

Heap sort

Heap Sort is a comparison-based sorting algorithm that uses a binary heap data structure. It first builds a heap from the input data and then repeatedly extracts the maximum element from the heap, which results in a sorted array. The time complexity of Heap Sort is O(n*log(n)).

Here are the detailed steps to perform Heap Sort:

  1. Build a max heap from the input array. A max heap is a binary tree where the value of each parent node is greater than or equal to the values of its children.

  2. Extract the maximum element from the heap and place it at the end of the array.

  3. Heapify the remaining elements of the heap.

  4. Repeat steps 2 and 3 until the heap is empty.

def heapsort(arr)
  n = arr.length

  # Build a max heap from the input array
  ((n / 2) - 1).downto(0) do |i|
    heapify(arr, n, i)
  end

  # Extract the maximum element from the heap and place it at the end of the array
  (n - 1).downto(1) do |i|
    arr[0], arr[i] = arr[i], arr[0]
    heapify(arr, i, 0)
  end

  return arr
end

# Heapify a subtree rooted with node i, which is an index in arr. n is the size of the heap
def heapify(arr, n, i)
  largest = i
  l = (2 * i) + 1
  r = (2 * i) + 2

  if l < n && arr[l] > arr[largest]
    largest = l
  end

  if r < n && arr[r] > arr[largest]
    largest = r
  end

  if largest != i
    arr[i], arr[largest] = arr[largest], arr[i]
    heapify(arr, n, largest)
  end
end

# Example usage
arr = [7, 2, 9, 4, 1, 8, 5, 6, 3]
sorted_arr = heapsort(arr)
puts sorted_arr.inspect
# Output: [1, 2, 3, 4, 5, 6, 7, 8, 9]

In the above code, the heapsort function takes an array arr as input and returns a sorted array using Heap Sort. It first builds a max heap from the input array using the heapify function. The heapify function takes an array arr, the size of the heap n, and an index i as input and heapifies a subtree rooted with node i. It then repeatedly extracts the maximum element from the heap and places it at the end of the array, and then heapifies the remaining elements of the heap. Finally, it returns the sorted array.

Radix sort

Radix Sort is a sorting algorithm that sorts data by digit positions. It sorts the data by comparing digits in the same position from each item to be sorted. Radix Sort is usually used to sort numbers, but it can also be used to sort strings or other data types that can be sorted by their individual characters.

Here are the detailed steps to perform Radix Sort:

  1. Find the maximum number in the input array and count the number of digits in it.

  2. Starting from the least significant digit (rightmost), sort the input array using counting sort.

  3. Move to the next digit (towards the left) and sort the input array again using counting sort.

  4. Repeat step 3 until all digits have been sorted.

def radixsort(arr)
  max_value = arr.max
  num_digits = Math.log10(max_value).to_i + 1

  num_digits.times do |d|
    counting_sort(arr, d)
  end

  arr
end

# Sort the input array by digit d using counting sort
def counting_sort(arr, d)
  n = arr.length
  counts = Array.new(10, 0)
  output = Array.new(n)

  # Count the number of occurrences of each digit in arr
  arr.each do |x|
    digit = (x / (10 ** d)) % 10
    counts[digit] += 1
  end

  # Modify counts to contain the number of elements less than or equal to each digit
  (1...10).each do |i|
    counts[i] += counts[i - 1]
  end

  # Build the output array by placing each element in its correct sorted position
  (n - 1).downto(0) do |i|
    x = arr[i]
    digit = (x / (10 ** d)) % 10
    output[counts[digit] - 1] = x
    counts[digit] -= 1
  end

  # Copy the output array back to the input array
  arr.each_index do |i|
    arr[i] = output[i]
  end
end

# Example usage
arr = [170, 45, 75, 90, 802, 24, 2, 66]
sorted_arr = radixsort(arr)
puts sorted_arr.inspect
# Output: [2, 24, 45, 66, 75, 90, 170, 802]

In the above code, the radixsort function takes an array arr as input and returns a sorted array using Radix Sort. It first finds the maximum value in the input array and counts the number of digits in it. It then sorts the input array by digit positions starting from the least significant digit using the counting_sort function. The counting_sort function takes an array arr and a digit position d as input and sorts the input array by digit d using counting sort. Finally, it returns the sorted array.

Conclusion

In conclusion, sorting algorithms are an essential part of computer science and are used extensively in a wide range of applications. There are many different types of sorting algorithms, each with their strengths and weaknesses, which make them suited for different use cases. Some algorithms like Quick Sort are generally faster than others, while others like Radix Sort are specialized for certain types of data.

It's important to choose the right sorting algorithm for the job and to understand the performance characteristics of each algorithm. The time and space complexity of a sorting algorithm are important factors to consider when choosing an algorithm for a particular task. Additionally, some sorting algorithms like Merge Sort and Heap Sort are stable, meaning that they preserve the relative order of equal elements in the input array, while others like Quick Sort are not.

Overall, a good understanding of sorting algorithms is an important tool in a programmer's toolbox, and choosing the right algorithm for a given task can have a significant impact on the performance of an application.

...



๐Ÿ“Œ Sorting Algorithms with Ruby


๐Ÿ“ˆ 46.1 Punkte

๐Ÿ“Œ 10 Best Sorting Algorithms Explained


๐Ÿ“ˆ 34.8 Punkte

๐Ÿ“Œ AlphaDev discovers faster sorting algorithms


๐Ÿ“ˆ 34.8 Punkte

๐Ÿ“Œ AlphaDev discovers faster sorting algorithms


๐Ÿ“ˆ 34.8 Punkte

๐Ÿ“Œ Different Sorting Algorithms and their Implementation


๐Ÿ“ˆ 34.8 Punkte

๐Ÿ“Œ Algorithms 101: How to use graph algorithms


๐Ÿ“ˆ 28.34 Punkte

๐Ÿ“Œ private_address_check Ruby Gem bis 0.4.x auf Ruby Socket TOCTOU Race Condition


๐Ÿ“ˆ 22.61 Punkte

๐Ÿ“Œ Ruby After 25 Years by the Creator of Ruby


๐Ÿ“ˆ 22.61 Punkte

๐Ÿ“Œ espeak-ruby Gem up to 1.0.2 on Ruby lib/espeak/speech.rb speak/save/bytes/bytes_wav privilege escalation


๐Ÿ“ˆ 22.61 Punkte

๐Ÿ“Œ yajl-ruby gem 1.3.0 on Ruby yajl_encode.c Yajl::Parser.new.parse denial of service


๐Ÿ“ˆ 22.61 Punkte

๐Ÿ“Œ private_address_check Ruby Gem up to 0.4.x on Ruby Socket TOCTOU race condition


๐Ÿ“ˆ 22.61 Punkte

๐Ÿ“Œ espeak-ruby Gem bis 1.0.2 auf Ruby lib/espeak/speech.rb speak/save/bytes/bytes_wav erweiterte Rechte


๐Ÿ“ˆ 22.61 Punkte

๐Ÿ“Œ ruby-grape Gem on Ruby format cross site scripting


๐Ÿ“ˆ 22.61 Punkte

๐Ÿ“Œ London Trust Media Private Internet Access v82 on Linux /opt/pia/ruby/64/ruby privilege escalation


๐Ÿ“ˆ 22.61 Punkte

๐Ÿ“Œ yajl-ruby gem 1.3.0 auf Ruby yajl_encode.c Yajl::Parser.new.parse Denial of Service


๐Ÿ“ˆ 22.61 Punkte

๐Ÿ“Œ Pixar ruby-jss Gem up to 1.5.x on Ruby XML Document Remote Privilege Escalation


๐Ÿ“ˆ 22.61 Punkte

๐Ÿ“Œ Semiology in Ruby (What are Ruby Symbols) ?


๐Ÿ“ˆ 22.61 Punkte

๐Ÿ“Œ ruby-grape Gem auf Ruby format Cross Site Scripting


๐Ÿ“ˆ 22.61 Punkte

๐Ÿ“Œ Future-istic Sorting with Dart (Dart Conference 2018)


๐Ÿ“ˆ 20.62 Punkte

๐Ÿ“Œ Was sorting some old papers and found this.


๐Ÿ“ˆ 20.62 Punkte

๐Ÿ“Œ Sorting through the old mans stuff. How things change in 10 years


๐Ÿ“ˆ 20.62 Punkte

๐Ÿ“Œ Better sorting for games and apps coming to Xbox One


๐Ÿ“ˆ 20.62 Punkte

๐Ÿ“Œ How to remove duplicate lines from files with awk without sorting or changing their order


๐Ÿ“ˆ 20.62 Punkte

๐Ÿ“Œ Trump Faces Off With the WHO: Sorting Through the Allegations


๐Ÿ“ˆ 20.62 Punkte

๐Ÿ“Œ GNOME Music 3.22 to Offer Better Sorting of Songs in Albums and Artists Views


๐Ÿ“ˆ 20.62 Punkte

๐Ÿ“Œ #0daytoday #OXID eShop 6.3.4 - (sorting) SQL Injection Vulnerability [webapps #exploits #Vulnerability #0day #Exploit]


๐Ÿ“ˆ 20.62 Punkte

๐Ÿ“Œ [webapps] OXID eShop 6.3.4 - 'sorting' SQL Injection


๐Ÿ“ˆ 20.62 Punkte

๐Ÿ“Œ Python Documentation 2/3 Sorting Incorrect Calculation


๐Ÿ“ˆ 20.62 Punkte

๐Ÿ“Œ Sorting Thoughts (64-bit)


๐Ÿ“ˆ 20.62 Punkte

๐Ÿ“Œ Sorting Thoughts


๐Ÿ“ˆ 20.62 Punkte

๐Ÿ“Œ Sorting Thoughts


๐Ÿ“ˆ 20.62 Punkte

๐Ÿ“Œ GNOME Music 3.22 to Offer Better Sorting of Songs in Albums and Artists Views


๐Ÿ“ˆ 20.62 Punkte

๐Ÿ“Œ Feedback Hub gets new achievement page, makes sorting feedback easier


๐Ÿ“ˆ 20.62 Punkte

๐Ÿ“Œ How to create folders in Gmail for sorting messages


๐Ÿ“ˆ 20.62 Punkte

๐Ÿ“Œ How to create folders in Gmail for sorting messages


๐Ÿ“ˆ 20.62 Punkte











matomo