Programmiz: Sorting Algorithms

Showing posts with label Sorting Algorithms. Show all posts

Sunday, 20 August 2017

Quick Sort

#include<stdio.h>

void swap(int* a, int* b)
{
int t = *a;
*a = *b;
*b = t;
}

/* This function takes last element as pivot, places the pivot element at its correct position in sorted array, and places all smaller (smaller than pivot)
to left of pivot and all greater elements to right of pivot */
int partition (int arr[], int low, int high)
{
int pivot = arr[high]; // pivot
int i = (low - 1); // Index of smaller element

for (int j = low; j <= high- 1; j++)
{
// If current element is smaller than or equal to pivot
if (arr[j] <= pivot)
{
i++; // increment index of smaller element
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}

// low - Starting index,
// high - Ending index
void quickSort(int arr[], int low, int high)
{
if (low < high)
{
// PI is partitioning index, arr[p] is now at right place
int pi = partition(arr, low, high);

// Separately sort elements before
// partition and after partition
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}

/* Function to print an array */
void printArray(int arr[], int size)
{
int i;
for (i=0; i < size; i++)
printf("%d ", arr[i]);
printf("n");
}

int main()
{
int arr[] = {10, 7, 8, 9, 1, 5};
int n = sizeof(arr)/sizeof(arr[0]);
quickSort(arr, 0, n-1);
printf("Sorted array: n");
printArray(arr, n);
return 0;
}

Sunday, 13 August 2017

Merge Sort

#include<stdlib.h>
#include<stdio.h>
void merge(int arr[], int l, int m, int r)
{
    int i, j, k;
    int n1 = m - l + 1;
    int n2 =  r - m; 
    // create temp arrays 
    int L[n1], R[n2]; 
    // Copy data to temp arrays L[] and R[] 
    for (i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[m + 1+ j];
     // Merge the temp arrays back into arr[l..r]
    i = 0; // Initial index of first subarray
    j = 0; // Initial index of second subarray
    k = l; // Initial index of merged subarray
    while (i < n1 && j < n2)
    {
        if (L[i] <= R[j])
        {
            arr[k] = L[i];
            i++;
        }
        else
        {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
     // Copy the remaining elements of L[], if there are any 
    while (i < n1)
    {
        arr[k] = L[i];
        i++;
        k++;
    } 
    // Copy the remaining elements of R[], if there are any 
    while (j < n2)
    {
        arr[k] = R[j];
        j++;
        k++;
    }
} 
// l is for left index and r is right index of the sub-array of arr to be sorted 
void merge_Sort(int arr[], int l, int r)
{
    if (l < r)
    {
        // Same as (l+r)/2, but avoids overflow for large l and h
        int m = l+(r-l)/2;
 
        // Sort first and second halves
        merge_Sort(arr, l, m);
        merge_Sort(arr, m+1, r);
 
        merge(arr, l, m, r);
    }
}
// Function to print an array
void print_Array(int A[], int size)
{
    int i;
    for (i=0; i < size; i++)
        printf("%d ", A[i]);
    printf("\n");
}

int main()
{
    int arr[] = {12, 11, 13, 5, 6, 7};
    int arr_size = sizeof(arr)/sizeof(arr[0]);
 
    printf("Given array is \n");
    print_Array(arr, arr_size);
 
    merge_Sort(arr, 0, arr_size - 1);
 
    printf("\nSorted array is \n");
    print_Array(arr, arr_size);
    return 0;
}

Insertion Sort

#include <stdio.h>
#include <math.h>
 Function to sort an array using insertion sort
void insertion_Sort(int arr[], int n)
{
   int i, key, j;
   for (i = 1; i < n; i++)
   {
       key = arr[i];
       j = i-1;
   Move elements of arr[0..i-1], that are  greater than key, to one position ahead of their current position 
       while (j >= 0 && arr[j] > key)
       {
           arr[j+1] = arr[j];
           j = j-1;
       }
       arr[j+1] = key;
   }
}
 A utility function ot print an array of size n
void print_Array(int arr[], int n)
{
   int i;
   for (i=0; i < n; i++)
       printf("%d ", arr[i]);
   printf("\n");
}

int main()
{
    int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr)/sizeof(arr[0]);
    insertion_Sort(arr, n);
    print_Array(arr, n);
    return 0;
}

Bubble Sort

#include <stdio.h>

void swap(int *xp, int *yp)
{
    int temp = *xp;
    *xp = *yp;
    *yp = temp;
}
 A function to implement bubble sort
void bubble_Sort(int arr[], int n)
{
   int i, j;
   for (i = 0; i < n-1; i++)      
        Last i elements are already in place   
       for (j = 0; j < n-i-1; j++) 
           if (arr[j] > arr[j+1])
              swap(&arr[j], &arr[j+1]);
}
Function to print an array 
void printArray(int arr[], int size)
{
    int i;
    for (i=0; i < size; i++)
        printf("%d ", arr[i]);
    printf("n");
}

int main()
{
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr)/sizeof(arr[0]);
    bubble_Sort(arr, n);
    printf("Sorted array: \n");
    printArray(arr, n);
    return 0;

Selection Sort

#include <stdio.h>  
void swap(int *xp, int *yp)
{
    int temp = *xp;
    *xp = *yp;
    *yp = temp;
} 
void selectionSort(int arr[], int n)
{
    int i, j, min_index; 
     One by one move boundary of unsorted subarray
    for (i = 0; i < n-1; i++)
    {
         Find the minimum element in unsorted array
        min_index = i;
        for (j = i+1; j < n; j++)
          if (arr[j] < arr[min_index])
            min_index = j;
         Swap the found minimum element with the first element
        swap(&arr[min_index], &arr[i]);
    }
} 
 Function to print an array 
void printArray(int arr[], int size)
{
    int i;
    for (i=0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
} 
int main()
{
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr)/sizeof(arr[0]);
    selectionSort(arr, n);
    printf("Sorted array: \n");
    printArray(arr, n);
    return 0;
}

Programmiz