C Program To Sort an array having duplicate elements

Sorting an array means arranging the elements of the array either in ascending order or in descending order. Sorting an array having duplicate elements means effectively sorting all the elements either in ascending or descending order with all the elements having the same number of occurrences in the sorted array as that of the original array.

In this tutorial, we will see how to sort an array having duplicate elements. But before moving forward if you are not familiar with the concept of the array in C, then do check the article on Arrays in C.

Input : Enter the array: 8 5 6 7 4 3 7 7

Output :Sorted Array: 3 4 5 6 7 7 7 8

Program 1: To Sort an Array Having Duplicate Elements

Quicksort is an algorithm that is based on a divide and conquers approach. Here, the array splits into two sub-arrays and these sub-arrays are recursively called to sort the elements.

Algorithm

1. Start
2. Declare an array
3. Initialize the array
4. Call a function that will perform the quick sort.
5. Declare two variables: low and high. These variables will determine the starting and ending index of the array.
6. Call another function partition in the quicksort function.
7. This partition function will divide the function based on the pivot element.
8. Put the elements smaller than pivot on the left and greater than pivot on the right of pivot
9. Call another function that will swap the position of the elements.
10. Lastly, print the sorted array.
11. End.

Below is the code for the Quick sort implementation in C language.

#include <stdio.h>
// Function to swap position of elements
void swap(int *a, int *b) 
{
  int temp = *a;
  *a = *b;
  *b = temp;
}
// Function to partition the array on the basis of pivot element
int partition(int array[], int low, int high) 
{  
  // Select the pivot element
  int pivot = array[high];
  int i = (low - 1);
  // Put the elements smaller than pivot on the left 
  // and greater than pivot on the right of pivot
  for (int j = low; j < high; j++) 
  {
    if (array[j] <= pivot) 
    {
      i++;
      swap(&array[i], &array[j]);
    }
  }
  swap(&array[i + 1], &array[high]);
  return (i + 1);
}
void quickSort(int array[], int low, int high) 
{
  if (low < high) 
  {    
    // Select pivot position and put all the elements smaller 
    // than pivot on left and greater than pivot on right
    int pi = partition(array, low, high);    
    // Sort the elements on the left of pivot
    quickSort(array, low, pi - 1);    
    // Sort the elements on the right of pivot
    quickSort(array, pi + 1, high);
  }
}
// Function to print elements of an array
void printArray(int array[], int size) 
{
  for (int i = 0; i < size; ++i) 
  {
    printf("%d  ", array[i]);
  }
  printf("\n");
}
// Driver code
int main() 
{
  int arr[] = {3 , 5 ,7 ,3 ,4,2 ,2, 8};
  int n = sizeof(arr) / sizeof(arr[0]);
  quickSort(arr, 0, n - 1);
  printf("Sorted array in ascending order: \n");
  printArray(arr, n);
}

Sorted array in ascending order:
2 2 3 3 4 5 7 8

Program 2: To Sort an Array Having Duplicate Elements

Counting sort is a sorting technique based on keys. It sorts the elements of the array by counting the number of occurrences of each element in the array.

Features of Counting Sort

1. It can be used for negative inputs.

2. It uses a partial hashing technique to count the occurrence.

3. It is effective when the range is not greater than the number of objects.

Algorithm

1. Start
2. Declare an array
3. Initialize the array
4. Call a function to sort the array
5. Declare another array that will store the frequency of the elements.
6. Count the key values by the number of occurrences of the object.
7. Update the array.
8. Now, sort the array.
9. Print the sorted array.
10. Stop

Below is the C program to sort array elements.

#include <stdio.h>
#include <string.h> 
#define RANGE 100 
// Function to sort an array with duplicate values
// using Counting Sort algorithm
void sortArray(int arr[], int n)
{
    // create a new array that stores the counts of elements in the input array
    // Here, freq[i] stores the number of items with key equal to i
    int freq[RANGE]; 
    // initialize array by 0
    memset(freq, 0, sizeof(freq)); 
    // using value of elements in the input array as index,
    // update their frequencies in the new array
    for (int i = 0; i < n; i++)
        freq[arr[i]]++; 
    // overwrite the input array with sorted order
    int k = 0;
    for (int i = 0; i < RANGE; i++)
    {
        while (freq[i]--)
            arr[k++] = i;
    }
} 
// Sort an array with many duplicated values
int main()
{
     int n;                  //Declare array size
     printf("Enter the number of elements : ");
     scanf("%d",&n);     
     int arr[n];             //Declare an array
     printf("Enter the elements : ");
     for(int i=0;i<n;i++)    //Initialize the array
     scanf("%d",&arr[i]); 
     sortArray(arr, n);      //Call a function to sort the array    
    //Print the sorted array with duplicate elements
    printf("Sorted array..\n");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
 
    return 0;
}

Enter the number of elements : 10
Enter the elements : 2 3 6 8 9 7 9 9 8 2 4
Sorted array..
2 2 3 6 7 8 8 9 9 9