Быстрая сортировка, пропускающая один элемент - PullRequest
Новая
       6

Быстрая сортировка, пропускающая один элемент

0 голосов
/ 12 февраля 2020

Итак, сегодня я попытался реализовать быструю сортировку. Это почти работает, но как-то пропускает один элемент.

example : 5 2 8 2 3 4 1 5 7 -5 -1 -9 2 4 5 7 6 1 4

output : -5 -1 -9 1 2 2 3 2 1 4 4 4 5 5 5 6 7 7 8

В этом случае пропускается -9. Вот код функции. 


test = quicksort_asc(0,size,tab,size) // this is function call 

int quicksort_asc(int l, int r, int tab[], int tabSize) //l is first index, r is last index, tabSize is tabsize-1 generally
{
    int i,buffer,lim,pivot,flag=0;
    if(l == r)
        return 0;

    lim = l-1;
    pivot = tab[r-1];
    printf("pivot:%d\n",pivot);
    for (i = l; i <= r-1; ++i)
    {
        if(tab[i] < pivot) {
            lim++;
            buffer = tab[lim];
            tab[lim] = tab[i];
            tab[i] = buffer;
            flag = 1;
        }
    }
    if(flag == 0)
        return 0;
    buffer = tab[lim+1];
    tab[lim+1] = pivot;
    tab[r-1] = buffer;
    quicksort_asc(l,lim+1,tab,lim+1);//left side
    quicksort_asc(lim+1,tabSize,tab,tabSize);//right side

}

Это мой код счета длины массива. 100 - максимальный размер, 0 - стоп-значение. Количество это размер. 

 int count=0;
    for (int i = 0; i < 100; i++)
    {
        test = scanf("%d",&vec[i]);
        if(vec[i] == 0) break;
        count++;
    }
    return count;

1 Ответ

1 голос
/ 12 февраля 2020

Кажется, никто не спешит вам помочь. :)

Для начала последний параметр является избыточным. 

int quicksort_asc(int l, int r, int tab[], int tabSize);
                                           ^^^^^^^^^^^

Все, что вам нужно, это указатель на первый элемент массива и начальные и конечные индексы.

Также вместо типов int для индексов лучше использовать тип size_t. Однако, поскольку вы используете оператор выражения 

lim = l-1;

, тогда все будет в порядке, если индексы будут иметь тип int, хотя вы можете использовать другой подход без этого выражения выражения.

Таким образом, функция должна быть объявленным как 

void quicksort_asc( int tab[], int l, int r );

Переменная flag является избыточной. Когда он равен 0, это означает, что все элементы перед значением поворота больше или равны ему. Но, тем не менее, вы должны поменять значение сводки с первым элементом, который больше или равен сводке.

Этот l oop

for (i = l; i <= r-1; ++i)

имеет одну избыточную итерацию. Он должен быть установлен как 

for (i = l; i < r-1; ++i)

Этот вызов 

quicksort_asc(lim+1,tabSize,tab,tabSize);
              ^^^^^ ^^^^^^^

должен быть заменен на этот вызов 

quicksort_asc( lim + 2, r, tab );
               ^^^^^^^  ^^

, потому что значение разворота не включено в этот суб -array.

Вот демонстрационная программа. 

#include <stdio.h>

void quicksort_asc( int tab[], int l, int r )
{
    if ( l + 1 < r )
    {
        int lim = l - 1;

        int pivot = tab[r - 1];

        for ( int i = l; i < r - 1; ++i )
        {
            if ( tab[i] < pivot ) 
            {
                lim++;

                int tmp = tab[lim];
                tab[lim] = tab[i];
                tab[i] = tmp;
            }
        }

        tab[r - 1] = tab[lim + 1];
        tab[lim + 1] = pivot;
        quicksort_asc( tab, l, lim + 1 );
        quicksort_asc( tab, lim + 2, r );
    }       
}

int main(void)
{
    int a[] = { 5, 2, 8, 2, 3, 4, 1, 5, 7, -5, -1, -9, 2, 4, 5, 7, 6, 1, 4 };
    const int N = ( int )( sizeof( a ) / sizeof( *a ) );

    for ( int i = 0; i < N; i++ )
    {
        printf( "%d ", a[i] );
    }
    putchar( '\n' );

    quicksort_asc( a, 0, N );

    for ( int i = 0; i < N; i++ )
    {
        printf( "%d ", a[i] );
    }
    putchar( '\n' );

    return 0;
}

Его вывод 

5 2 8 2 3 4 1 5 7 -5 -1 -9 2 4 5 7 6 1 4 
-9 -5 -1 1 1 2 2 2 3 4 4 4 5 5 5 6 7 7 8
...