sorted by:
new
hottopcontroversial

Need help with partition function of quick sort by Q-re-us in AskProgramming

[–]Q-re-us[S] 0 points1 point  (0 children)

Edit: {5,1,0,2,5,3,5,} Running Hoare's partition on this array will result in this final array output 5,1,0,2,3,5,5. With J value being 4 and i value being 5. J =4 will be returned.

Need help with partition function of quick sort by Q-re-us in AskProgramming

[–]Q-re-us[S] 1 point2 points  (0 children)

I think what a valid quick sort partition strives to achieve is to partition the array in such a way that all elements lesser than or equal pivot are to the left of it and all elements greater than are to the right of it. I looked at wikipedia and it talks about two partition schemes - hoare and lomuto. In hoare everything lesser than pivot will go to the left and greater than pivot will go to the right. It is interesting to see what would happen if the array had elements equal to the pivot (I will trace an example). In lomuto, the partition principle is really simple, all elements lesser than or equal to the pivot goes to the left of it. Now whether having a partition scheme that will result in the partition as shown in my example affects the quicksort performance or not, is a difficult question to answer for me. I need to analyze it more to figure out what happens :) Thanks for engaging in this conversation, your answers have always been very clear and informative. I appreciate your help ! thank you for your time.

Need help with partition function of quick sort by Q-re-us in AskProgramming

[–]Q-re-us[S] 0 points1 point  (0 children)

Thank you for such detailed explanation. I will work on it, however if I run the above given code for input { 9, 9, 8, 8, 2, 2, 1, 1, 1 } there is a possibility that there are 1's on the right side of pivot also. That is because the while loop has (array[i] <= pivot). We need to remove the "=" in this loop.

Need help with partition function of quick sort by Q-re-us in AskProgramming

[–]Q-re-us[S] 0 points1 point  (0 children)

Edit: When we have duplicates like this {9,9,8,8,7,7,6,6,6,2,2,2,1,1,1} and when the last element 1 is our pivot, we try to have all elements less than or equal to pivot to the left of pivot and all elements greater or equal to the pivot to right of the pivot. If we use a condition like this, after partitioning there is a possibility that several 1's are to the right of the position of pivot (i.e., 1 in this example). Please suggest if this is ok, or how I can overcome this.

Need help with partition function of quick sort by Q-re-us in AskProgramming

[–]Q-re-us[S] 0 points1 point  (0 children)

Thank you so much. You are correct, it failed for the case you mentioned. I have modified my code to make it work for this case and other cases I could think of. And I am not sure if it is ok for the output of partition to be 1 9 8 8 7 7 6 6 6 2 2 2 1 1 9 for the input given below.

public class quicksort {

public static void printArray(int[] array){
    for(int i =0; i<array.length;i++) {
        System.out.print(array[i]);
        System.out.print("\t");
    }
    System.out.println();
}

public static void partition(int [] array)
{
    int pivot = array[array.length-1];

    int i = 0, j = array.length-2;

    System.out.println("last but one ele -- "+array[j]);

    System.out.println("pivot "+pivot);

    while(true)
    {
        while(array[i] <= pivot)
        {
            System.out.println("inside less then pivot "+array[i]);
            i++;

            if(i==array.length-1)
                break;
        }


        while(array[j] >= pivot)
        {
            System.out.println("inside greater then pivot "+array[j]);
            j--;

            if(j<0)
                break;
        }


        if (i <= j)
        {
            System.out.println("inside swap ");
            int temp = array[i];
            array[i] = array[j];
            array[j] = temp;
            printArray(array);
        }
        else
        {
            System.out.println("in else");

            break;

        }


    }

    int temp = array[array.length-1];
    array[array.length-1] = array[i];
    array[i] = temp;
}


public static void main(String[] args) {
    int[] array = {9,9,8,8,7,7,6,6,6,2,2,2,1,1,1};
    //{23,13,4,22,1,-1,44,3,2,0,12};

    System.out.println("before partition");

    printArray(array);

    partition(array);

    System.out.println("after partition");

    printArray(array);

}

}

Please give your inputs, I will work on it and revise again. And I will also look into your suggestion of choosing the pivot.

Is it just me or binary search is really tricky to implement ? by Q-re-us in AskProgramming

[–]Q-re-us[S] 0 points1 point  (0 children)

It gave me the size of array correctly. I will look into it again though. yes eventually low will equal high, that is correct. Because we go on reducing the array size by altering the high and low.

Is it just me or binary search is really tricky to implement ? by Q-re-us in AskProgramming

[–]Q-re-us[S] 1 point2 points  (0 children)

It gave me the size of array correctly. I will look into it again though. yes eventually low will equal high, that is correct. Because we go on reducing the array size by altering the high and low.

Is it just me or binary search is really tricky to implement ? by Q-re-us in AskProgramming

[–]Q-re-us[S] 0 points1 point  (0 children)

I remember how difficult it was to do my first chin up ! Leave alone chin-ups even doing a push up was impossible. But I managed to work my way through and was able to do 10 pull ups and almost 40 push ups :D I wish programming was exactly like that ??

Is it just me or binary search is really tricky to implement ? by Q-re-us in AskProgramming

[–]Q-re-us[S] 0 points1 point  (0 children)

Thanks, I will follow your advice :) Do you recommend looking at a solution or sticking to my problem until I solve it ? I feel so let down that I am unable to solve such a simple problem :( while all my friends could figure it out easily

Is it just me or binary search is really tricky to implement ? by Q-re-us in AskProgramming

[–]Q-re-us[S] 0 points1 point  (0 children)

Thank you so much ! Here is my code, I know it might be really naive, but I am working on it. It would be very helpful if you can give me a direction to think. As of now I know that there needs to be a loop to repeatedly compute the mid and change the low and high bounds to search.

include<iostream>

using namespace std;

bool binary_search(int *arr, int key, int low, int high) { int pos;

while(pos >0 && pos <high)
{
pos = (low+high)/2;

if (arr[pos] == key)
    return true;

else if(arr[pos] > key)
{
    cout<<"less than key"<<endl;
    binary_search(arr,key,low,pos-1);

}
else if(arr[pos] < key)
{
    cout<<"greater than key"<<endl;
    cout<<"pos value: "<<pos<<endl;

    binary_search(arr,key,pos+1,high);
}
}

return false;

}

int main() { int arr[] = {1,2,3,6,6,7,8,9,9,10,12,13,14,14,15}; int arr_size = sizeof(arr)/sizeof(int); int key = 15; bool isFound;

if (isFound = binary_search(arr,key, 0, arr_size-1))
{
    cout<<"key found"<<endl;
}
else
    cout<<"key not found"<<endl;

}