// An iterative implementation of quick sort #include <stdio.h> // A utility fun
ID: 667812 • Letter: #
Question
// An iterative implementation of quick sort
#include <stdio.h>
// A utility function to swap two elements
void swap ( int* a, int* b )
{
int t = *a;
*a = *b;
*b = t;
}
/* This function is same in both iterative and recursive*/
int partition (int arr[], int l, int h)
{
int x = arr[h];
int i = (l - 1);
for (int j = l; j <= h- 1; j++)
{
if (arr[j] <= x)
{
i++;
swap (&arr[i], &arr[j]);
}
}
swap (&arr[i + 1], &arr[h]);
return (i + 1);
}
/* A[] --> Array to be sorted, l --> Starting index, h --> Ending index */
void quickSortIterative (int arr[], int l, int h)
{
// Create an auxiliary stack
int stack[ h - l + 1 ];
// initialize top of stack
int top = -1;
// push initial values of l and h to stack
stack[ ++top ] = l;
stack[ ++top ] = h;
// Keep popping from stack while is not empty
while ( top >= 0 )
{
// Pop h and l
h = stack[ top-- ];
l = stack[ top-- ];
// Set pivot element at its correct position in sorted array
int p = partition( arr, l, h );
// If there are elements on left side of pivot, then push left
// side to stack
if ( p-1 > l )
{
stack[ ++top ] = l;
stack[ ++top ] = p - 1;
}
// If there are elements on right side of pivot, then push right
// side to stack
if ( p+1 < h )
{
stack[ ++top ] = p + 1;
stack[ ++top ] = h;
}
}
}
// A utility function to print contents of arr
void printArr( int arr[], int n )
{
int i;
for ( i = 0; i < n; ++i )
printf( "%d ", arr[i] );
}
// Driver program to test above functions
int main()
{
int arr[] = {4, 3, 5, 2, 1, 3, 2, 3};
int n = sizeof( arr ) / sizeof( *arr );
quickSortIterative( arr, 0, n - 1 );
printArr( arr, n );
return 0;
}
I have an error when implementing the code. This is a quicksort in C programming language "Iterative".
Here is my ERROR
UNDER >> void quickSortIterative (int arr[], int l, int h)
{
"""""" int stack[ h - l + 1 ]; """""" because h and l has not been initilaized but how I can solve without changing the program and I need to get quicksort without Recursive.
Thank you
Explanation / Answer
#include<stdio.h>
#include<malloc.h>
#include<conio.h>
struct linked_list
{
int data;
struct linked_list *link;
struct linked_list *prev;
};
typedef struct linked_list node;
void create(node *first);
void print(node *first);
node *quick_sort(node *first);
int count(node *first);
main()
{
node *first;
int x,n,i,j=0,m;
clrscr();
first=(node *)malloc(sizeof(node));
first->prev=0;
create(first);
printf("the numbers you have entered are : ");
print(first);
n=count(first);
printf(" the number of elements you have entered are: %d ",n);
for(i=0;idata);
printf( " do you want to add more?(y=1/n=2) ");
scanf("%d",&x);
if(x==2)
{
first->link=0;
}
else
{
first->link= (node *)malloc(sizeof(node));
first->link->prev=first;
create(first->link);
}
return;
}
void print(node *list)
{
if(list->link!=0)
{
printf("%d-> ",list->data);
if(list->link->link==0)
printf("%d",list->link->data);
print(list->link);
}
}
node *quick_sort(node *first)
{
node *save,*temp,*pivot,*p;
pivot=first;
temp=pivot->link;
while(temp!=0)
{
if(pivot->data > temp->data)
{
if(temp->link==0)
{
temp->prev->link=0;
temp->link=first;
first->prev=temp;
temp->prev=0;
first=temp;
break;
}
else
{
temp=temp->link;
temp->prev->link=first;
temp->prev->prev->link=temp;
first->prev=temp->prev;
temp->prev=temp->prev->prev;
first->prev->prev=0;
first=first->prev;
}
}
else
temp=temp->link;
}
pivot=pivot->link;
while(pivot->link!=0)
{
temp=pivot->link;
while(temp!=0)
{
if(pivot->data > temp->data)
{
if(temp->link==0)
{
temp->prev->link=0;
temp->link=pivot;
pivot->prev->link=temp;
temp->prev=pivot->prev;
break;
}
else
{
p=pivot->prev;
temp=temp->link;
temp->prev->link=pivot;
temp->prev->prev->link=temp;
pivot->prev=temp->prev;
temp->prev=temp->prev->prev;
pivot->prev->prev=p;
pivot->prev->prev->link=pivot->prev;
}
}
else
temp=temp->link;
}
pivot=pivot->link;
}
printf(" first=%d ",first->data);
return(first);
}
int count(node *first)
{
node *save=first;
int n=0;
while(save!=0)
{
n++;
save=save->link;
}
return(n);
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.