search

emory-courses / dsa-java

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

[HW#1 ] determining row properties #88

Closed MimiOlayeye closed 3 years ago

MimiOlayeye commented 3 years ago

How would you recommend we determine a row in the 2d array in mostly sorted opposed to randomly distributed?

I don't want to waste runtime by comparing each element in a row, but I want to be able to keep track of rows that follow the properties given to us in the assignment.

MimiOlayeye commented 3 years ago

Also for a mostly sorted row.. does that imply only 2 elements are swapped (ie. 1 4 3 2 5) or can more than two elements be in the incorrect position?

Kaseyc27 commented 3 years ago

Hello Mimi it all depends on what you want to consider for mostly ascending sorted, mostly descending sorted, and randomed. You could measure the amount of swaps done to determine each, then go from there.

NuntuPu commented 3 years ago

If you were to traverse each row once to check if it is ascending, descending, or random, it would be O(n) and wouldn't significantly add to the runtime complexity.

marvinquiet commented 3 years ago

Yeah, thank you guys for your answers!