hash table quicksort function

[MyOnlinePersona]

Hello, I asked this question earlier http://www.cplusplus.com/forum/beginner/268612/ and it was explained good to me. But i am wondering, is quicksort or any type of sort done on hash tables. I thought it must since my question was answered but I can not find help online on how to do this sort and I normally can find help for everything. so is this sort done on hash tables?

[jonnin]

it just depends on what you are doing.
you don't normally sort anything in a hash table, but if you think you have a reason to do so?
this is one of those times when maybe you need to explain to yourself what it is you want to actually DO?
a badly undersized hash could be sorted and binary searched on each bucket.
or a weird hash like first letter of strings is a bucket, sort the buckets, and you have broken up big data by alphabet or something.

quick sort would work on a hash table just like any other array. the algorithm is unaware of what the input 'means' to the human.

[MyOnlinePersona]

I have to use a binary search on the table so i think must sort it first. I think the quick sort is the best. That is why I look to do this. I have found geekforgeek website that has quick sort, and I understand that, but it does not work for hash table because it is not array.


It would be every bucket that i must pass as the array to the quicksort method?

quickSort(arr[], low, high)
{
    if (low < high)
    {
        /* pi is partitioning index, arr[pi] is now
           at right place */
        pi = partition(arr, low, high);

        quickSort(arr, low, pi - 1);  // Before pi
        quickSort(arr, pi + 1, high); // After pi
    }
}

[Ganado]

If you're using binary search on the "table" itself, then it isn't a hash table, it's a binary search tree. So I'm still not sure what you're asking.

Perhaps I'm using different terminology than you, but in my experience a "hash table" is unordered (e.g. it's like C++ unordered_map). An ordered map (e.g. C++ map) is often implemented as a tree.

What does your data structure actually look like? Describe it to us.
If it's some type of structure that you would do a binary search on, then perhaps you are looking for an in-order traversal: https://www.geeksforgeeks.org/tree-traversals-inorder-preorder-and-postorder/

[MyOnlinePersona]

I think i must use the binary search on each bucket. I do have a hash table I learned to code it from tutorial. this one https://www.youtube.com/watch?v=m6n_rozU8dA

My code is not all same as tutorial but similar, but is hashtable as same as his.

I am not sure why i must do the binary search, i have just been told this is how i have to do it.

[jonnin]

I am not sure why i must do the binary search, i have just been told this is how i have to do it.

if you were told to do something for school or something, sure.
you can double hash (make each bucket its own hash table). You can hash the original better, so your buckets are very small and linear search without sorting it. Or anything else you want to build.

We can't tell you why with zero details. As often as not its because someone said so -- the idiotic requirements put on students in school lately are just mind boggling, for example.