Data structures

Here was another interesting interview question on arrays How do you sort the array so that all the odd elements are before all the even elements. And both these subarrays must be sorted. We can first split the array so that all odd elements are in first subarray and all even elements come afterwards. Next we can use some sorting method to sort these two sub-arrays separately. Next comes the question. How do we split the array? For ith element in array, if it is even  remove the element from ith position move it to end of array Repeat this process for all elements from last to 0th Here is the code to split array into odd and even. int splitOddEven ( int * arr, int n) { int i; int evencount =0 ; for (i = n -1 ;i >=0 ;i -- ) { if (arr[i] %2==0 ) { move_extreme_right(arr,n,i); evencount ++ ; } } return evencount; } The function test whether arr[i] is even. If yes, to moves the element ...

Insertion sort is slightly better sorting method among O(n2) algorithms. It is effecient if the elements are almost sorted and if the size is small. Insertion sort basically works by splitting your elements into two parts. Sorted half and unsorted half. To begin with, Sorted half is empty and unsorted half has all elements. Then one element is removed from unsorted half and added to the sorted half. When adding , this element is inserted at the correct location. This process is continued till we have all the elements in sorted half and unsorted half is empty. Now let us try to understand it with a diagram. First 17 is removed from unsorted array and added to sorted array. Since there is one element there, it is sorted. Next 4 which is front most element now in unsored array is removed and added to sorted array. But 4 is smaller than 17, so 17 is pushed to right and its place is taken by 4.    Next 32 is removed from the front of unsorted array and added to sorted array. But he...

Quick and dirty way of sorting an array is bubble sort. It is very easy to write and follow. But please keep in mind that it is not at all effecient. #include<iostream> using std::cin; using std::cout; void readArray(int arr[],int sz); void printArray(int arr[],int sz); void sortArray(int arr[],int sz); void swap(int &a,int &b); int main() {    int sz;    cout<<"Size of the array=";    cin>>sz;    int arr[sz];    readArray(arr,sz);     sortArray(arr,sz);   cout<<"Sorted array is ";   printArray(arr,sz); } void readArray(int arr[],int sz) {  for(int i=0;i<sz;i++)    {       cout<<"arr["<<i<<"]=";       cin>>arr[i];   } } void printArray(int arr[],int sz) {  for(int i=0;i<sz;i++)    {       cout<<"arr["<<i<<"]=";    ...