8 FAQ Sorting Algorithms Bubble,Insertion,Selection,Pancake,Quick,Merge,Heap & Tree Sorting

1st program Contains Bubble,Insertion,Selection,Pancake Sorting

#include

/* Function to reverse arr[] from start to end*/
void rvereseArray(int arr[], int start, int end)
{

int temp;
while(start < end)
{
temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
start++;
end--;
}
}

/* Utility that prints out an array on a line */
void printArray(int arr[], int size)
{
int i;
for (i=0; i < size; i++)
printf("%d ", arr[i]);

printf("\n");
}

int get(int ar[],int i)
{

return ar[i];

}

int length(int ar[])
{
return (sizeof(ar)/sizeof(int));
}


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

for( i = 1; i < n; i++ )
{
int index = i;
for( j = i-1; j >= 0; j-- )
{
if( arr[j] > arr[index] )
{
rvereseArray(arr, j, index);
index = j;
}
}
}

}

void swap(int a[],int i,int j)
{
int temp;
temp=a[i];
a[i]=a[j];
a[j]=temp;

}
void select_sort(int a[],int n)
{
/* a[0] to a[n-1] is the array to sort */
int iPos;
int iMin,i;

/* advance the position through the entire array */
/* (could do iPos < n-1 because single element is also min element) */
for (iPos = 0; iPos < n; iPos++)
{
/* find the min element in the unsorted a[iPos .. n-1] */

/* assume the min is the first element */
iMin = iPos;
/* test against all other elements */
for (i = iPos+1; i < n; i++)
{
/* if this element is less, then it is the new minimum */
if (a[i] < a[iMin])
{
/* found new minimum; remember its index */
iMin = i;
}
}

/* iMin is the index of the minimum element. Swap it with the current position */
if ( iMin != iPos )
{
swap(a, iPos, iMin);
}
}


}
void insert_sort(int A[],int n)
{
int i,j,key;

for(j=1;j {
key=A[j];
//> A[ j ] is added in the sorted sequence A[0, .. j-1]
i=j-1;
while(i >= 0 && A [i] > key)
{ A[i+1] =A[i];
i=i-1;
}
A [i+1]=key;
}

}

void bubble_sort(int arr[],int n)//optmized see loop
{
int temp,i,j,k;

for(i=0;i{
for(j=n-1;j>i;j--)
{
if(arr[j-1] >arr[j])
{
temp=arr[j-1];
arr[j-1]=arr[j];
arr[j]=temp;
}
}
for(k=0;k{
printf(" %d \t",arr[k]);
}

printf( " \n " );

}

}



int main()
{
int arb[]={5,2,1,4,3};
int n=5;
int i=0;

bubble_sort(arb,n);

printf("\n\n-- Bubble Sorted Series --");
for(i=0;i{
printf("\n \n \t %d",arb[i]);
}

int ari[]={5,2,1,4,3};

insert_sort(ari,n);

printf("\n\n-- Insertion Sorted Series --");
for(i=0;i{
printf("\n \n \t %d",ari[i]);
}

int ars[]={5,2,1,4,3};

select_sort(ars,n);

printf("\n\n-- Selection Sorted Series --");
for(i=0;i{
printf("\n \n \t %d",ars[i]);
}


int arp[]={5,2,1,4,3};

pancake_sort(arp,n);

printf("\n\n-- Pancake Sorted Series --");
for(i=0;i{
printf("\n \n \t %d",arp[i]);
}


}


Time Complexity O(n^2)
Space Complexity O(1)
Run Here https://ideone.com/clone/5Htf9


2nd program heap Sort 

How heap can be build in O(n)  check this out http://www.cs.umd.edu/~meesh/351/mount/lectures/lect14-heapsort-analysis-part.pdf

#include
#include
using namespace std;

void swap(int *x, int *y) {
int temp = *x;
*x = *y;
*y = temp;
}

class Heap
{
int *arr; // pointer to array of elements in heap
int heap_size;
public:
Heap(int a[], int size);
void buildminHeap();
void minHeapify(int );
void heapSort();
int getRoot() {return arr[0];}
int parent(int i){ return (i-1)/2; } ;
int left(int i) { return (2*i + 1); } ;
int right(int i) { return (2*i + 2); } ;
};

Heap::Heap(int a[], int size) {
heap_size = size;
arr = a;
}



void Heap::minHeapify(int i) {
int l = left(i);
int r = right(i);

printf( "l=%d,r=%d \n ",l,r);

int largest;
if (l < heap_size && arr[l] < arr[i])
largest = l;
else
largest = i;
if (r < heap_size && arr[r] < arr[largest])
largest = r;
if (largest != i)
{
swap(&arr[i], &arr[largest]);
printf(" a[i]=%d \t a[large]=%d", arr[i],arr[largest]);
minHeapify(largest);
}
}

void Heap::buildminHeap() {
int i = (heap_size - 1)/2;
printf( " %d ",i);
while (i >= 0)
{
minHeapify(i);
i--;
}
}
void heapsort(int a[],int n)
{
Heap hp(a, n);
hp.buildminHeap();
int i=0,temp=0;
for (i = n-1; i >= 1; i--)
{
temp = a[0];
a[0] = a[i];
a[i] = temp;
hp.minHeapify(0);
}

}
int main()
{
int k = 4;
int arr[] = {12, 34, 10, 8, 9, 4, 56};
int n = sizeof(arr)/sizeof(arr[0]);

heapsort(arr,n);

int i=0;
for(i=0;i printf( " %d ",arr[i]);

getchar();
return 0;
}


Time Complexity O(nlogn)
Space Complexity O(1)
Run here https://ideone.com/tP2z3

3rd program Merge Sort

#include

void merge(int numbers[], int temp[], int left, int mid, int right)
{
int i, left_end, num_elements, tmp_pos;

left_end = mid - 1;
tmp_pos = left;
num_elements = right - left + 1;

while ((left <= left_end) && (mid <= right))
{
if (numbers[left] <= numbers[mid])
{
temp[tmp_pos] = numbers[left];
tmp_pos = tmp_pos + 1;
left = left +1;
}
else
{
temp[tmp_pos] = numbers[mid];
tmp_pos = tmp_pos + 1;
mid = mid + 1;
}
}

while (left <= left_end)
{
temp[tmp_pos] = numbers[left];
left = left + 1;
tmp_pos = tmp_pos + 1;
}
while (mid <= right)
{
temp[tmp_pos] = numbers[mid];
mid = mid + 1;
tmp_pos = tmp_pos + 1;
}

for (i=0; i <= num_elements; i++)
{
numbers[right] = temp[right];
right = right - 1;
}
}

void m_sort(int numbers[], int temp[], int left, int right)
{
int mid;

if (right > left)
{
mid = (right + left) / 2;
m_sort(numbers, temp, left, mid);
m_sort(numbers, temp, mid+1, right);

merge(numbers, temp, left, mid+1, right);
}
}


void mergeSort(int numbers[], int temp[], int array_size)
{
m_sort(numbers, temp, 0, array_size - 1);
}



int main()
{

int arr[] = {12, 34, 10, 8, 9, 4, 56};
int n = sizeof(arr)/sizeof(arr[0]);
int temp[7];

mergeSort(arr,temp,n);

int i=0;
for(i=0;i printf( " %d ",arr[i]);

getchar();
return 0;
}


Time Complexity O(nlogn)
Space Complexity O(n)
Run here https://ideone.com/ZQImg

4th program Quick Sort

#include "stdio.h"

int split ( int*, int, int ) ;

int main( )
{
int arr[10] = { 11, 2, 9, 13, 57, 25, 17, 1, 90, 3 } ;
int i ;

void quicksort ( int *, int, int ) ;

quicksort ( arr, 0, 9 ) ;

printf ( "\nArray after sorting:\n") ;

for ( i = 0 ; i <= 9 ; i++ )
printf ( "%d\t", arr[i] ) ;

}

void quicksort ( int a[ ], int lower, int upper )
{
int i ;
if ( upper > lower )
{
i = split ( a, lower, upper ) ;
quicksort ( a, lower, i - 1 ) ;
quicksort ( a, i + 1, upper ) ;
}
}

int split ( int a[ ], int lower, int upper )
{
int i, p, q, t ;

p = lower + 1 ;
q = upper ;
i = a[lower] ;

while ( q >= p )
{
while ( a[p] < i )
p++ ;

while ( a[q] > i )
q-- ;

if ( q > p )
{
t = a[p] ;
a[p] = a[q] ;
a[q] = t ;
}
}

t = a[lower] ;
a[lower] = a[q] ;
a[q] = t ;

return q ;
}


Time Complexity O(nlogn)
Space Complexity O(logn) if stack space considered else O(1)
Run Here https://ideone.com/clone/YFFWE

5th program BST Sort


#include
#include

/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct node
{
int data;
struct node* left;
struct node* right;
};

/* Helper function that allocates a new node
with the given data and NULL left and right
pointers. */
struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;

return(node);
}

/* Give a binary search tree and a number,
inserts a new node with the given number in
the correct place in the tree. Returns the new
root pointer which the caller should then use
(the standard trick to avoid using reference
parameters). */
struct node* insert(struct node* node, int data)
{
/* 1. If the tree is empty, return a new,
single node */
if (node == NULL)
return(newNode(data));
else
{
/* 2. Otherwise, recur down the tree */
if (data <= node->data)
node->left = insert(node->left, data);
else
node->right = insert(node->right, data);

/* return the (unchanged) node pointer */
return node;
}
}

/* Given a binary tree, print its nodes in inorder*/
void printInorder(struct node* node)
{
if (node == NULL)
return;

/* first recur on left child */
printInorder(node->left);

/* then print the data of node */
printf("%d ", node->data);

/* now recur on right child */
printInorder(node->right);
}

/* Driver program to test sameTree function*/
int main()
{
struct node* root = NULL;
root = insert(root, 4);
insert(root, 2);
insert(root, 1);
insert(root, 3);
insert(root, 6);
insert(root, 5);

printInorder(root);

getchar();
return 0;
}

Time Complexity O(nlogn)
Space Complexity O(1)
Run here https://ideone.com/tP2z3

8 FAQ Sorting Algorithms Bubble,Insertion,Selction,Pancake,Quick,Merge,Heap,Tree Sorting

WAP to Implement The Counting Sort Pure O(n)

#include
#include

void counting_sort(int array[], int size)
{
int i, min, max;

min = max = array[0];
for(i = 1; i < size; i++)
{
if (array[i] < min)
min = array[i];
else if (array[i] > max)
max = array[i];
}

int range = max - min + 1;
int *count =(int*)malloc(range * sizeof(int));

for(i = 0; i < range; i++)
count[i] = 0;

for(i = 0; i < size; i++)
count[ array[i] - min ]++;
int j, z = 0;
for(i = min; i <= max; i++)
for(j = 0; j < count[ i - min ]; j++)
array[z++] = i;

free(count);
}

/* Explaination
// CountingSort.
//
// The data to be sorted is in array A with
// subscripts 0..n-1. For example,
//
// subscript: 0 1 2 3 4 5 6 7 8
// A = [ 2, 0, 4, 1, 4, 2, 2, 1, 0 ]
//
// The data values range from 0 to MAX (=4).
// A second array B will hold the sorted data.
//
// Initialize a "counting array" C:
// ---------------------------------------------

for (i = 0; i <= MAX; i++)
C[i] = 0;

// ---------------------------------------------
// Count how often each value occurs in A:
// ---------------------------------------------

for (i = 0; i < n; i++)
C[A[i]]++;

// ---------------------------------------------
// At this point C[i] contains the number
// of occurrences of the value i in A. In
// the example:
//
// 0 1 2 3 4
// C = [ 2, 2, 3, 0, 2 ]
//
// Make C[i] contain the number of
// occurrences of values 0..i in A:
// ---------------------------------------------

for (i = 1; i <= MAX; i++)
C[i] += C[i-1];

// ---------------------------------------------
// In the example:
//
// 0 1 2 3 4
// C = [ 2, 4, 7, 7, 9 ]
//
// Note that now C[i] is such that in the sorted
// array, the last occurrence of value i will be
// just before position C[i] (e.g., the last 2 in
// the sorted array B will be just before position
// C[2]=7).
//
// Move values from A to B, using C to know
// where to put them:
// ---------------------------------------------

for (i = n-1; i >= 0; i--)
B[--C[A[i]]] = A[i];

// ---------------------------------------------
// Now B looks like
//
// 0 1 2 3 4 5 6 7 8
// B = [ 0, 0, 1, 1, 2, 2, 2, 4, 4 ]
//
// Not that it matters, but now C[i] contains the
// subscript of the first occurrence of value i
// in the sorted array B:
//
// 0 1 2 3 4
// C = [ 0, 2, 4, 7, 7 ]
//
*/
void counting_sort_n(int A[],int n)
{

int i, min, MAX;

min = MAX= A[0];
for(i = 1; i < n; i++)
{
if (A[i] < min)
min = A[i];
else if (A[i] > MAX)
MAX= A[i];
}

int range = MAX- min + 1;
int *C =(int*)malloc(range * sizeof(int));
int *B=(int*)malloc(range * sizeof(int));
for (i = 0; i <= MAX; i++)
C[i] = 0;

for (i = 0; i < n; i++)
C[A[i]]++;

for (i = 1; i <= MAX; i++)
C[i] += C[i-1];

for (i = n-1; i >= 0; i--)
B[--C[A[i]]] = A[i];

for(i=0;i<9;i++)
printf( "%d ", B[i]);

}
int main()
{
int a[]={5,1,2,4,3};

//1st Method
counting_sort(a,5);

int i=0;
printf( "\n");
for(i=0;i<5;i++)
printf( "%d ", a[i]);

//2nd Method

int b[]={ 2, 0, 4, 1, 4, 2, 2, 1, 0};
counting_sort_n(b,9);



return 0;

}

Run here https://ideone.com/kLlEa

WAP Create a singly linked list of Leaf nodes from a binary tree

include

struct node
{
struct node *left, *right;
int data;

};


void LeafLinked(struct node *t, struct node **prevLeaf, struct node **head)
{
if(t)
{

if(t->left == NULL && t->right == NULL)
{ //leaf

if(*head == NULL)
*head = t;

else if(*prevLeaf)
(*prevLeaf)->next = t;

*prevLeaf = t;
}
else { //at least one child
LeafLinked(t->left, prevLeaf, head);
LeafLinked(t->right, prevLeaf, head);
}
}
}


/*Utilities*/

struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;

return(node);
}

inline void printList(struct node *t)
{
while(t)
{
printf("%d ", t->data);
t = t->next;
}
printf("\n");
}

int main()
{
/*level 0*/
struct node *t = newNode(10);

/*level 1*/
t->left = newNode(20);
t->right = newNode(30);


/*level 2*/
t->left->left = newNode(40);
t->left->right = newNode(70);
t->right->left = newNode(50);
t->right->right = newNode(60);

/*level 3*/
t->left->left->left = newNode(70);
t->right->right->left = newNode(60);
t->right->right->right = newNode(160);

/*Empty List head*/
struct node *head = NULL, *prevLeaf = NULL;

/*Convert tree to list*/
LeafLinked(t, &prevLeaf, &head);

/*print list*/
printList(head);


return 0;
}

Rune Here https://ideone.com/UOakN

Project Euler problem 16 -What is the sum of the digits of the number 2^1000?

215 = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.

What is the sum of the digits of the number 2^1000?


The problem no. 16 in Project Euler required us to find the sum of all the digits of the number 2^{1000}. Well, a no brainer would be to use the BigInteger and find the number by multiplication. I wanted a better solution.

But my knowledge and wits failed me. I must accept taking help on this one. I googled up a bit and found a very neat way of exponentiation. The basic funda is this:

2^n = 2 * 2^{n-1}

=> 2^n = 2^{n-1} + 2^{n-1}

So at any given time, if we have an array of digits of say 2^p, then getting 2^{p+1} is as simple as doubling all the digits and adjusting the carry-overs. The same principle can be easily extended to deal with any base.

class Problem_16 {
public long sumOfDigits(int base, int exp) {
int numberOfDigits = (int) Math.ceil(exp * Math.log10(base));
System.out.println(numberOfDigits);
int[] digits = new int[numberOfDigits];
digits[0] = base;
int currentExp = 1;


while (currentExp < exp) {
currentExp++;
int carry = 0;
for (int i = 0; i < digits.length; i++) {
int num = base * digits[i] + carry;
digits[i] = num % 10;
carry = num / 10;
}
}

long sum = 0;
for (int digit : digits)
sum += digit;


return sum;
}

public static void main(String[] args) {
int base = 2;
int exp = 10;
System.out.println(new Problem_16().sumOfDigits(base, exp));
}
}


Run here https://ideone.com/pYciv

Project Euler Problem 8- Finding product of 5 Consecutive in 1000 Digit Number

Source http://projecteuler.net/index.php?section=problems&id=8

public class Problem_8 {
public int getMaxProductOfFiveConsequtiveDigits(String[] nums) {
int maxProduct = 0;


for (String num : nums) {
int length = num.length();
if (length < 5)
continue;
int[] n = new int[5];
for (int i = 0; i < 5; i++)
n[i] = num.charAt(i) - '0';
int cycle = 5;
while (cycle < length) {
int prod = n[0] * n[1] * n[2] * n[3] * n[4];
if (prod > maxProduct)
maxProduct = prod;
n[cycle % 5] = num.charAt(cycle) - '0';
cycle++;
}
}

return maxProduct;
}

public static void main(String[] args) {
String[] nums = ("73167176531330624919225119674426574742355349194934"
+ "96983520312774506326239578318016984801869478851843"
+ "85861560789112949495459501737958331952853208805511"
+ "12540698747158523863050715693290963295227443043557"
+ "66896648950445244523161731856403098711121722383113"
+ "62229893423380308135336276614282806444486645238749"
+ "30358907296290491560440772390713810515859307960866"
+ "70172427121883998797908792274921901699720888093776"
+ "65727333001053367881220235421809751254540594752243"
+ "52584907711670556013604839586446706324415722155397"
+ "53697817977846174064955149290862569321978468622482"
+ "83972241375657056057490261407972968652414535100474"
+ "82166370484403199890008895243450658541227588666881"
+ "16427171479924442928230863465674813919123162824586"
+ "17866458359124566529476545682848912883142607690042"
+ "24219022671055626321111109370544217506941658960408"
+ "07198403850962455444362981230987879927244284909188"
+ "84580156166097919133875499200524063689912560717606"
+ "05886116467109405077541002256983155200055935729725"
+ "71636269561882670428252483600823257530420752963450").split("0");
System.out.println((new Problem_8()).getMaxProductOfFiveConsequtiveDigits(nums));
}
}


Run herer for Smaller Input https://ideone.com/SLY30

Project Euler Problem 67-Finding Maximum Sum in Triangle

By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.

3
7 4
2 4 6
8 5 9 3

That is, 3 + 7 + 4 + 9 = 23.

Find the maximum total from top to bottom in triangle.txt (right click and 'Save Link/Target As...'), a 15K text file containing a triangle with one-hundred rows.

NOTE: This is a much more difficult version of Problem 18. It is not possible to try every route to solve this problem, as there are 299 altogether! If you could check one trillion (1012) routes every second it would take over twenty billion years to check them all. There is an efficient algorithm to solve it. ;o)




The 18th and the 67th problems in Project Euler are one and the same. The only difference is in the input test case. The problem 18 has a smaller input and 67 has a large input. For the explanation purpose, I’ll consider problem 18. The code without any modification can be extended to 67th problem.

Given a triangle of numbers, the objective is to determine the maximum sum along paths descending from the apex of the triangle to the base. Consider the example:

3

7 4

2 4 6

8 5 9 3

The maximum sum occurs along the path 3-7-4-9.

The problem required us to determine the maximum sum for any given triangle. Also an interesting thing is mentioned about the problem, in case you were considering a brute force method of checking every path:

It is not possible to try every route to solve this problem (where the base of the triangle has 100 numbers), as there are 2^(99) altogether! If you could check one trillion (10^(12)) routes every second it would take over twenty billion years to check them all. There is an efficient algorithm to solve it. ;o)

Being forewarned, I never once gave a thought to the brute force solution.

This problem was not as tricky as they tried to sound it. The solution is quite easy to see. I’ll run you through the idea as it formed in my mind. I used the top-to-bottom approach for forming the idea and coming up with the solution, and then implemented the solution in bottom-to-top sweep. I hope you have realized that a greedy solution will not work here.

Consider the triangle given above. I’ll work out the maximum path for it from top to bottom. We start with 3. We may choose either 7 or 4. To help make this choice, consider the two triangles with apex 7 and the other with 4. So we have two smaller triangles of height 3 each. Say the maximum length for the triangle with apex 7 is x and with apex 4 is y. If x > y, we choose 7 as the next on the path, else 4.

Thus, at every step we form two triangle of height 1 smaller, and choose the apex which has the larger sum. Implemented as it is will give us the recursive solution. To get an iterative solution to this problem, one could traverse from bottom-to-top. The bottom-to-top approach is also simple. It is greedy in approach.

Consider the penultimate row, specifically the triangle with 2 as apex and 8, 5 as the base. The maximum sum in this triangle is 2+8 = 10. Replace 2 with 10. Do the same for all the triangles formed with the penultimate layer as the apex. Thus our triangle reduces to

3

7 4

10 13 15

You know what to do next. Keep applying the same till the apex of the original triangle has the maximum sum.

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;

public class Problem_18 {
private static int heightOfTree = 100;
private final String fileName = "problem_67.in";
private int[][] tree;

public int maxValue() throws IOException {
readTree();

for (int i = Problem_18.heightOfTree - 2; i >= 0; i--)
for (int j = 0; j <= i; j++)
tree[i][j] += tree[i + 1][j] > tree[i + 1][j + 1] ? tree[i + 1][j] : tree[i + 1][j + 1];

return tree[0][0];
}

private void readTree() throws IOException {
tree = new int[Problem_18.heightOfTree][];

BufferedReader bufferedReader = new BufferedReader(new FileReader(fileName));
for (int i = 0; i < Problem_18.heightOfTree; i++) {
tree[i] = new int[i + 1];
String[] values = bufferedReader.readLine().split(" ");
for (int j = 0; j <= i; j++)
tree[i][j] = Integer.parseInt(values[j]);
}
}

public static void main(String[] args) throws IOException {
System.out.println(new Problem_18().maxValue());
}
}

Project Euler Problems Finding Maximum Sum In Triangle From Top to Bottom

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;

public class Problem_18 {
private static int heightOfTree = 100;
private final String fileName = "problem_67.in";
private int[][] tree;

public int maxValue() throws IOException {
readTree();

for (int i = Problem_18.heightOfTree - 2; i >= 0; i--)
for (int j = 0; j <= i; j++)
tree[i][j] += tree[i + 1][j] > tree[i + 1][j + 1] ? tree[i + 1][j] : tree[i + 1][j + 1];

return tree[0][0];
}

private void readTree() throws IOException {
tree = new int[Problem_18.heightOfTree][];

BufferedReader bufferedReader = new BufferedReader(new FileReader(fileName));
for (int i = 0; i < Problem_18.heightOfTree; i++) {
tree[i] = new int[i + 1];
String[] values = bufferedReader.readLine().split(" ");
for (int j = 0; j <= i; j++)
tree[i][j] = Integer.parseInt(values[j]);
}
}

public static void main(String[] args) throws IOException {
System.out.println(new Problem_18().maxValue());
}
}

WAP to reorder linked list as even elements followed by odd elements or Vice versa

#include
#include

/* Link list node */
struct node
{
int data;
struct node* next;
};

void push(struct node** head_ref, int new_data)
{
/* allocate node */
struct node* new_node =
(struct node*) malloc(sizeof(struct node));

/* put in the data */
new_node->data = new_data;

/* link the old list off the new node */
new_node->next = (*head_ref);

/* move the head to point to the new node */
(*head_ref) = new_node;
}

//struct node*
void even_odd(struct node *current)
{
struct node* even=NULL;
struct node* odd=NULL;
struct node* oddstart=NULL;
//struct node* current=*head;

while(current)//partition linked list in two part
{
if((current->data)&1)//%2!=0)
{
if(odd)
odd->next=current;
else
oddstart=current;

odd=current;
}
else
{
if(even)
even->next=current;
even=current;

}

current=current->next;
}


if(even)
even->next=oddstart;// append to odd-starting position

if(odd)
odd->next=NULL;////make odd last equal to null;


}

/* Utility function to print a linked list */
void printList(struct node *head)
{
while(head!=NULL)
{
printf("%d ",head->data);
head=head->next;
}
printf("\n");
}

/* Drier program to test above function*/
int main()
{
/* Start with the empty list */
struct node* head = NULL;

push(&head, 12);
push(&head, 4);
push(&head, 12);
push(&head, 3);
push(&head, 16);
push(&head, 13);
push(&head, 8);
push(&head, 16);
push(&head, 15);
push(&head, 5);

even_odd(head);

printList(head);


}


Run Here

WAP to Fine Min Distance between two Number in Different List , Each Word May Occur at Differnt Position

You have two lists, each containing position of a word in some document. Write a program that returns minimum distance between the words in the document.
For example: Suppose X occurs at places {2, 3, 5, 10, 12, 16, 19, 20} and Y occurs at {8, 14, 27, 29}, then the minimum distance between X and Y is 1 (X=12,Y=14 OR X=16,Y=14).


#include
#include
#include

int min_Dist(int a[], int m, int b[], int n)
{

int i = 0,j= 0,min = INT_MAX,cur;

while(i < m && j < n)
{
cur = abs(a[i] - b[j]);

if(cur min=cur;
else
min=min;

if(a[i] < b[j])
i++;
else
j++;
}

return min;
}

int main() {

int a[] ={2, 3, 5, 10, 12, 16, 19, 20};//{2, 3, 5, 11, 18, 19, 20};
int b[]= {8, 14, 27, 29};//{15, 24, 27, 29};
int a_size=sizeof(a)/sizeof(int);
int b_size=sizeof(b)/sizeof(int);

printf("%d\n", min_Dist(a,a_size,b,b_size));

return 0;
}


Run Here https://ideone.com/5qIcB