Quicksort algorithm

quicksort.cpp

void quickSort(int arr[], int left, int right) {
      int i = left, j = right;
      int tmp;
      int pivot = arr[(left + right) / 2];
 
      /* partition */
      while (i <= j) {
            while (arr[i] < pivot)
                  i++;
            while (arr[j] > pivot)
                  j--;
            if (i <= j) {
                  tmp = arr[i];
                  arr[i] = arr[j];
                  arr[j] = tmp;
                  i++;
                  j--;
            }
      };
 
      /* recursion */
      if (left < j)
            quickSort(arr, left, j);
      if (i < right)
            quickSort(arr, i, right);
}

quicksort.java

int partition(int arr[], int left, int right)
{
      int i = left, j = right;
      int tmp;
      int pivot = arr[(left + right) / 2];
     
      while (i <= j) {
            while (arr[i] < pivot)
                  i++;
            while (arr[j] > pivot)
                  j--;
            if (i <= j) {
                  tmp = arr[i];
                  arr[i] = arr[j];
                  arr[j] = tmp;
                  i++;
                  j--;
            }
      };
     
      return i;
}
 
void quickSort(int arr[], int left, int right) {
      int index = partition(arr, left, right);
      if (left < index - 1)
            quickSort(arr, left, index - 1);
      if (index < right)
            quickSort(arr, index, right);
}

quicksort.py

def Quicksort(A, p, r):
    """Sort array A in place.

    Initial call should be Quicksort(A, 0, len(A))
    """
    if p < r:
  q = Partition(A, p, r)
	Quicksort(A, p, q)
	Quicksort(A, q+1, r)
  

def Partition(A, p, r):
    x = A[p]                       # the pivot element
    i = p - 1
    j = r + 1

    while 1:
	j = j - 1
	while A[j] <= x:
	    j = j - 1

	i = i + 1
	while A[i] >= x:
	    j = j - 1

	if i < j:               # elements being compared
	    swap(A[i], A[j])
	else:
	    return j

http://www.algolist.net/Algorithms/Sorting/Quicksort

http://users.teilam.gr/~alexefentakis/Quicksort.pdf

Nice 👍