Complexity and no. of swaps required

#include <stdio.h>

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

void qsort(int a[], int start, int end)
{
	int i, j, p;
	if(start >= end)
	{
		return;
	}
	i = p = start, j = end;
	while(i < j)// Finds the no. of elements in the array < a[p] from the beginning and swaps with the no. of elements in the array greater than a[p] from the end
	{
		while(a[i] <= a[p] && i < end)
			i++;
		while(a[j] > a[p]) //( > ensures j never comes equal to p)
			j--;
		if(i < j)
		{
			swap(&a[i], &a[j]);
		}
	}
	swap(&a[j], &a[p]);
	qsort(a, start,  j-1);
	qsort(a,  j + 1, end);
}

void printArray(int a[], int n)
{
	int i;
	for(i = 0; i < n; i++)
	{
		printf("%d ",a[i]);
	}
}

int main()
{
	char str[20];
	int num[100];
	int i = 0;
	printf("Enter the numbers to sort (. to stop): ");
	while(1)
	{
		scanf("%s",str);
		if(str[0] == '.')
			break;
		sscanf(str, "%d", &num[i++]); 
	}
	qsort(num, 0, i-1);
	printf("The sorted numbers are: ");
	printArray(num, i);
	printf("\n");

        return 0;
}




blog comments powered by Disqus

Sister Sites: GATE Overflow, GATE CSE Wiki, GATE CSE, Aptitude Overflow

This work is licensed under the CC By-SA 3.0 , without all the cruft that would otherwise be put at the bottom of the page.