Sorting Strings in C

In this article, we have explored different ways to sort a string and an array of string in C Programming Language. We have presented C code snippets to illustrate the concepts. Sorting refers to the arrangement of the elements in a particular order depending on the comparing parameter.

Table of contents:

1. Introduction.
2. Sorting a string using bubble sort with steps.
3. Explanation of bubble sort
4. Sorting using quick sort with steps.
5. Explanation of quick sort.
6. Sorting using merge sort with steps.
7. Explanation of merge sort.
8. Sorting an array of strings:
   a. Bubble sort method.
   b. qsort method.
   c. qsort method for a single string sorting.

Introduction

We will study about how the string is sorted in lexographical order using various sorting algorithms in C language along with their varying time complexities and also sorting an array of strings using bubble sort method and qsort function.

1. Sorting a string using bubble sort.

Steps:

1. Start with the first element of the string.
2. Compare the selected element with the next element.
3. If the selected element is greater than the next element then perform swapping of the elements or else move up to the next element.
4. Repeat these steps till the selected element is of the last index and we get sorted array.

Code:

#include <stdio.h>
#include <stdlib.h>
#include<string.h>

int main()
{
    char c[30], t;
    int flag =0, count=0;
    printf("Enter the string to be sorted:\n");
    scanf("%s", c);
    int n=strlen(c);
    for(int i=0; i<n-1; i++){
        for(int j=i+1; j<n; j++){
            count++;
            if(c[i]>c[j]){
                t = c[i];
                c[i] = c[j];
                c[j] = t;
            }
        }
    }
    printf("\nThe sorted string is %s:", c);
    return 0;
}

Input:

edcba

Output:

abcde

Explanation:
Bubble sort as the name suggests brings the smallest element to the front of the array.
So here smallest lexographically character will come at front.
Here the average and worst case time complexity of the bubble sort is O(n^2).

2.Sort String using Quick Sort.

Steps:

1. Pick any pivot element in this case index 0.
2. Take two variables to point left and right of the string say variables low and high in this case.
3. The left will point to the low index, and the right will point to the high index.
4. Move greater than pivot element to the right of the pivot.
5. Move smaller than pivot element to the left of the pivot.
6. Perform these operations until we get the sorted string.

Code:

#include<stdio.h>
#include<string.h>

void swap (char *a, char *b)
{

  int t = *a;
  *a = *b;
  *b = t;

}

int partition (char arr[], int low, int high)
{

  int pivot = arr[high];
  int i = (low - 1);
  for (int j = low; j <= high - 1; j++)
   {
    if (arr[j] <= pivot)
    {
      i++;
      swap (&arr[i], &arr[j]);
    }
   }

  swap (&arr[i + 1], &arr[high]);
  return (i + 1);

}

void quickSort (char arr[], int low, int high)
{
 if (low < high)
  {
   int pi = partition (arr, low, high);
   quickSort (arr, low, pi - 1);
   quickSort (arr, pi + 1, high);
  }

}

void printArray (char arr[])
{

 printf ("%s ", arr);

}

int main ()
{

  char arr[30] ;
  printf("Enter the string to be sorted:\n");
  scanf("%s", arr);
  int n = strlen(arr);
  quickSort (arr, 0, n - 1);
  printf ("The sorted array is: \n");
  printArray (arr);
  return 0;

}

Input:

opengenus

Output:

eegnnopsu

Explanation:

Quick Sort is a divide and conquer algorithm in which there are two functions one is quicksort and the other is partition function. In partition function one element is picked as pivot and the partitions the string around that pivot.
Here the average and worst case time complexity of the sort quick sort is O(nlog(n)) and O(n^2) respectively.

3.Sorting String using Merge Sort

Steps:

1. Find the middle index of the string.
2. Divide the string from the middle.
3. Call the mergesort function for the first half of the string.
4. Perform the same for second half of the string.
5. Merge the sorted parts to form the complete sorted sring.

Code:

#include <stdio.h>
#include<string.h>
#define MAX 1000

char arr[MAX]; 
char arr2[MAX]; 

