C# と VB.NET の質問掲示板

Jitta on the wayさんのご指摘により
char を　int に書き換えました。

お世話様です。
C言語で書いたクイックソートです
再帰で書いていますがループに変換した
コードはどうなるのでしょうか？

一応参考として知りたい程度です。
宜しくお願いします。


//
//	プログラム名
//	作成者
//	作成日
//
//	動作概要　クイックソート
//
#include <stdio.h>
#include "myutil.h"		//SWAPを使用するために参照

int  data[] = { 3,9,-8,5,9,1,-2,-5,13,0};


	int  n = sizeof(data)/sizeof(int);
	int  i;



void Quicksort(int *v,int left,int right)
{
	int i,last;
	
	if(left>=right)
		return;
		
	last=left;
	
	for(i=left+1;i <= right;i++)
	{
		if(v[i] <= v[left])
		{
			last++;
			SWAP(int,v[last],v[i]);
		}
	}	
		SWAP(int,v[left],v[last]);
		Quicksort(v ,left,last-1);
		Quicksort(v,last+1,right); 
}




int main()
{

	for(i=0;i<n;i++)
		printf("%d ",data[i]);　　//元の配列の確認
	printf("\n\n");

	// ポインタで記述
	int *p =data;
	
	for(i=0;i<n;i++)
		printf("%d  ",*(p+i));　　//元の配列の確認

	printf("\n\n");


	//クイックソートして表示
	Quicksort(data,0,n-1);

	for(i=0;i<n;i++)
		printf("%d ",data[i]);　　//ソート後の結果の確認


	return 0;
}

■No27539 (C学習中 さん) に返信
　C でクイックソートなら、qsort(3) を使う。いじょ

typedef struct {
    int* pArray;
    int count;
} SortIntStruct;
void SortInt(SortIntStruct* data);

int main(int argc, char** argv)
{
    int idx;
    int size, *org;
    SortIntStruct sortData;
    if (argc < 2) {
        return -1;
    }
    size = sizeof(int) * argc;
    org = (int*) malloc(size);
    memset(org, 0, size);
    for (idx = 1; idx < argc; ++idx) {
        org[idx - 1] = atoi(argv[idx]);
        printf("%d ", org[idx - 1]);
    }
    printf("\n");
    sortData.pArray = org;
    sortData.count = argc - 1;
    SortInt(&sortData);
    // TODO 表示
    free(org);
}

void SortInt(SortIntStruct* data)
{
    SortIntStruct *ptr = (SortIntStruct*) malloc(sizeof(SortIntStruct));
    ptr->pArray = &(data->pArray[0]);
    ptr->count = data->count;
    while (ptr != NULL) {
        // TODO ここで入れ替えとスタックへの積み込みをやる
        // ごめん、疲れた。。。
        free(ptr);
        ptr = Pop();
    }
}

// -----
static void* stack = NULL;
static int stackSize = 0;
void* Pop(void);
int Push(void* data);

int Push(void* data)
{
    int sz = stackSize + 1;
    void* ptr = NULL;
    if (stackSize == 0) {
        ptr = (void*) malloc(sizeof(void*) * stackSize);
    } else {
        ptr = (void*) realloc(stack, stackSize);
    }
    stack = ptr;
    memcpy(&stack[stackSize], data, sizeof(void*));
    stackSize = sz;
    return stackSize;
}

void* Pop(void)
{
    void* ptr = NULL;
    void* ret = NULL;
    if (stackSize == 0) { return NULL; }
    ret = stack[--stackSize];
    // 今までに確保した最大を別途保存しておけば、
    // 毎回サイズを縮小する必要はない。
    // ただし、いつかどこかで解放してやる必要がある。
    ptr = (void*) realloc(stack, stackSize);
    stack = ptr;
    return ret;
}

アルゴリズムの勉強ということで、元の処理を極力破壊せずに
再帰をループにしました。
myutil.h はないので、SWAPはマクロにしました。
スタックサイズは、面倒なので100固定でオーバフローのチェックはしてません。

#include <stdio.h>
#define SWAP(a,b) {int w=a;a=b;b=w;}

static int data[] = { 3, 9, -8, 5, 9, 1, -2, -5, 13, 0 };

static int stackP, stack[100];

static void Push( int i, int j ) {
	stack[stackP++] = i;
	stack[stackP++] = j;
}

static int Pop( int *i, int *j ) {
	if ( stackP ) {
		*j = stack[--stackP];
		*i = stack[--stackP];
		return 1;
	}
	return 0;
}

static int Quicksort( int left, int right ) {
	int i, last;

	if ( left >= right )
		return -1;

	last = left;
	
	for ( i=left+1; i<=right; i++ ) {
		if ( data[left] >= data[i] ) {
			last++;
			SWAP( data[last], data[i] );
		}
	}
	SWAP( data[left], data[last] );
	return last;
}

int main() {
	int left, right, last, i, n = sizeof( data ) / sizeof( int );

	Push( 0, n - 1);
	while ( Pop( &left, &right ) ) {
		last = Quicksort( left, right );
		if ( last != -1 ) {
			Push( left    , last - 1 );
			Push( last + 1, right    );
		}
	}

	// 結果の確認
	for ( i=0; i<n; i++ )
		printf( "%d ", data[i] );
	printf( "\n" );

	return 0;
}