0

Implement quick sort algorithm with faulty results. Details of what I want to do can be found at the video: https://courses.edx.org/courses/course-v1:HarvardX+CS50+X/courseware/cdf0594e6a80402bbe902bb107fd2976/22251a2b00ac42788c70ca6f6ccbe7fd/ Does break command take me out of inner loop or both loops? Below you'll find the code, any help will be welcome.

int main (void)
{

// List to be sorted
int list[] = { 3, 9, 8, 5, 7, 6, 4, 2, 1};
int arrayIndexLimit = (sizeof (list) / sizeof (int)) - 1;
int temp = 0;

// "J" separates sorted part from unsorted one 
for (int j = 0; j < arrayIndexLimit; j++)
{

    // Inner iteration looks for the smallest number in unsorted part 
    for (int i = j; i <= arrayIndexLimit; i++)
    {

        // Swaps values whenever current item is smaller than pivot 
        if (list[i] < list[arrayIndexLimit])
        {
            temp = list[j];
            list[j] = list[i];
            list[i] = temp;
            break;
        }  

        // If pivot is the smallest
        if (i == arrayIndexLimit)
        {
            temp = list[i];
            list[i] = list[j];
            list[j] = temp;
            break;
        }
    }
}

// Print sorted list
}
0

break breaks out of the inner loop.

About quicksort:

I haven't watched the video, but that is not quicksort.

For starters, quicksort uses the "divide and conquer" principle, by which you continuously divide the array into smaller parts and tackle the task. Your code is not doing that at all.

Most implementations I've seen are not iterative, but recursive, which usually makes it much easier to do, but either way, the pseudo code is something like this:

1) Pick a pivot 
2) Partition the array around the pivot so that all elements < pivot are on the left and all elements > pivot are on the right
3) Repeat 1 and 2 on left hand side
4) Repeat 1 and 2 on right hand side.

And the partitioning routine is:

Partition(array, indexL, indexR) // First and last index of array
... pivot = array[indexL] // much easier to always have the first element of the array as pivot (even if you choose another one, it's always best to swap it to the beginning)
... i = indexL + 1 // this index keeps track of where the pivot should be, which is always going to be at index i - 1
... for j = indexL + 1 to indexR: // j iterates the array
...... if array[j] < pivot:  
.......... swap array[j] and array[i]
.......... increase i  
...swap array[indexL] and array[i-1] // this puts the pivot after the last element smaller than it. 

If you are on Coursera, i highly recommend watching these videos, if you're interested in quicksort: https://www.coursera.org/learn/algorithm-design-analysis/lecture/Zt0Ti/quicksort-overview

It doesn't get any better that Prof. Roughgarden explanation and it's the cleanest implementation i've seen.

I have no idea how to implement it iteratively, by the way. It will make things complicated because, unlike binary search, in which you only explore one half of the array each time, in this case you have to explore both, so it's much easier to do it recursively.

To better understand the logic, grab your array, pen and paper and run the partitioning pseudocode with it.

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .