edited by
639 views
0 votes
0 votes

Why the code is not showing correct sorting ?(here pivot is smaller index element, i.e. arr[low])

#include <stdio.h>
    #include <stdlib.h>
    #include <time.h>
 
    void fillArray(int array[], int n)
    {
    	time_t t;
    	time(&t);//get current time
    	srand(t);//gives current time as seed for random number generator
 
 
    	for(int i = 0; i < n; i++)
    	{
    		array[i] = rand()%(10*n);//Doing mod to avoid very large numbers
    	}
    }
    void printArray(int array[], int n)
    {
    	for(int i = 0; i < n; i++)
    	{
    		printf("\n%d ", array[i]);
    	}
    }
    void swap(int *a, int *b)
    {
    	int temp = *a;
    	*a = *b;
    	*b = temp;
    }
int partition (int arr[], int low, int high)
{
	int j;
	static int swap1=0;
	static int swap2=0;
    int pivot = arr[low];    // pivot
    int i = (low);  // Index of smaller element
 
    for (j = low+1; j <= high; j++)
    {
        // If current element is smaller than or
        // equal to pivot
        if (arr[j] <= pivot)
        {
            i++;    // increment index of smaller element
            swap(&arr[i], &arr[j]);
            swap1++;
        }
    }
    swap(&arr[i], &arr[low]);
    swap2++;
    printf("Total number of swaps:%d",(swap1+swap2));
    return (i + 1);
}
 void quickSort(int arr[], int low, int high)
{
    if (low < high)
    {
        /* pi is partitioning index, arr[p] is now
           at right place */
        int pi = partition(arr, low, high);
 
        // Separately sort elements before
        // partition and after partition
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}
 
    int main()
    {
    	int * array, n=5;
		int low=0;
 
 
    	//printf("Enter the no. of numbers: ");
    	//scanf("%d", &n);
    	array = malloc(n * sizeof(int));
    	fillArray(array, n);
        quickSort(array,low,n);
    	printArray(array, n);
    	return 0;
    }

 

edited by

Please log in or register to answer this question.

Related questions

0 votes
0 votes
3 answers
2
ajaysoni1924 asked Sep 2, 2019
3,469 views
In quick sort for sorting of n Numbers, the 75th greatest Element is selected as pivot using $O(n^2)$ time complexity algorithm than what is the worst case time complexit...