Когда вы пишете функцию, протестируйте ее перед использованием в программе.
Функция QuickSortPartition явно неправильная.
Рассмотрим следующую демонстрационную программу с реализацией вашей функции
#include <stdio.h>
int QuickSortPartition(int *array, int begin, int end){
int pivot = array[end];
int i = (begin - 1), j = 0;
for (j = begin; j <= end - 1; j++) {
if (array[j] <= pivot) {
i++;
array[i] = array[j];
}
}
array[i + 1] = array[end];
return (i + 1);
}
int main( void )
{
int a[] = { 5, 4, 2, 1, 3 };
const size_t N = sizeof( a ) / sizeof( *a );
for ( size_t i = 0; i < N; i++ ) printf( "%d ", a[i] );
putchar( '\n' );
QuickSortPartition( a, 0, ( int )( N - 1 ) );
for ( size_t i = 0; i < N; i++ ) printf( "%d ", a[i] );
putchar( '\n' );
}
Его выход
5 4 2 1 3
2 1 3 1 3
Вам нужно поменять значения в функции вместо простого присваивания. Например
#include <stdio.h>
size_t QuickSortPartition( int *array, size_t begin, size_t end )
{
const int pivot = array[end];
size_t i = begin - 1;
for ( size_t j = begin; j < end; j++ )
{
if ( array[j] <= pivot )
{
int tmp = array[++i];
array[i] = array[j];
array[j] = tmp;
}
}
int tmp = array[++i];
array[i] = array[end];
array[end] = tmp;
return i;
}
int main( void )
{
int a[] = { 5, 4, 2, 1, 3 };
const size_t N = sizeof( a ) / sizeof( *a );
for ( size_t i = 0; i < N; i++ ) printf( "%d ", a[i] );
putchar( '\n' );
size_t partition = QuickSortPartition( a, 0, N - 1 );
printf( "%zu: ", partition );
for ( size_t i = 0; i < N; i++ ) printf( "%d ", a[i] );
putchar( '\n' );
}
Его вывод
5 4 2 1 3
2: 2 1 3 4 5
Для индексов я использовал тип size_t (и вы должны сделать то же самое) вместо типа int.
А внутри функции QuickSortFunction вам нужно вызывать ее самому вместо функции QuickSortPartition.
void QuickSortFunction(int *array, size_t begin, size_t end){
if (begin < end) {
size_t pivot = QuickSortPartition(array, begin, end);
QuickSortFunction(array, begin, pivot - 1);
QuickSortFunction(array, pivot + 1, end);
}
}
Учтите, что эта инициализация в объявлении функции QuickSortPartition
int i = (begin - 1), j = 0;
^^^^^^^^^^^
это плохо. (Кажется, все копируют алгоритм из плохого примера :)). И функция неэффективна, когда все элементы меньше или равны значению pivot.
Также вы можете написать отдельную функцию, которая заменяет два элемента массива.
Ниже приведена демонстрационная программа, показывающая, как можно улучшить код функции QuickSortPartition.
#include <stdio.h>
void swap( int *a, int *b )
{
int tmp = *a;
*a = *b;
*b = tmp;
}
size_t QuickSortPartition( int *array, size_t begin, size_t end )
{
const int pivot = array[end];
size_t i = begin;
for ( size_t j = begin; j < end; j++ )
{
if ( array[j] <= pivot )
{
if ( i != j ) swap( &array[i], &array[j] );
++i;
}
}
if ( i != end ) swap( &array[i], &array[end] );
return i;
}
int main( void )
{
int a[] = { 5, 4, 2, 1, 3 };
const size_t N = sizeof( a ) / sizeof( *a );
for ( size_t i = 0; i < N; i++ ) printf( "%d ", a[i] );
putchar( '\n' );
size_t partition = QuickSortPartition( a, 0, N - 1 );
printf( "%zu: ", partition );
for ( size_t i = 0; i < N; i++ ) printf( "%d ", a[i] );
putchar( '\n' );
}