void merge(int low, int mid, int high) 
{
    int i, j, k;

    for(i=low, j=mid+1, k=low; i<=mid && j<=high; k++) 
    {
        if(arr[i]<arr[j]) 
        {
            arr2[k]=arr[i];
            i++;
        }
        else   
        {
            arr2[k] = arr[j];
            j++;
        }
    }
    while(i<=mid)   
    {
        arr2[k]=arr[i];
        k++;
        i++;
    }
    while(j<=high) 
    {
        arr2[k]=arr[j];
        k++;
        j++;
    }

    for (int l = 0; l <high+1 ; ++l)   
    {
        arr[l]=arr2[l];
    }
}

void mergesort(int low, int high)
{
    if(low<high)    
    {
        int mid= (low + high)/2; 
        mergesort(low,mid); 
        mergesort(mid+1, high);
        merge(low, mid, high);
    }
    else
        return;
}

int main()
{
    int n;
   
    printf("\nEnter string: \n" );
    scanf("%s", arr);
    n= strlen(arr);
    printf("\nString after sorting is : ");

    mergesort(0, n-1);

    printf("%s", arr);
}

Explanation:

Merge sort is also an divide and conquer algorithm in which the unsorted string is divided into n substring each of one character and then merge these substrings in a sorted manner in order to get one complete string which is sorted.
Here the average and worst case time complexity of the sort Merge sort is O(nlog(n)) and O(nlog(n)) respectively.

Input:

hello

Output:

ehllo

Sorting an array of strings:

Bubble sort method:

Steps:

1. Declare a 2-d array to store the strings.
2. Now perform bubble sort on each row of the array by comparing strings of different rows.
3. Print the array row wise.

Code:

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int main(){
    int n=5;
    char arr[25][25] = {"Yellow", "Region", "Statue", "Avatar", "Kevlar"};
    char temp[25];
    for(int i=1;i<=n;i++)
	for(int j=0;j<=n-i;j++)
	  if(strcmp(arr[j],arr[j+1])>0)
	  { 
        strcpy(temp,arr[j]);
	    strcpy(arr[j],arr[j+1]);
	    strcpy(arr[j+1],temp);
	  }
    for(int i=0; i<=n; i++){
        printf("%s \n", arr[i]);
    } 
     return 0;
}

OUTPUT:

Avatar 
Kevlar
Region
Statue
Yellow

This is the same method mentioned above but the difference is here the array of strings is scanned and each string is compared with the other to form the order.

qsort function

This function is used to sort the array of any data type mentioned in it. It's syntax is:

qsort(array, number of elements in the array, 
      size of element, basis of comparison).

It comes under the header file stdlib.h.

Code:

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

int comp(const void *str1, const void *str2) 
{ 
    const char **str_1 = (const char **)str1;
    const char **str_2 = (const char **)str2;
    return strcmp(*str_1, *str_2);
} 

int main(){
    int n=5;
    char* arr[] = {"Yellow", "Region", "Statue", "Avatar", "Kevlar"};
    qsort(arr, n, sizeof(char*), comp);
    for(int i=0; i<n; i++){
        printf("%s \n", arr[i]);
    } 
     return 0;
}

Output:

Avatar 
Kevlar    
Region    
Statue    
Yellow

Qsort function for single string:

Here the input for qsort function is changed a little bit compared to the qsort function used in above code mentioned such as instead of char* , char is used.

Code:

#include <stdlib.h> 
#include <stdio.h>
char arr[] = {'h', 'e', 'l', 'l', 'o'};

int comparator (const void * p1, const void * p2)
{
  return (*(char*)p1 - *(char*)p2);
}


int main ()
{
  printf("The unsorted string is: \n");
  for(int i = 0; i < 5; i++)
  {   
    printf("%c ", arr[i]);
  }  
  qsort(arr, 5, sizeof(char), comparator);
  printf("\nThe sorted string is: \n");
  for(int i = 0; i < 5; i++)
  {   
    printf("%c ", arr[i]);
  }
}

Input:

h e l l o

Output:

e h l l o

In this article at OpenGenus, we have discussed some basic sorting algorithms and qsort function for sorting an array of strings which should be known by every programmer as they are important from academic point of view and very easy to understand and implement.