CareerCup

#include<stdio.h>

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


int main()
{
int a[] = {1,3,6,8,-5,-2,3,8};
// half of both part is sorted
int mid = 4;
int end = 8;
int i;
int j;

// take 4 pointer 2 for min and 2 for max
int min1 = mid -1;
int min2 = end - 1 ;
int max1 = 0;
int max2 = mid;

//reverse the array from mid to end
i = mid;
j = end -1;

while( i <= j )
{
swap(&a[i], &a[j]);
i++;
j--;
}

//reverse the array from begining to mid
i = 0;
j = mid -1;
while( i <= j )
{
swap(&a[i],&a[j]);
i++;
j--;
}

for(i = 0 ; i< end ; i++ )
{
printf(" %d ", a[i]);
}
printf("\n");
//always remove max from max1, if max1 is less than max2 swap them
//always replcae min from min2, if min2 is greater than min1 swap them

while(min2 > min1 )
{
if(a[max1] < a[max2])
{
swap(&a[max1],&a[max2]);
}

if(a[min2] > a[min1])
{
swap(&a[min1],&a[min2]);
}

swap(&a[max1],&a[min2]);
min2--;
max1++;
}
for(i = 0 ; i< end ; i++ )
{
printf(" %d ", a[i]);
}
printf("\n");

return 0;
}

1.Multiply the array values with -1.
2.Sort the array.
3. Multiply again with -1, display result.

Example :
Step 1 > Multiply with -1
original array 1,3,6,8,-5,-2,3,8
after multiplication -1,-3,-6,-8,5,2,-3,-8

Step 2 > Sort == > 5,2,-1,-3,-3,-6,-8,-8

Step 3 > Multiply with -1
-5,-2,1,3,3,6,8,8

but paul, this will be complexity more than O(n).

@anonymous
great logic and code dude..i guess its working for all cases

I dont think any one can solve this problem.If we remember the merging step of merge sort in which left half and right half of the array are sorted, if there was some algorithm which can solve this problem in space and in O(n) then merge sort would have become the first Algorithm to run in O(nlogn) time and constant space rather than heap sort. So I would like to conclude that this problem cannot be solved in strict O(nlogn) and constant space.

I dont think any one can solve this problem.If we remember the merging step of merge sort in which left half and right half of the array are sorted, if there was some algorithm which can solve this problem in space and in O(n) then merge sort would have become the first Algorithm to run in O(nlogn) time and constant space rather than heap sort. So I would like to conclude that this problem cannot be solved in strict O(n) and constant space.

even m hvng d same doubt..
bt is d given code giving wrng ans in ne case?

#include <iostream>
using namespace std;

void swap(int * a1, int * a2)
 {
    int temp = *a1;
    *a1 = *a2;
    *a2 = temp;
    }

int main()
 {
   int numberOfElements = 8;
   int a[] = {1,3,6,8,-5,-2,3,8};

   int i=0, j= numberOfElements/2;
   while(i <= numberOfElements/2)
    {
       if(a[i] > a[j])
         swap(&a[i], &a[j]);

       j = numberOfElements/2 ;
       while(j < (numberOfElements - 1))
        {
          if(a[j] > a[j+1])
            swap(&a[j], &a[j+1]);
          j++;
          }

       j= numberOfElements/2;
       i++;
       }
   return 0;
   }

Superb solution josh machine. appreciate it. Thanks

@josh

Can you prove the complexity of your code as O(n)

I think it will be O(n*n)
And you are using a approach quite similar to insertion sort.

As "Anonymous on November 01, 2010" pointed out if there was a solution better than heapsort (o(nlogn)) for this problem, mergesort would have already used it without using the extra space. So moral of the story, the best solution could be heapsort, I guess. No point in spending time on this question

We can do it in manner similar to Insertion sort.
We start from second half and one by one place the element in correct position by swaping.
In-place. But, time complexity will be O(N*N).
Won't work for large array.

1. Walk through the array to find the index where the value goes down - that is the starting point of the second half of the array
Let l1=length of first part, l2=length of second part

2. If l1 >= l2,start at i=0 and j=index from 1. Keep swapping elements and increment i and j by 1 until j reaches l2
(else)
If l1 < l2,start at i=l1 - 1 and j=l2 - 1. Keep swapping elements and decrement i and j by 1 until i reaches 0

O(N) time.

@ josh thanks

Solution is sorting bitonic sequence.
search for bitonic sort in google or look in wikipedia

Time complexity = O((log n)2)

NA

Why cant we use a quicksort??? O(nlogn)..??

using System;
using System.Collections.Generic;
using System.Linq;

namespace SortTest
{
    public interface IOrderedArray<T> where T : IComparable<T>
    {
        void Swap(int srcIdx, int dstIdx, IList<T> array);
    }

    public class IntOrderedArrayHelper : IOrderedArray<int>
    {
        public void Swap(int srcIdx, int dstIdx, IList<int> array)
        {
            array[srcIdx] += array[dstIdx];
            array[dstIdx] = array[srcIdx] - array[dstIdx];
            array[srcIdx] = array[srcIdx] - array[dstIdx];
        }
    }

    public class OrderPartialOrderedArray<T> where T : IComparable<T>
    {
        private readonly IOrderedArray<T> _orderHelper;
        public OrderPartialOrderedArray(IOrderedArray<T> orderHelper)
        {
            if (orderHelper == null) throw new Exception("Injection Helper is null!");
            _orderHelper = orderHelper;
        }

        public void Order(IList<T> array, OrderType orderType)
        {
            var n = array.Count() / 2;
            var compareCount = n;
            for (var i = n - 1; i >= 0; i--)
            {
                var shift = CompareSubArray(i, array, i + 1, compareCount, orderType);
                if (shift == i) return;

                compareCount = shift - i;
            }
        }

        private int CompareSubArray(int valIdx, IList<T> array, int startIdx, int compareCount, OrderType orderType)
        {
            var val = array[valIdx];
            for (var i = startIdx; i < startIdx + compareCount; i++)
            {
                var compRes = val.CompareTo(array[i]);
                if ((orderType == OrderType.Desc && compRes <= 0) || (orderType == OrderType.Asc && compRes >= 0))
                {
                    return valIdx;
                }
                _orderHelper.Swap(valIdx, i, array);
                valIdx = i;
            }
            return valIdx;
        }
    }

    public enum OrderType
    {
        Asc,
        Desc
    }

    internal class Program
    {
        private static void Main(string[] args)
        {
            var array = new List<int> {1, 3, 6, 8, -5, -2, 3, 8};
            var arraytst = new List<int> {-5, -2, 3, 8, 1, 3, 6, 8};
            var arraytst1 = new List<int> {-5, 7, 9, -1, 8, 11};
            var arrayasc = new List<int> { 8, 6, 3, 1, 8, 3, -2, -5 };

            var orderHelper = new IntOrderedArrayHelper();
            var orderArray = new OrderPartialOrderedArray<int>(orderHelper);

            orderArray.Order(arraytst1, OrderType.Desc);
            orderArray.Order(arrayasc, OrderType.Asc);
        }
    }
}

great Josh Machine ..