@all
Please find my O(n) time and O(1) space implementation for this
problem.
Summary of approach: let i be start for first sorted part and j be
start of next sorted part. move i as long as a[i] is less than a[j] as
that means things are sorted.
if a[i] > a[j], swap them and increment i. Increment j if it is no
more start of a sprted part. So j always points to start of a sorted
part of array. As long as i equals j, we are done.
Here is the implementation
# include "stdio.h"
void sort(int* array, int SIZE, int i, int j)
{
while(i<j)
{
if(array[i] <= array[j])
i++;
if(array[j] < array[i])
{
int temp = array[j];
array[j]=array[i];
array[i]=temp;
i++;
if(j< (SIZE-1) && (array[j] > array[j+1]) )
j++;
}
}
}
void my_print(int * array, int SIZE)
{
printf("\n");
for(int i = 0; i < SIZE ; i++)
printf("%d, ",array[i]);
printf("\n");
}
int main()
{
int array1[8] = {1,3,6,7,4,5,6,8};
int array2[10] = {1,2,3,5,6,7,4,8,9,10};
sort(array1,8,0,4);
sort(array2,10,0,6);
my_print(array1,8);
my_print(array2,10);
return 0;
}
Sourav
On Jul 5, 2:15 pm, harit agarwal <[email protected]> wrote:
> inplace merging requires worst case O(nlogn)
> check pdf
>
> merge-algorithms-screen.pdf
> 238KViewDownload
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
