技事録

大学で人工知能の研究しています.

クイックソート

C言語クイックソートです.

#include <stdio.h>
#include <stdlib.h>

#define swap(type, x ,y) do {type t = x; x = y; y = t;} while(0)

void __quick_sort ( int* a, int left, int right )
{
	int pl, pr;
	int mid;
	int pivot;
    
	if ( left < right )
	{
		// 中央の要素をpivotとする.
		mid = ( left + right ) / 2;
        
		pivot = a[mid];
        
		pl = left;
		pr = right;
        
		while ( pl <= pr )
		{
			while ( a[pl] < pivot ) { ++pl; } // 左側のポインタの移動.
			while ( a[pr] > pivot ) { --pr; } // 右側のポインタの移動.
            
			if ( pl >= pr ) { break; }
            
			if ( pl < pr )
			{
				swap ( int, a[pl], a[pr] );
                
				pl++;
				pr--;
			}
		}
        
		if ( left < pl - 1 ) // 軸の左側に要素を2つ以上あれば再帰.
		{
			__quick_sort ( a, left, pl - 1 );
		}
		if ( pr + 1 < right ) // 軸の左側に要素を2つ以上あれば再帰.
		{
			__quick_sort ( a, pr + 1, right );
		}
        
	}
}

void quick_sort ( int* a, int size )
{
	__quick_sort ( a, 0, size - 1 );
}


int main ( void )
{
	int a[] = { 10, 20, 30, 5, 26, 2, 87, 12, 22, 7 };
	int size = sizeof ( a ) / sizeof ( a[0] );
    
	printf ( "ソート前の要素の表示\n" );
	for ( int i = 0; i < size; ++i )
	{
		printf ( "%d ", a[i] );
	}
	printf ( "\n" );
    
	quick_sort ( a, size );
    
	printf ( "ソート前の要素の表示\n" );
	for ( int i = 0; i < size; ++i )
	{
		printf ( "%d ", a[i] );
	}
	printf ( "\n" );
}