C Program to Sort Elements in Lexicographical Order (Dictionary Order)

by

Sorting elements in lexicographical order (also known as dictionary order) is a common task in many applications. This article explores three different C Program to Sort Elements in Lexicographical Order (Dictionary Order) to achieve lexicographical sorting, complete with explanations, example code, and outputs.

Prerequisites

Before diving into the solutions, ensure you have the following prerequisites:

  • Basic understanding of C programming.
  • Familiarity with strings and arrays.
  • A C compiler installed on your system (e.g., GCC).

Solution 1: Using Bubble Sort

1.1 Explanation

In this approach, we use the bubble sort algorithm to sort strings lexicographically. Bubble sort repeatedly swaps adjacent elements if they are in the wrong order.

1.2 Program

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

void bubbleSort(char arr[][50], int n) {
    char temp[50];
    for (int i = 0; i < n-1; i++) {
        for (int j = 0; j < n-i-1; j++) {
            if (strcmp(arr[j], arr[j+1]) > 0) {
                strcpy(temp, arr[j]);
                strcpy(arr[j], arr[j+1]);
                strcpy(arr[j+1], temp);
            }
        }
    }
}

int main() {
    char arr[5][50];
    int n = 5;

    printf("Enter 5 strings:\n");
    for (int i = 0; i < n; i++) {
        fgets(arr[i], sizeof(arr[i]), stdin);
        arr[i][strcspn(arr[i], "\n")] = 0; // Remove newline character
    }

    bubbleSort(arr, n);

    printf("\nSorted strings:\n");
    for (int i = 0; i < n; i++) {
        printf("%s\n", arr[i]);
    }

    return 0;
}

1.3 Output

C
Enter 5 strings:
banana
apple
grape
cherry
mango

Sorted strings:
apple
banana
cherry
grape
mango

Solution 2: Using Selection Sort

2.1 Explanation

In this approach, we use the selection sort algorithm to sort strings lexicographically. Selection sort repeatedly selects the smallest element from the unsorted portion and swaps it with the first unsorted element.

2.2 Program

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

void selectionSort(char arr[][50], int n) {
    char temp[50];
    for (int i = 0; i < n-1; i++) {
        int minIndex = i;
        for (int j = i+1; j < n; j++) {
            if (strcmp(arr[j], arr[minIndex]) < 0) {
                minIndex = j;
            }
        }
        if (minIndex != i) {
            strcpy(temp, arr[i]);
            strcpy(arr[i], arr[minIndex]);
            strcpy(arr[minIndex], temp);
        }
    }
}

int main() {
    char arr[5][50];
    int n = 5;

    printf("Enter 5 strings:\n");
    for (int i = 0; i < n; i++) {
        fgets(arr[i], sizeof(arr[i]), stdin);
        arr[i][strcspn(arr[i], "\n")] = 0; // Remove newline character
    }

    selectionSort(arr, n);

    printf("\nSorted strings:\n");
    for (int i = 0; i < n; i++) {
        printf("%s\n", arr[i]);
    }

    return 0;
}

Output

C
Enter 5 strings:
zebra
lion
elephant
tiger
cat

Sorted strings:
cat
elephant
lion
tiger
zebra

Solution 3: Using Quick Sort

3.1 Explanation

In this approach, we use the quicksort algorithm to sort strings lexicographically. Quicksort is a divide-and-conquer algorithm that works by selecting a ‘pivot’ element and partitioning the array around the pivot.

3.2 Program

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

void swap(char arr[][50], int i, int j) {
    char temp[50];
    strcpy(temp, arr[i]);
    strcpy(arr[i], arr[j]);
    strcpy(arr[j], temp);
}

int partition(char arr[][50], int low, int high) {
    char pivot[50];
    strcpy(pivot, arr[high]);
    int i = (low - 1);

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

void quickSort(char arr[][50], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);

        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

int main() {
    char arr[5][50];
    int n = 5;

    printf("Enter 5 strings:\n");
    for (int i = 0; i < n; i++) {
        fgets(arr[i], sizeof(arr[i]), stdin);
        arr[i][strcspn(arr[i], "\n")] = 0; // Remove newline character
    }

    quickSort(arr, 0, n-1);

    printf("\nSorted strings:\n");
    for (int i = 0; i < n; i++) {
        printf("%s\n", arr[i]);
    }

    return 0;
}

Output

C
Enter 5 strings:
pear
kiwi
orange
apple
banana

Sorted strings:
apple
banana
kiwi
orange
pear

Conclusion

Using C Program to Sort Elements in Lexicographical Order (Dictionary Order) is essential. This article presented three different methods to achieve this task: using bubble sort, selection sort, and quicksort. Each method has its own advantages and can be chosen based on the specific requirements of your application. By understanding and experimenting with these techniques, you can efficiently sort strings and enhance your overall programming skills in C.