Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Для новичков > Сортировка массива.

Автор: Soeth 15.2.2012, 17:37

Написал ф-ю сортировки массива методом Шейкера.
Собственно проблема в том, что программа впадает в бесконечный цикл после того, как весь массив отсортирован, L и R не пересекаются.
Может подскажете в чём проблема?
S,P - количество сравнений\ перестановок.
N - длина массива.
L - левая граница, R - правая.
L1,R1 - индикаторы последней перестановки с левой\правой сторон.

Код


int SheikerSort(int arr[], int N, int &S, int &P)
{
    int L = 0, R = N - 1,L1 = 0, R1 = 0, buff;
    while(R != L){
        for(L = R1; L <= R - 1; L++){
            S++;
            if(arr[L] > arr[L + 1]){
                buff = arr[L];
                arr[L] = arr[L + 1];
                arr[L + 1] = buff;
                L1 = L;
                P++;
            }
        }
        L = R1;
        for(R = L1; R >= L + 1; R--){
            S++;
            if(arr[R] < arr[R - 1]){
                buff = arr[R];
                arr[R] = arr[R - 1];
                arr[R - 1] = buff;
                R1 = R;
                P++;
            }
        }
        R = L1;
    }
    return 0;
}

Автор: feodorv 15.2.2012, 18:44

Цитата(Soeth @ 15.2.2012, 17:37

)

программа впадает в бесконечный цикл

Ни фига не циклится:

Код


#include <stdio.h>

int SheikerSort(int *arr, int N, int *S, int *P)
{
    int L = 0, R = N - 1,L1 = 0, R1 = 0, buff;
    while(R != L){
        for(L = R1; L <= R - 1; L++){
            (*S)++;
            printf( "L=%d\n", L);
            if(arr[L] > arr[L + 1]){
                buff = arr[L];
                arr[L] = arr[L + 1];
                arr[L + 1] = buff;
                L1 = L;
                (*P)++;
            }
        }
        L = R1;
        for(R = L1; R >= L + 1; R--){
            (*S)++;
            printf( "R=%d\n", R);
            if(arr[R] < arr[R - 1]){
                buff = arr[R];
                arr[R] = arr[R - 1];
                arr[R - 1] = buff;
                R1 = R;
                (*P)++;
            }
        }
        R = L1;
        printf( "L=%d R=%d\n", L, R);
    }
    return 0;
}

int main( void )
{
  int i;
  int m[201];
  int S, P;

  S = P = 0;
  for( i = 0; i < 201; i++) m[i] = 100-i;
  SheikerSort( m, 201, &S, &P);
  printf( "S = %d, P = %d\n", S, P);

  S = P = 0;
  for( i = 0; i < 201; i++) m[i] = 100-i%2;
  SheikerSort( m, 201, &S, &P);
  printf( "S = %d, P = %d\n", S, P);

  return 0;
}

Или дайте данные, на которых циклится...

Автор: Soeth 15.2.2012, 21:01

Проверял на различных случайных массивах различных структур, но как пример:

Код


int main()
{
    int arr[8] = {44, 55, 12, 42, 94, 18, 06, 67};
    int N = 8, S = 0, P = 0;
    SheikerSort(arr,N,S,P);

        cout << "Comparisons: " << S << endl;
        cout << "Permutations: " << P << endl;

    for (int i=0; i <= N-1; i++){
        cout << arr[i] << endl;
    }

    system("pause");

}

В бесконечный цикл while входит при L = 3 и R = 4.

Автор: feodorv 16.2.2012, 02:42

Не понятно, согласно какому описанию алгоритма Вы составили программу... На каждом шаге должны меняться либо L, либо R (иначе - зацикливание). При отсортированном списке обменов не происходит, и L и R так и остаются отличающимися на 1.

Как вариант решения:

Цитата

вводится достаточное прерывание проходов, если на очередном проходе обнаруживается, что нет ни одного обмена.

Цитата взята http://gubsky.ru/study/5/soad/sh/5.htm

Автор: Soeth 16.2.2012, 10:08

Составлял согласно тому, как препод в универе объяснял.
Благодарю за помощь, булеанская переменная поможет. )