forum.boolean.name - 2 алгоритма сортировки массива

forum.boolean.name (http://forum.boolean.name/index.php)

- C++ (http://forum.boolean.name/forumdisplay.php?f=22)

- - 2 алгоритма сортировки массива (http://forum.boolean.name/showthread.php?t=14968)

2 алгоритма сортировки массива

Еще раз здравствуйте, форумчане. Я хотел бы узнать, какой из алгоритмов сортировки быстрее. Сам я, к сожалению, еще работать со временем еще не научился, и поэтому не могу определить скорость выполнения операций. Интересует именно скорость выполнения функции sort.

Код:

#include <iostream>

using namespace std;



void sort(int arr[], int L);

void swap(int *p_1, int *p_2);



int main() {

        int i;

    int arr[5]={1, 100, 3, 2, 6};



        sort(arr, 5);

        for (i=0; i<5; i++) {cout << i << " = " << arr[i] << endl;}



    return 0;

}



void sort(int arr[], int L) {

        if (L<2) {return;}



        int i, k;

        int current_n=arr[0];



        for (i=1; i<L; i++) {

                if (arr[i]<current_n) {

                        swap(&arr[i], &arr[i-1]);

                        for (k=i-1; k>0; k--) {

                                if (arr[k]<arr[k-1]) {

                                        swap(&arr[k], &arr[k-1]);

                                } else {

                                        break;

                                }

                        }

                }

                current_n=arr[i];

        }

}



void swap(int *p_1, int *p_2) {

        int tmp=*p_1;

        *p_1=*p_2;

        *p_2=tmp;

}

Код:

#include <iostream>

usingnamespace std;



void sort(int n);



int main() {

        int a[10];

        int i;



        for (i=0; i<10; i++) {

                cout << "Enter array element #" << i << ": ";

                cin >> a[i];

        }



        sort(a, 10);

        cout << "Here are all the array elements, sorted:" << endl;

        for (i=0; i<10; i++) {

                cout << a[i] << " ";

        }



        return 0;

}



void sort(int a[], int n) {

        int i, j, low;

        for (i=0; i<n-1; i++) {

                low=i;

                for (j=i+1; j<n; j++) {

                        if (a[j]<a[low]) {

                                low=j;

                        }

                }

                if (i!=low) {

                        swap(&a[i], &a[low]);

                }

        }

}



void swap(int *p1, int *p2) {

        int temp=*p1;

        *p1=*p2;

        *p2=*temp;

}

Заранее благодарен.

Ответ: 2 алгоритма сортировки массива

Первый исходник:
- 10000 объектов
- 650 milliseconds
Второй:
- В swap ругался на *p2=*temp; (error C2100: illegal indirection)
- Поставил swap от первого
- 10000 объектов
- 203 milliseconds
Как видишь, второй шустрее.
---
Насчет времени,
Инициализация:

Код:

#include <ctime>

Функция (аналог Millisecs() в Blitz3d):

Код:

clock();

Ответ: 2 алгоритма сортировки массива

Большое спасибо!
Интересно, конечно, засчет чего второй вариант функции работает быстрее. Наверное, это из-за многочисленных вызовов функции swap.

Ответ: 2 алгоритма сортировки массива

Выяснил, что I-ый алгоритм гораздо стабильнее, а быстрота выполнения второго зависит от того, как в нем расставлены цифры. По сути оба из них схожи, но быстрота II-го и в правду достигается засчет малого количества вызовов функции swap.