Tag: c sorting programs

In this tutorial, we will write a C program to implement shell sort. Before that, you may go through the following topics in C.

• function in C
• for loop in C

Shell Sort Algorithm

Shell sort is an in-place comparison-based sorting algorithm and variation of Insertion sort. It is a better version of Insertion sort in comparison-based. It can compare the elements far apart whereas Insertion compares adjacent elements.

In shell sort, we make the array h-sorted for a large value of h. We keep reducing the value of h until it becomes 1. An array is said to be h-sorted if all sublists of every h’th element are sorted.

---

Implementation of Shell Sort Algorithm in C

Question: C program to implement Shell sort using function.

// Shell Sort in C programming
#include <stdio.h>

//function prototype
void shellSort(int array[], int n);

int main()
{
  int arr[30], n, i;

  printf("Enter the number of elements: ");
  scanf("%d", &n);

  printf("Enter %d Elements:\n", n);
  for (i = 0; i < n; i++)
    scanf("%d", &arr[i]);

  //calling sorting function
  shellSort(arr, n);

  //Display the result
  printf("\nArray after sorting: \n");
  for (i = 0; i < n; i++)
    printf("%d ", arr[i]);

  return 0;
}

// Shell sort
void shellSort(int arr[], int n)
{
  //Rearrange the array elements at n/2, n/4, ..., 1 intervals 
  for (int interval = n / 2; interval > 0; interval /= 2)
  {
    for (int i = interval; i < n; i += 1)
    {
      int temp = arr[i];
      int j;

      for (j = i; j >= interval && arr[j - interval] > temp; j -= interval)
        arr[j] = arr[j - interval];

      arr[j] = temp;
    }
  }
}

Output:

Enter the number of elements: 6
Enter 6 Elements:
55
3
356
124
54
18

Array after sorting:
3 18 54 55 124 356

Time Complexity of Shell Sort:

• Best case:  0(nlogn)
• Average case:  0(n(logn)^2)
• Worst case:  0(n(logn)^2)

---

In this tutorial, we will write a C program to implement quick sort. Before that, you may go through the following topics in C.

• function in C
• for loop in C

Quick Sort Algorithm

Quicksort algorithm is a way of rearranging the elements in an array in ascending or descending order. Quicksort is another Divide and Conquer algorithm.

It takes two empty arrays to hold elements, the first is less than the pivot value and the second element greater than the pivot value, and then sort the element around it or inside it. It involves Swapping and partitioning a section of the array.

---

Implementation of Quick SortAlgorithm in C

Question: C program to implement Quick sort using function.

// implementation of quick sort in C program

#include <stdio.h>

// function prototype
void quickSort(int a[], int start, int end);
int partitionFunc(int a[], int start, int end);

int main()
{
  int arr[30], n, i;

  printf("Enter the number of elements: ");
  scanf("%d", &n);

  printf("Enter %d Elements:\n", n);
  for (i = 0; i < n; i++)
    scanf("%d", &arr[i]);

  //calling sorting function
  quickSort(arr, 0, n - 1);

  //Display the result
  printf("\nArray after sorting: \n");
  for (i = 0; i < n; i++)
    printf("%d ", arr[i]);

  return 0;
}

int partitionFunc(int a[], int start, int end)
{
  int pivot = a[end];	// pivot element  
  int i = (start - 1);

  for (int j = start; j <= end - 1; j++)
  {
    // If current is smaller than the pivot  
    if (a[j] < pivot)
    {
      i++;

      //swap
      int t = a[i];
      a[i] = a[j];
      a[j] = t;
    }
  }

  //swap
  int t = a[i + 1];
  a[i + 1] = a[end];
  a[end] = t;

  return (i + 1);
}

//quickSort Function 
void quickSort(int a[], int start, int end)
{
  if (start < end)
  {
    //p_index is the partitioning index
    int p_index = partitionFunc(a, start, end);

    quickSort(a, start, p_index - 1);
    quickSort(a, p_index + 1, end);
  }
}

Output:

Enter the number of elements: 6
Enter 6 Elements:
12
65
5
224
68
45

Array after sorting:
5 12 45 65 68 224

Time Complexity of Quick Sort:

• Best case:  0(n log n)
• Average case:  0(n log n)
• Worst case:  0(n^2)

---

In this tutorial, we will write a C program to implement heap sort. Before that, you may go through the following topics in C.

• function in C
• for loop in C

Heap Sort Algorithm

Heap is a tree in heap sorting that possesses some specific properties whose value should be greater than or equal to that of the children node.

Heapsort is a comparison-based sorting algorithm and is also considered as the improved Selection sort. It is based on a Binary Heap data structure so to understand we must know two types of data structure:
Arrays and trees

Learn more on Heap sort.

---

Implementation of HeapSort Algorithm in C

