Программа quicksort предоставляет частично отсортированный вывод

Question

Ниже простого быстрого кода сортировки с последним элементом в виде сводной таблицы почти работает, но кроме последнего элемента не удается отсортировать. Любые мысли, когда эта программа пошла не так?

Вот результат:

$a.out 
4 3 5 2 1 3 2 3 //input 
1 2 2 3 3 3 5 4 //output 

Простая замена выглядит тонкой

void swap (int* a, int* b) 
{ 
    int t = *a; 
    *a = *b; 
    *b = t; 
} 

Hmm..fine слишком ..may вопрос с end?

int partition(int a[],int start,int end){ 
int pivot = a[end]; 
int pindex=start;int i; 

    for (i=start; i <= end-1; i++){ 
     if (a[i] <= pivot){ 
      swap(&a[i],&a[pindex]);pindex++; 
     } 
    } 
    swap(&a[pindex],&a[pivot]); 
    return (pindex + 1); 
} 

Несомненно хорошо выглядит.

void quicksort(int a[],int start,int end){ 
int pindex; 

    if (start < end){ 
     pindex = partition(a,start,end-1); 
     quicksort(a,start,pindex-1); 
     quicksort(a,pindex+1,end); 
    } 
} 

Простой главный вызов

int main(){ 
    int a[8] = {4, 3, 5, 2, 1, 3, 2, 3}; 
    int i=0; 

    for(i=0;i<8;i++) 
     printf(" %d", a[i]); 
    quicksort(a,0,8); 
    printf("\n"); 
    for(i=0;i<8;i++) 
     printf(" %d", a[i]); 
} 

Answer 1

Пожалуйста, ознакомьтесь с partition функцию.

Она должна возвращать

return pindex; 

вместо pindex+1.

Потому что, просто взять следующий случай:

1 2 3 4 5

Как 5 выбран в качестве опоры, он должен вернуть 4, не 5 как индекс поворота.

Проверьте для инварианта, что pindex должен находиться между началом и концом (оба включительно). Если ось вращения должна лежать в конце, она не должна заканчиваться.

Как правило, раздел начинается с обоих концов. Вы начинаете его с одного конца. Постарайтесь сделать это и для достижения цели. В противном случае, в 1 2 3 4 5, вы будете держать подкачку с тем же элементом (1 с 1, 2 с 2 и так далее).

А в разделе:

swap(&a[pindex],&a[pivot]); 

должен быть

swap(&a[pindex],&a[end]); 

pivot было значение, а не индекс.

Еще одно изменение, вам требуется quicksort,

if (start < end){ 
    pindex = partition(a,start,end-1); 
    //As here index is one past last, so make it start..pindex 
    quicksort(a,start,pindex); 
    quicksort(a,pindex+1,end); 
    } 

Ваша функция секционирования должна быть

int partition(int a[],int start,int end){ 

int pivot = a[end]; 
int pindex=start;int i; 

for (i=start; i <= end-1; i++){ 
    if (a[i] <= pivot){ 
     swap(&a[i],&a[pindex]);pindex++; 
     } 
    } 

    swap(&a[pindex],&a[end]); 
    return (pindex); 
} 

https://en.wikipedia.org/wiki/Quicksort#Lomuto_partition_scheme См. Эта схема разделов используется здесь.

Answer 2

Ваша программа не работает, если кто-то вводит отрицательные числа. Почему вы так усложняете?

Вот простая сортировка:

#include <stdio.h> 

void bubble_sort(int *array, int length){ 
    int i,j, k, temp; 

    for (i = 0 ; i < length-1; i++){ 
    for (k = 0 ; k < length-i-1; k++){ 
     if (array[k] > array[k+1]){ 
     temp = array[k]; 
     array[k] = array[k+1]; 
     array[k+1] = temp; 
     } 
    } 
    } 

    printf("The sorted Array List:\n\n"); 

    for (j = 0 ; j < length ; j++){ 
    printf("%d ", array[j]); 
    } 
} 

int main(void){ 
    int array[8] = {4, 3, 5, 2, 1, -1, 2, 3}; 
    int length = sizeof array/sizeof array[0]; 

    bubble_sort(array, length); 
    printf("\n"); 

    return 0; 
} 

Выход:

-1 1 2 2 3 3 4 5

Answer 3

Хорошо пара изменений

В doptimusprime заостренный возврат pindex

int partition(int a[],int start,int end){ 
    int pivot = a[end]; 
    int pindex=start;int i; 
    for (i=start; i <= end-1; i++){ 
     if (a[i] <= pivot){ 
      swap(&a[i],&a[pindex]);pindex++; 
     } 
    } 
    swap(&a[pindex],&a[end]); 
    return (pindex); 
} 

Настройте функцию QuickSort соответственно

void quicksort(int a[],int start,int end){ 
    int pindex; 

    if (start < end){ 
     pindex = partition(a,start,end-1); 
     quicksort(a,start,pindex); // no pindex-1 
     quicksort(a,pindex+1,end); 
    } 
}