Optimize the cost of concatenation of all these strings into one big string.

You have n strings with their lengths. You are given an add(string s1,string s2) which would concatenate the string s2 with s1 and return s3. Optimize the cost of concatenation of all these strings into one big string.
Eg: 1,5,2 are the lengths of given strings.
1+5=6
6+2=8
total cost=14 can you Optimize this total cost?

Source : Sent by a reader named rahul.

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

WAP for Quick Sort Algorithm

Data Structure used:Array

Algorithm:Divide & Conquer
1. Phase:Partition O(N) Time
2. Phase: Divide the array in two part Recursively & call partition function until we are run out of array O(nlogn)

Recursive Function Looks Like T(n)=2*T(n/2)+O(n)

Working Code:
public class QuickSort
{

public static int SIZE = 1000000;

public int[] sort(int[] input) {
quickSort(input, 0, input.length-1);
return input;
}

public static void main(String args[]){
int[] a = new int[SIZE];
for(int i=0;i pivot)
j--;
if (i <= j) {
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
j--;
}
}
return i;
}
}
//Time taken to sort a million elements : 156 milliseconds

Time Complexity O(nlogn)
Space Complexity O(logn)
Run Here http://ideone.com/clone/ClBCZ

Complexity Analysis ( More Focus on Space )

very Few of us Know & are abale to come up space compelxity of quick sort if asked during the interview isn't it ?

Quicksort has a space complexity of O(logn), even in the worst case, when it is carefully implemented such that

* in-place partitioning is used. This requires O(1).
* After partitioning, the partition with the fewest elements is (recursively) sorted first, requiring at most O(logn) space. Then the other partition is sorted using tail-recursion or iteration.

The version of quicksort with in-place partitioning uses only constant additional space before making any recursive call. However, if it has made O(logn) nested recursive calls, it needs to store a constant amount of information from each of them. Since the best case makes at most O(logn) nested recursive calls, it uses O(logn) space. The worst case makes O(n) nested recursive calls, and so needs O(n) space.

However, if we consider sorting arbitrarily large lists, we have to keep in mind that our variables like left and right can no longer be considered to occupy constant space; it takes O(logn) bits to index into a list of n items. Because we have variables like this in every stack frame, in reality quicksort requires O(log2n) bits of space in the best and average case and O(nlogn) space in the worst case. This isn't too terrible, though, since if the list contains mostly distinct elements, the list itself will also occupy O(nlogn) bits of space.