Quicksort is a sorting algorithm developed by Tony Hoare that, on average, makes O(nlog n) comparisons to sort n items. In the worst case, it makes O(n²) comparisons, though this behavior is rare. Quicksort is often faster in practice than other O(nlog n) algorithms.^[1] Additionally, quicksort's sequential and localized memory references work well with a cache. Quicksort can be implemented with an in-place partitioning algorithm, so the entire sort can be done with only O(log n) additional space.^[2]
Quicksort (also known as "partition-exchange sort") is a comparison sort and, in

Visualization of the quicksort algorithm. The horizontal lines are pivot values.
Class	Sorting algorithm
Worst case performance	O(n2)
Best case performance	O(n log n)
Average case performance	O(n log n)
Worst case space complexity	O(n) (naive) O(log n) (Sedgewick 1978)

Quicksort is a sorting algorithm developed by Tony Hoare that, on average, makes

Merge sort

Merge sort is an O(n log n) comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the implementation preserves the input order of equal elements in the sorted output. Merge sort is a divide and conquer algorithm that was invented by John von Neumann in 1945.[1] A detailed description and analysis of bottom-up mergesort appeared in a report by Goldstine and Neumann as early as 1948.[2]		An example of merge sort. First divide the list into the smallest unit (1 element), then compare each element with the adjacent list to sort and merge the two adjacent list. Finally all the elements are sorted and merged.
Class	Sorting algorithm
Data structure	Array
Worst case performance	O(n log n)
Best case performance	O(n log n) typical, O(n) natural variant
Average case performance	O(n log n)
Worst case space complexity	O(n) auxiliary

Bucket sort

 Bucket sort, or bin sort, is a sorting algorithm that works by partitioning an array into a number of buckets. Each bucket is then sorted individually, either using a different sorting algorithm, or by recursively applying the bucket sorting algorithm. It is a distribution sort, and is a cousin of radix sort in the most to least significant digit flavour. Bucket sort is a generalization of pigeonhole sort. Since bucket sort is not a comparison sort, the O(n log n) lower bound is inapplicable. The computational complexity estimates involve the number of buckets.
Bucket sort works as follows:

1. Set up an array of initially empty "buckets."
2. Scatter: Go over the original array, putting each object in its bucket.
3. Sort each non-empty bucket.
4. Gather: Visit the buckets in order and put all elements back into the original array.

Elements are distributed among bins

Then, elements are sorted within each bin

Shellsort

From Wikipedia, the free encyclopedia

  (Redirected from Shell Sort)

Shellsort

Shellsort with gaps 23, 10, 4, 1 in action.
Class	Sorting algorithm
Data structure	Array
Worst case performance	depends on gap sequence
Best case performance	O(N)
Average case performance	depends on gap sequence
Worst case space complexity	O(1)

Shellsort, also known as Shell sort or Shell's method is an in-place comparison sort. It generalizes an exchanging sort, such as insertion or bubble sort, by allowing the comparison and exchange of elements that lie far apart.^{[citation needed]} Its first version was published by Donald Shell in 1959.^[1][2] 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.

[edit] Description

Shellsort is a multi-pass algorithm. Each pass is an insertion sort of the sequences consisting of every h-th element for a fixed gap h (also known as the increment). This is referred to as h-sorting.
An example run of Shellsort with gaps 5, 3 and 1 is shown below.

Insertion sort

From Wikipedia, the free encyclopedia

  (Redirected from Insertion Sort)

Insertion sort

Example of insertion sort sorting a list of random numbers.
Class	Sorting algorithm
Data structure	Array
Worst case performance	О(n2)
Best case performance	O(n)
Average case performance	О(n2)
Worst case space complexity	О(n) total, O(1) auxiliary

Insertion sort is a simple sorting algorithm: a comparison sort in which the sorted array (or list) is built one entry at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. However, insertion sort provides several advantages:

• Simple implementation
• Efficient for (quite) small data sets
• Adaptive (i.e., efficient) for data sets that are already substantially sorted: the time complexity is O(n + d), where d is the number of inversions
• More efficient in practice than most other simple quadratic (i.e., O(n²)) algorithms such as selection sort or bubble sort; the best case (nearly sorted input) is O(n)
• Stable; i.e., does not change the relative order of elements with equal keys
• In-place; i.e., only requires a constant amount O(1) of additional memory space
• Online; i.e., can sort a list as it receives it

When humans manually sort something (for example, a deck of playing cards), most use a method that is similar to insertion sort.^[1]

Contents  [hide]  1 Algorithm 2 Best, worst, and average cases 3 Comparisons to other sorting algorithms 4 Variants 4.1 List insertion sort code in C 5 References 6 External links

[edit] Algorithm

An example of insertion sort. Check each element and put it in the right place in the sorted list.

Every repetition of insertion sort removes an element from the input data, inserting it into the correct position in the already-sorted list, until no input elements remain. The choice of which element to remove from the input is arbitrary, and can be made using almost any choice algorithm.
Sorting is typically done in-place. The resulting array after k iterations has the property where the first k + 1 entries are sorted. In each iteration the first remaining entry of the input is removed, inserted into the result at the correct position, thus extending the result:

becomes

Selection Sort

Selection sort performs sorting by repeatly putting the largest element in the unprocessed portion of the array to the end of the this unprocessed portion until the whole array is sorted.
The following teaching aid illstrates how the selection sort works.

Selection Sort Animation

In computer science, a Selection sort is a sorting algorithm, specifically an in-place comparison sort. It has O(n²) time complexity, making it inefficient on large lists, and generally performs worse than the similar insertion sort. Selection sort is noted for its simplicity, and also has performance advantages over more complicated algorithms in certain situations, particularly where auxiliary memory is limited.

bubble sort

From Wikipedia…

Bubble sort is a simple sorting algorithm that works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping 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. The algorithm gets its name from the way smaller elements “bubble” to the top of the list. Because it only uses comparisons to operate on elements, it is a comparison sort.

[ad code=1]
[ad code=1]

Algorithm

1. Iterates thru every element of the array, starting with the first 2 elements.
2. If left element is bigger than right element, swap them.
3. Repeat step #1 and #2 until there are no more swaps.

[ad code=1]
[ad code=1]

Block Diagram