This semester we learned about Divide and Conquer in which the problem is divided into subproblems and then solved just like in Merge Sort or Quick Sort.
Though I am not posting this question to get my assignment solved by you people , Our professor gave us an assignment to implement Bubble Sort as a divide and conquer algorithm , Now I'm sitting on my laptop scratching my head for days on how Bubble Sort can be divide and conquer algorithm.
If I try to implement Bubble Sort as divide and conquer the array must be divided , when I divide the array into its last element and then merge it back to its sorted form , The algorithm just becomes Merge Sort.
If I implement it by recursively calling bubbleSort(array,size-1) , the algorithm becomes Reduce and Conquer.
My question is "How can bubble sort be implemented as Divide and Conquer Algorithm ?"
Assume you write a bubblesort function that lets you sort part of an array:
bubblesort(arr, start, end)
{
// sorts the items from arr[start] to arr[end]
}
So if you had the array [1,7,4,9,6,3,2,5] and called bubblesort(arr, 0, 3), the resulting array would be [1,4,7,9,6,3,2,5].
Now imagine what would happen if you made these calls:
bubblesort(arr, 0, 1);
bubblesort(arr, 2, 3);
bubblesort(arr, 4, 5);
bubblesort(arr, 6, 7);
Then
bubblesort(arr, 1, 3);
bubblesort(arr, 4, 7);
And, finally:
bubblesort(arr, 0, 7);
It's the same call pattern as merge sort, but it's definitely not merge sort.