CODEWITHSUNDEEP
algorithmsortingquicksort
Kiriakos Ioannidis
Kiriakos Ioannidis

Reputation: 3

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!

Upvotes: 0

Views: 532

Answers (2)

Jorge Bellon
Jorge Bellon

Reputation: 3116

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}

Upvotes: 0

Code-Apprentice
Code-Apprentice

Reputation: 83577

The answer depends on your base case. In many academic implementations, the base cases are an empty array or an array with one element. This means that an array with two elements is treated the same way an array with 1000 elements: pick a pivot, divide the array into two subarrays, then make a recursive call on the two subarrays.

Alternatively, you can treat an array of 2 elements as a base case and sort it directly.

Upvotes: 0

Related Questions