Reputation: 1

The Fastest Sorting function

In C++ I need to sort the arrays that I had written with a fast speed as possible, My Question is What is the Best and the Fastest sorting function to use? Or Just Make One with MY self?

Upvotes: 0

Answers (11)

Mohd. Anas Siddiqui

Reputation: 743

This code uses the QuickSort algorithm, which has an average time complexity of O(nlogn) and is generally considered to be one of the fastest sorting algorithms. Additionally, the swap() function is used to swap elements in the array, which is typically faster than implementing a swap function manually.

#include <iostream>
#include <algorithm>

using namespace std;

// Function to partition the array
int partition(int arr[], int low, int high) {
    int pivot = arr[high]; // Choose the last element as the pivot
    int i = low - 1;
    for (int j = low; j <= high - 1; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]);
    return i + 1;
}

// QuickSort function
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high); // pi is partitioning index
        quickSort(arr, low, pi - 1); // Sort the elements before partition
        quickSort(arr, pi + 1, high); // Sort the elements after partition
    }
}

// Driver code to test the sorting function
int main() {
    int arr[] = { 64, 25, 12, 22, 11 };
    int n = sizeof(arr) / sizeof(arr[0]);

    quickSort(arr, 0, n - 1);

    cout << "Sorted array: ";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    return 0;
}

Upvotes: 0

sandy101

Reputation: 3427

sorting algorithms basically depend on the requirement of the programmer .the size of the array (to be sorted ) is highly matters in this case . so for instance you can check out the link and know about the efficiency of the various sorting algorithms

http://www.durangobill.com/SortAlgorithms/Sort_Algorithms.html

Upvotes: 0

Timo Geusch

Reputation: 24351

I wouldn't write my own sort unless your requirements are extremely specific. Use the ones that are part of the standard library, they are well tested and unlikely to trip you up when it comes to boundary conditions.

That said, if you have an array and you need the contents sorted in a specific order every time (as opposed to being able to resort it by various arbitrary criteria) I would think that you are using the wrong container and might want to look into one that automatically sorts the elements on insert, for example a std::set or std::multiset.

Upvotes: 0

p.marino

Reputation: 6252

While qsort alone could very well be the safer option, if you are really desperate for speed you have to give a little bit more about the specific case.

In general, sort methods are considered "better" when they scale well for large dataset and work gracefully with general cases without having pathologically bad results for corner cases (like sorting an almost completely sorted array, or an array which is in reverse order).

So while you look at sorting methods in general (plenty of literature) keep in mind if your specific applications has to deal with plenty of small (say 10-12 items) arrays. Or very large array. Or if memory is limited. Or if the compare function is extremely expensive.

Upvotes: 0

jonnystoten

Reputation: 7133

Whatever you do, don't try to make your own sorting algorithm unless you really know what you're doing, and you have some very unusual requirements.

Upvotes: 3

Nils Pipenbrinck

Reputation: 86343

Use Radix- or Bucket sort if your keys are small in size (integers for example) and your sort typical more than 500 items.

Otherwise use introsort: http://en.wikipedia.org/wiki/Introsort You may want to try std::sort as well. Usually it is just an implementation of introsort.

Upvotes: 3

Engo

Reputation: 1

Yes,Quicksort is the best, but if you have a new good algorithm and it is good for your current situation, Just write your own.

Upvotes: -2

Pontus Gagge

Reputation: 17258

Use the std::sort function which typically defaults to quicksort (but deals with the ugly edge cases of e.g. a fully sorted array taking O(n^2) time).

Then measure the speed: if that's not good enough, describe details (e.g. how large are your arrays, what data do they contain, will there be a lot of equivalent elements and is stability important), and get further advice. Don't, for the love of Knuth, implement your own sorting function unless you have some extremely unique requirements!

Upvotes: 20