w04d00

Announcements

Quicksort

void sort(int *arr, int len)
{
	void swap(int i, int j)
	{
		int t = arr[i] ; arr[i] = arr[j] ; arr[j] = t ; return ;
	}
	int pivt = arr[len], i = 0, j = len-1 ;
	if (len-- < 2) { return ; }
	
	while (i < j)
	{
		while (arr[i] < pivt && i < len) { i++ ; }
		while (arr[j] > pivt && j > 0  ) { j-- ; }
		if (i < j) { swap(i,j) ; }
	}
	while (arr[j] < pivt) { j++; }
	swap(j,len) ; sort(arr, j) ; sort(arr+j+1, len-j) ;
	return ;
}

Print memory

void print_mem( void *arr , size_t siz )
{
	size_t i ;
	unsigned char *ptr = (unsigned char *)arr ;
	for ( i = 0 ; i < siz ; i++ )
	{
		printf("%02hhX", *(ptr+i)) ;
	}
	putchar('\n') ;
	return ;
}

Interactive testing

int main()
{
	int a[10] ;
	printf("Provide ten comma separated input integers.\n") ;
	while (1)
	{
		scanf("%d,%d,%d,%d,%d,%d,%d,%d,%d,%d",a,a+1,a+2,a+3,a+4,a+5,a+6,a+7,a+8,a+9) ;
		printf("I: ") ; print_mem(a,10*sizeof(int)) ;
		sort(a, 10) ;
		printf("0: ") ; print_mem(a,10*sizeof(int)) ;
	}
	return 0;
}

Radixsort

Binary, In-place, MSD

void sort(int *arr, int len)
{
	void rsort(int *arr, int len, int rad)
	{
		if (len < 2 || rad < 0) { return ; }
		void swap(int i, int j)
		{
			int t = arr[i] ; arr[i] = arr[j] ; arr[j] = t ; return ;
		}
		int msk = 1 << rad, i = 0, j = len-1 ;
		while (i < j)
		{
			while ((arr[i] & msk) == 0 && i < len) { i++ ; }
			while ((arr[j] & msk) != 0 && j > 0  ) { j-- ; }
			if (i < j) { swap(i,j) ; }
		}
		rsort(arr, i, rad - 1) ; rsort(arr+i, len-i, rad - 1) ;  return ;
	}
	int max = arr[0] , i ;
	for ( i = 1 ; i < len   ; i++ ) { if (arr[i] > max) { max = arr[i] ; } }
	for ( i = 0 ; max >>= 1 ; i++ ) {}
	rsort(arr, len, i) ;  return ;
}