# Sorting

It’s generally an “in-place” algorithm, with the average time complexity of O(n log n).

Outline of the

`partition`

method goes something like this:- 1.Pick a pivot point.
- 2.Move all elements that are less than the pivot point to the left side of the partition.
- 3.Move all elements that are greater than the pivot point to the right side of the partition.
- 4.Return the index of the pivot point.

public static int partition(int low, int high)

{

int pivot = a[low];

int i = low - 1;

int j = high + 1;

while (i < j)

{

for (i++; a[i] < pivot; i++);

for (j--; a[j] > pivot; j--);

if (i < j)

swap(i, j);

}

return j;

}

public static void swap(int i, int j)

{

int temp = a[i];

a[i] = a[j];

a[j] = temp;

}

_________________

public void quickSort(int arr[], int begin, int end) {

if (begin < end) {

int partitionIndex = partition(arr, begin, end);

quickSort(arr, begin, partitionIndex-1);

quickSort(arr, partitionIndex+1, end);

}

}

private int partition(int arr[], int begin, int end) {

int pivot = arr[end];

int i = (begin-1);

for (int j = begin; j < end; j++) {

if (arr[j] <= pivot) {

i++;

int swapTemp = arr[i];

arr[i] = arr[j];

arr[j] = swapTemp;

}

}

int swapTemp = arr[i+1];

arr[i+1] = arr[end];

arr[end] = swapTemp;

return i+1;

}

In 3 Way QuickSort, an array arr[l..r] is divided in 3 parts:

a) arr[l..i] elements less than pivot.

b) arr[i+1..j-1] elements equal to pivot.

c) arr[j..r] elements greater than pivot.

**Quick Select**is a selection algorithm to find the k-th smallest element in an unordered list.

The algorithm is similar to QuickSort. The difference is, instead of recurring for both sides (after finding pivot), it recurs only for the part that contains the k-th smallest element.

This reduces the expected complexity from O(n log n) to O(n), with a worst case of O(n^2).

**Pseudo Code:**

function quickSelect(list, left, right, k)

if left = right

return list[left]

Select a pivotIndex between left and right

pivotIndex := partition(list, left, right,

pivotIndex)

if k = pivotIndex

return list[k]

else if k < pivotIndex

right := pivotIndex - 1

else

left := pivotIndex + 1

Let’s discuss in which cases we should choose QuickSort over MergeSort.

Although both Quicksort and Mergesort have an average time complexity of

*O(n log n)*, Quicksort is the preferred algorithm, as it has an _O(log(n)) _space complexity. Mergesort, on the other hand, requires _O(n) _extra storage, which makes it quite expensive for arrays.Quicksort requires to access different indices for its operations, but this access is not directly possible in linked lists, as there are no continuous blocks; therefore to access an element we have to iterate through each node from the beginning of the linked list. Also, Mergesort is implemented without extra space for

*LinkedLists.*In such case, overhead increases for Quicksort and Mergesort is generally preferred.

Last modified 3yr ago