Quick Sort
Computer Science, GATE

Quick Sort

Quick Sort algorithm:

  • is one of the most efficient sorting algorithms.
  • is based on divide and conquer approach.
  • Successively divides the problem into smaller parts until the problem become so small that they can be directly solved.



In quick sort algorithm, you:

  • Select an element from the list called as pivot.
  • Partition the list into 2 parts such that:
    • All the elements towards the left end of the list are smaller than the pivot.
    • All the elements towards the right end of the list are greater than the pivot.
  • Store the pivot at its correct position between the two parts of the list.

You repeat this process for each of the two sublists created after partitioning. This process continues untill one element is left in each sublist.

Algorithm:

QuickSort(low,high)

  1. if(low>high)
    • Return
  2. Set pivot = arr[low]
  3. set i = low + 1
  4. set j = high
  5. Repeat step 6 until i < high and arr[i] < pivot //Search for element greater than pivot
  6. increment i by 1
  7. Repeat step 8 until j > low and arr[j] > pivot //Search for element smaller than pivot
  8. Decrement j by 1
  9. if i < j     //If greater element is on the left of smaller element
    • swap arr[i] with arr[j]
  10. if i<=j
    • Go to step 5 //Continue the search
  11. if low < j
    • Swap arr[low] with arr[j] //Swap pivot with last element in first part of the list
  12. QuickSort(low,j-1) //Apply quicksort on list left of pivot
  13. QuickSort(j+1,high) //Apply quicksort on list right of pivot



Implementing Quick Sort

#include<stdio.h>
void quicksort(int a[],int low,int high);
int main()
{
int high=0,i=0,arr[20];
printf(“Enter no. of elements\n”);
scanf(“%d”,&high);
printf(“Enter %d numbers to be sorted\n”,high);
for(i=0;i<high;i++)
scanf(“%d”,&arr[i]);
quicksort(arr,0,high-1);
printf(“Sorted Array:\t”);
for(i=0;i<high;i++)
printf(“%d\t”,arr[i]);
return 0;
}
void quicksort(int a[],int low,int high)
{
int first,last,temp,pivot;
pivot = a[low];
first = low+1;
last = high;
if(low<high)
{
while(first<last)
{
while(a[first]<pivot && first < high)
first++;
while(a[last]>pivot && last > low)
last–;
if(first<last)
{
temp = a[first];
a[first] = a[last];
a[last] = temp;
}
}
if(low<last)
{
temp = a[low];
a[low] = a[last];
a[last] = temp;
}
quicksort(a,low,last-1);
quicksort(a,last+1,high);
}
}

If you found any mistakes in above code then please let us know in the comment box below.

For Gate CSE study material Click Here..!!

Click For Time Complexities of Sorting Algorithms

Reverse
Computer Science

Reverse Strings in C

There are three ways to reverse string in c.They are as follows:

  1. Use predefined function from c library to reverse a string.
  2. Directly print reversed string.
  3. Write own code of reversing a string permanently by swapping.

Let’s see all the program to reverse a given string.

1. Predefined Function

C library has a predefined function called as strrev() that reverses a string. It takes only one argument that is the variable which holds the string to be reversed or the string itself direclty surrounded by double qoutes. Lets have a look at the program.



#include<stdio.h>
#include<string.h> //header file that contain strrev() function
int main()
{
char str[20];
printf(“Enter String to be reversed\n”);
gets(str);
printf(“String is %s\n”,str);
printf(“Reverse String is %d\n”,strrev(str));
return 0;
}

2. Printing Reversed String

We can directly print a string in reversed order.

#include<stdio.h>
#include<string.h>
int main()
{
char str[20];
int i,length;
printf(“Enter a string\n”);
gets(str);
length=strlen(str); //Count the length of string
for(i=length-1;i>=0;i–)
{
printf(“Reversed string is %c”,str[i]);
}
return 0;
}



3. Write own code of reversing string

#include<stdio.h>
#include<conio.h>
int main()
{
char a[20],b[20];
int count=0,i=0,j=1;
printf(“Enter a string to be reversed\n”);
scanf(“%s”,&a);
while(a[count]!=’\0′) /*Calculate length of string*/
{
count++;
}
j=count-1;
while(i<count) /* Reverses string*/
{
b[i]=a[j];
j–;
i++;
}
b[i]=’\0′; /*Terminates string*/
printf(“%s\n”,b);
return 0;
}

Here we would have used strlen() function direclty to count the length of string but here we are reversing string explicitly that’s why we don’t used predefined function strlen to count length of string and counted it too explicitly.



Above all code snippets are for reversing a string if you have any new method then feel free to share and if you found something wrong in above code then let us know in the comment box below.

For study materials of GATE Click Here..!!

For more on computer Science Click Here..!!