Which one is the best and efficient sort?

Answer 1

There are a great many sorts, Mergesort and Quicksort being among the most popular. These both have on the order of n*log n expected case runtime, and while Quicksort can get as bad as n^2, this is unlikely due to most implementations using a random pivot.

If you can make the assumption that ONLY NUMBERS will be sorted, you can use RadixSort, which is the fastest known sort for numbers.

As for how to sort in particular programming languages, consult your local API (in C++ it is in the STL's "algorithm" include file).

Answer 2

The algorithm for selection sort is to treat the array as two subsets, with the sorted subset to the left and the unsorted subset to the right. Initially, the sorted subset is empty, but we repeatedly scan the unsorted subset for the smallest element and swap it with the first element in the unsorted subset, thus reducing the unsorted subset by one element each time. When there is only one element left in the unsorted subset we are done; we have already sorted every element that is less than or equal to the final element.

To implement this algorithm in C++, we can use the following template function:

template<class T>

void selection_sort(T a[], size_t size)

{

// an array of 0 or 1 elements can always be regarded as being sorted

if( size<2 )

return;

// traverse from left to right, stopping at the penultimate element

// (by the time we sort the penultimate element, the final element

// is guaranteed to be greater than or equal to it).

size_t last = size-1;

for( size_t index=0; index<last; ++index )

{

// assume the currently indexed element is the smallest element.

size_t smallest=index;

// locate an element that is smaller in the remainder of the array

for( size_t select=index+1; select<size; ++select )

if( a[select]<a[smallest] )

smallest=select;

// if we found a smaller element, swap it with the indexed element.

if( index!=smallest )

{

T temp=a[index];

a[index]=a[smallest];

a[smallest]=temp;

}

}

}

Answer 3

A sorting algorithm's efficiency is measured in the number of comparisons required to completely sort the elements in the array given a worse case scenario. The best sorting algorithms are rated at O(n), where n is the number of elements, and the worst algorithms are O(n2), with most algorithms falling in the O(n log n) range.

A best case algorithm, for example, takes about 20 comparisons when there are 20 elements, while a worst case algorithm would take about 400 comparisons for 20 elements.

Answer 4

Qucik sort or merge sort with time complexity O(n log n). In terms of both time and space Qucik sort is efficient.

Answer 5

Quick Sort