Quick_sort.c

/** Divide  : Partition the array A[low....high] into two sub-arrays
  *           A[low....j-1] and A[j+1...high] such that each element
  *           of A[low....j-1] is less than or equal to A[j], which
  *           in turn is is less than or equal to A[j+1...high]. Compute
  *           the index j as part of this partitioning procedure.
  * Conquer : Sort the two sub-arrays A[low....j-1] and A[j+1....high]
  *           by recursive calls to quicksort
  **/

#include<stdio.h>

int main()
{
  int arr[20], n, i;
  printf("Enter the size of the array\n");
  scanf("%d", &n);

  printf("Enter the elements to be sorted\n");
  for(i = 0; i < n; i++)
    scanf("%d", &arr[i]);

  quicksort(arr, 0, n-1);

  printf("Sorted array\n");
  for(i = 0; i < n; i++)
    printf("%d ", arr[i]);

  return 0;
}
void quicksort(int *arr, int low, int high)
{
  int pivot, i, j, temp;
  if(low < high) {
    pivot = low; // select a pivot element
    i = low;
    j = high;
    while(i < j) {
      // increment i till you get a number greater than the pivot element
      while(arr[i] <= arr[pivot] && i <= high)
        i++;
      // decrement j till you get a number less than the pivot element
      while(arr[j] > arr[pivot] && j >= low)
        j--;
      // if i < j swap the elements in locations i and j
      if(i < j) {
        temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
      }
    }

    // when i >= j it means the j-th position is the correct position
    // of the pivot element, hence swap the pivot element with the
    // element in the j-th position
    temp = arr[j];
    arr[j] = arr[pivot];
    arr[pivot] = temp;
    // Repeat quicksort for the two sub-arrays, one to the left of j
    // and one to the right of j
    quicksort(arr, low, j-1);
    quicksort(arr, j+1, high);
  }
}

Quick_sort_linked_list.c

#include<stdio.h>
struct linknode
{
int data;
struct linknode *next;
struct linknode *prev;
};

typedef struct linknode node;
createlist(int d, node **h)
{
node *newnode=(node*)malloc(sizeof(node));
if(newnode==NULL)
printf("error in allocating size");
else
{
node *temp=*h;
newnode->data=d;
newnode->next=NULL;
newnode->prev=NULL;
if(*h==NULL)
{
*h=newnode;
}
else
{
while(temp->next!=NULL)
temp=temp->next;
temp->next=newnode;
newnode->prev=temp;
}
}
}


display(node *h)
{
node *current=h;

while(current!=NULL)
{
printf("%d ",current->data);
current=current->next;
}
}
node *findlast(node *h)
{
node *temp=h;
while(temp->next!=NULL)
temp=temp->next;
return temp;
}
swap(int *a,int *b)
{
int t;
t=*a;
*a=*b;
*b=t;
}

node *partition(node *p, node *q)
{
        int x=q->data;
        int t;
  node *i=p->prev;
node *j;
for(j=p;j!=q;j=j->next)
{

if(j->data<=x)
{
i=(i==NULL)?p:i->next;
swap(&(i->data),&(j->data));
}
}
i=(i==NULL)?p:i->next;
swap(&(i->data),&(q->data));
return i;
}

quicksort(node *s,node *l)
{
printf("in quicksort");
node *p;
if(s!=l && s!=l->next&& l!=NULL)
{
p=partition(s,l);
quicksort(s,p->prev);
quicksort(p->next,l);
}
}



//typedef linknode node;
int main(int argc[],char *argv[])
{

node *head=NULL;
FILE *fp;
int val;
fp=fopen(argv[1],"r");
if(fp==NULL)
printf("eror");
else
{
while((fscanf(fp,"%d",&val)!=EOF))
{
//printf("%d ",val);
createlist(val,&head);

}
}
display(head);
node *last=findlast(head);
printf("data of last= %d",last->data);
quicksort(head,last);
printf("****after quicksort******\n");
display(head);

//return 0;
}