Data structures Ruby
Need help with Ruby?
Click the “chat” button below for chat support from the developer who created it, or find similar developers for support. TheAlgorithms #### Description

All algorithms implemented in Ruby (for education) 322 Stars 106 Forks 91 Commits 10 Opened issues # The Algorithms - Ruby

### All algorithms implemented in Ruby (for education)

These are for demonstration purposes only. For a full list of all algorithms, please see:DIRECTORY.md

## Sorting Algorithms

### Bogo Sort From Wikipedia: Bogo sort is a highly ineffective sorting function based on the generate and test paradigm. The function successively generates permutations of its input until it finds one that is sorted. It is not useful for sorting, but may be used for educational purposes, to contrast it with more efficient algorithms.

Properties * Unbounded (randomized version), O((n+1)!) (deterministic version) * Best case performance O(n) * Average case performance O((n+1)!)

### Bubble Sort From Wikipedia: Bubble sort, sometimes referred to as sinking sort, is a simple sorting algorithm that repeatedly steps through the list to be sorted, compares each pair of adjacent items and swaps them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted.

Properties * Worst case performance O(n^2) * Best case performance O(n) * Average case performance O(n^2)

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

Properties * Worst case performance O(n^2) * Best case performance O(n) * Average case performance O(n^2)

### Selection Sort From Wikipedia: The algorithm divides the input list into two parts: the sublist of items already sorted, which is built up from left to right at the front (left) of the list, and the sublist of items remaining to be sorted that occupy the rest of the list. Initially, the sorted sublist is empty and the unsorted sublist is the entire input list. The algorithm proceeds by finding the smallest (or largest, depending on sorting order) element in the unsorted sublist, exchanging (swapping) it with the leftmost unsorted element (putting it in sorted order), and moving the sublist boundaries one element to the right.

Properties * Worst case performance O(n^2) * Best case performance O(n^2) * Average case performance O(n^2)

### Shell Sort From Wikipedia: Shellsort, also known as Shell sort or Shell's method, is an in-place comparison sort. It can be seen as either a generalization of sorting by exchange (bubble sort) or sorting by insertion (insertion sort). The method starts by sorting pairs of elements far apart from each other, then progressively reducing the gap between elements to be compared. Starting with far apart elements, it can move some out-of-place elements into position faster than a simple nearest neighbor exchange. Donald Shell published the first version of this sort in 1959. The running time of Shellsort is heavily dependent on the gap sequence it uses. For many practical variants, determining their time complexity remains an open problem.

Properties * Worst case performance O(n^2) * Best case performance O(n log n) * Average case performance depends on gap sequence