Search code examples
algorithmsortingquicksort

QuickSort Algorithm in C Sorting Just Two Numbers

I'm new to algorithms so I'm trying to understand every possible situtation. Last thing I did was to work with QuickSort algorithm sorting integers with a single pivot. My question is: What happens when I have to sort an array with only two integers? For example the arr[2]={4,2} . I know that the algorithm works but I'm not sure about how it makes it happen. I didn't found any animation for just 2 numbers, so please can anyone explain me what happens step by step in this situation?

Thanks a lot! Also, I'm sorry if its a foolish question but I can't figure it out. Have a nice day guys!

Solution

  • You perform the sorting with two elements as with any generic list size:

    1. Pick a pivot. See https://en.wikipedia.org/wiki/Quicksort for methods of choosing a pivot. For example pivot is the leftmost element 4.
    2. Partition the array in two based on the pivot:
      • 4 < 4 is false. Right hand list.
      • 2 < 4 is true. Left hand list.
    3. Sort both lists:
      • Left hand list {2} is sorted already
      • Right hand list {4} is sorted already
    4. Result is left hand list plus right hand list: {2, 4}