Question: C program to implement Heap sort using function.

// implementation of heap sort in C program

#include <stdio.h>

//function prototype
void heapSort(int arr[], int n);
void heapify(int arr[], int size, int i);

//main function
int main()
{
  int arr[30], n, i;

  printf("Enter the number of elements: ");
  scanf("%d", &n);

  printf("Enter %d Elements:\n", n);
  for (i = 0; i < n; i++)
    scanf("%d", &arr[i]);

  //calling sorting function
  heapSort(arr, n);

  //Display the result
  printf("\nArray after sorting: \n");
  for (i = 0; i < n; i++)
    printf("%d ", arr[i]);

  return 0;
}

void heapSort(int arr[], int n)
{
  // create heap
  for (int i = n / 2 - 1; i >= 0; i--)
    heapify(arr, n, i);

  // One by one extract an element from heap
  for (int i = n - 1; i > 0; i--)
  {
    // arrA[0] being max element
    int x = arr[0];
    arr[0] = arr[i];
    arr[i] = x;

    // call max 
    heapify(arr, i, 0);
  }
}

void heapify(int arr[], int size, int i)
{
  int largest = i;  // root

  //Indexes
  int leftChild = 2 *i + 1;
  int rightChild = 2 *i + 2;

  // If left child is larger than root
  if (leftChild < size && arr[leftChild] > arr[largest])
    largest = leftChild;

  // If right child is larger than root
  if (rightChild < size && arr[rightChild] > arr[largest])
    largest = rightChild;

  // If root is not largest
  if (largest != i)
  {
    int swap = arr[i];
    arr[i] = arr[largest];
    arr[largest] = swap;

    // Recursive call
    heapify(arr, size, largest);
  }
}

Output:

Enter the number of elements: 6
Enter 6 Elements:
25
98
3
124
66
9

Array after sorting:
3 9 25 66 98 124

---

In this tutorial, we will learn and write a C program to implement insertion sort. Before that you may go through the following topics in C:

• for loop in C
• Function in C

Insertion Sort Algorithm

Insertion sort is a simple sorting algorithm that sorts the elements in an array by comparing the values at index with all its prior elements. This process takes more time so it is only used for small data set.

This sorting takes the first index element and compares it to its largest value in an array and it moves the element to its right location.

---

C Program to implement Insertion sort

Question: Insertion sort program in C using function.

// implementation of insertion sort in C program

#include <stdio.h>

void insertionSort(int arr[], int n)
{
  int i, j, key;

  for (i = 1; i < n; i++)
  {
    key = arr[i];
    j = i - 1;

    //moving the value
    while (j >= 0 && arr[j] > key)
    {
      arr[j + 1] = arr[j];
      j = j - 1;
    }
    arr[j + 1] = key;
  }
}

int main()
{
  int arr[30], n, i;

  printf("Enter the number of elements: ");
  scanf("%d", &n);

  printf("Enter %d Elements:\n", n);
  for (i = 0; i < n; i++)
    scanf("%d", &arr[i]);

  //calling sorting function
  insertionSort(arr, n);

  //Display the result
  printf("\nArray after sorting: \n");
  for (i = 0; i < n; i++)
    printf("%d ", arr[i]);

  return 0;
}

Output:

Enter the number of elements: 6
Enter 6 Elements:
55
14
77
2
115
99

Array after sorting:
2 14 55 77 99 115

Time Complexity of Heap Sort:

• Best case:  0(n)
• Average case:  0(n^2)
• Worst case:  0(n^2)

---

In this tutorial, we will learn and write a C program to implement selection sort using function. Before that you may go through the following topics in C:

• for loop in C
• Function in C

Selection Sort Algorithm

The selection sort is a simple sorting algorithm which is an in-place comparison-based algorithm. It has two parts where the left end has a sorted part and the right end has an unsorted part.

In the beginning, the left end is empty and the right end has all the elements then the smallest element from the right end is brought to the left end and swapped with the leftmost element. This process continues until the element from the right end is brought to the left by swapping.

Although, it may cause a problem with the large inputs.

---

Implementation of Selection sort in C

Question: Selection sort program in C using function.

// implementation of selection sort in C program
#include <stdio.h>

void selectionSort(int arr[], int n)
{
  int i, j, min, temp;

  for (i = 0; i < n - 1; i++)
  {
    // finding the minimum
    min = i;
    for (j = i + 1; j < n; j++)
      if (arr[j] < arr[min])
        min = j;

    // Swapping
    temp = arr[min];
    arr[min] = arr[i];
    arr[i] = temp;
  }
}

int main()
{
  int arr[30], n, i;

  printf("Enter the number of elements: ");
  scanf("%d", &n);

  printf("Enter %d Elements:\n", n);
  for (i = 0; i < n; i++)
  {
    scanf("%d", &arr[i]);
  }

  //calling sorting function
  selectionSort(arr, n);

  //Display the result
  printf("\nArray after sorting: \n");
  for (i = 0; i < n; i++)
    printf("%d ", arr[i]);

  return 0;
}

Output:

Enter the number of elements: 6
Enter 6 Elements:
25
12
88
5
76
50

Array after sorting:
5 12 25 50 76 88

Time Complexity of Selection Sort:

• Best case:  0(n^2)
• Average case:  0(n^2)
• Worst case:  0(n^2)

---

In this tutorial, you will learn about the Bubble Sort and how to implement bubble sort in C Program.

Question:
Write a c program to implement bubble sort.

Sorting is a technique for organizing the elements in an increasing or decreasing order.

Bubble Sort Algorithm:

Bubble Sort is a comparison-based algorithm in which the adjacent elements are compared and swapped to maintain the order or found in the wrong order.

Bubble sort compares the first element with the next one and if found in the wrong order then that compared element in an array are swapped. This algorithm traverse through the entire element in an array.

Time Complexity of Bubble Sort:

• Best case:  O(n)
• Average case:  O(n^2)
• Worst case:  O(n^2)

---

Bubble Sort in C Program:

Source Code: We will see for descending order. We take the user input for the elements.

//Bubble sorting c

#include <stdio.h>

int main()
{
  int arr[50], numElemt, i, j, swap;

  printf("Enter maximum number of elements that you want to sort for:\n");
  scanf("%d", &numElemt);

  printf("Enter the Elements:\n");

 //elements input
  for (i = 0; i < numElemt; i++)
  {
    scanf("%d", &arr[i]);
  }

 //calculation for sorting for decreasing order
  for (i = 0; i < numElemt - 1; i++)
  {
    for (j = 0; j < numElemt - i - 1; j++)
    {
      if (arr[j] > arr[j + 1])
      {
        swap = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = swap;
      }
    }
  }

  printf("After bubble sort, the sorted elements in decresing order:\n");
 
//Displaying sorted elements
  for (i = 0; i < numElemt; i++)
    printf("%d ", arr[i]);

  return 0;
}

The output of bubble sorting in c programming.

---

In this tutorial, you will learn about the Merge Sort and how to implement in C Program.

Merge Sort Algorithm:

Merge Sort is a sorting algorithm that follows a Divide and Conquer algorithm approach to sort the elements in an array in ascending or descending order.

It divides the array into two halves and sorts them separately. Again the two halves are divided into separate two halves and the process keeps on going until the elements are totally separated. After that, the elements are combined together in the same steps as they were separated but while combining the elements are sorted in each steps.

When the combining step is completed we will get a fully sorted array.

Time Complexity of Merge Sort:

• Best case:  0(n log n)
• Average case:  0(n log n)
• Worst case:  0(n log n)

---

C Program for Merge Sort

//merge sort c program

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

void MergeSorted(int[], int);
void Merg(int[], int[], int, int, int);
void MSort(int[], int[], int, int);

int main()
{
  int i, numElemt, arr[50];

  //User Input
  printf("Enter the number of elements you want to sort for: ");
  scanf("%d", &numElemt);

  printf("Enter %d elements\n", numElemt);
  for (i = 0; i < numElemt; i++)
  {
    scanf("%d", &arr[i]);
  }

  MergeSorted(arr, numElemt);

  printf("After Merge Sort, the elements are: ");
  for (i = 0; i < numElemt; i++)
  {
    printf("%d  ", arr[i]);
  }

  printf("\n");
}

void Merge(int arr[], int temp[], int lpos, int rpos, int rend)
{
  int i, lend, numElemt, temppos;
  lend = rpos - 1;
  temppos = lpos;
  numElemt = rend - lpos + 1;

  while (lpos <= lend && rpos <= rend)
  {
    if (arr[lpos] <= arr[rpos])
      temp[temppos++] = arr[lpos++];
    else
      temp[temppos++] = arr[rpos++];
  }

  while (lpos <= lend)
    temp[temppos++] = arr[lpos++];
  while (rpos <= rend)
    temp[temppos++] = arr[rpos++];

  for (i = 0; i < numElemt; i++, rend--)
    arr[rend] = temp[rend];
}

void MSort(int arr[], int temp[], int left, int right)
{
  int mid;
  if (left < right)
  {
    mid = (left + right) / 2;
    MSort(arr, temp, left, mid);
    MSort(arr, temp, mid + 1, right);
    Merge(arr, temp, left, mid + 1, right);
  }
}

void MergeSorted(int arr[], int numElemt)
{
  int *temparray;
  temparray = malloc(sizeof(int) *numElemt);
  MSort(arr, temparray, 0, numElemt - 1);
  free(temparray);
}

The output of merge sort in C program.

---