search

emory-courses / dsa-java

Data Structures and Algorithms in Java
https://emory.gitbook.io/dsa-java/
42 stars 55 forks source link

[HW1] What is the most efficient way of sorting all sorted row in 2d array #83

Closed BaichenRong closed 3 years ago

BaichenRong commented 3 years ago

According to my previous post, I have sorted all of my rows in 2d arrays. The speed is significantly faster than the baseline. However, it is not enough because I need a sorting algorithm to sort all the sorted row into a final sorted 1d array. I have tried several methods and it failed. What's more, I learned from the internet that using a k-way merge will be efficient but that sorting algorithm was not taught in the class. What sorting algorithm can I apply in this situation in order to surpass the baseline?

https://github.com/BaichenRong/dsa-java/blob/master/src/main/java/edu/emory/cs/sort/hybrid/HybridSortHW.java

Thank you!

marvinquiet commented 3 years ago

I think a mergesort strategy can be applied for sorting rows into a 1d array.

BaichenRong commented 3 years ago

Thank you for your reply! I tried mergesort but it is still slower than the baseline. Any amendment I can make in my code?

marvinquiet commented 3 years ago

IMO, the reason why it is slow is because of putting them into 1D and use quicksort again.

When I say mergesort, I was talking about i.e, sorted row1, sorted row2. When merging them together, you can use two pointers pointing to these two arrays, and then try to compare them. Whenever one of them is empty, you simply concatenate the remaining parts to the sorted result. The worst case is comparing to the end, however, most of them will return halfway. Does this sound reasonable?

BaichenRong commented 3 years ago

Thank you for your suggestion! It is extremely helpful! I will try this right now!