Quick Sort

Algorithm

Copy
main() 
Begin
	Read array size, "size"
	Declare arr[size]
	for (i = 0; i < size; i++), do
		Read element store in arr[i]
	End For
	Call quicksort(arr, 0, size - 1)
	Display sorted array "arr"
End

Copy
quicksort(arr, low, high)
Begin
	if (low >= high) return
	Set pivot = partition( arr, low, high)
	Call quicksort(arr, low, pivot - 1)
	Call quicksort(arr, pivot + 1, high)
End

Copy
partition(arr, low, mid)
Begin
	Set pivot = arr[low]
	Set i = low
	Set j = high
	while (i < j), do
		while (i < high && arr[i] <= pivot), do
			Increment i by 1
		End While 
		while (j > low && arr[j] > pivot), do
			Decrement j by 1
		End While
		if (i < j), then
			Call swap(arr, i, j)
		End If
	End While
	Call swap(arr, low, j)
	return j
End

Copy
swap(arr, i, j)
Begin
	Set temp = arr[i]
	Set arr[i] = arr[j]
	Set arr[j] = temp
End

Program

Copy
#include <stdio.h>

void swap(int arr[], int i, int j) {
  int temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

int partition(int arr[], int low, int high) {
  int pivot = arr[low];
  int i = low;
  int j = high;

  while (i < j) {
    while (i < high && arr[i] <= pivot) i++;
    while (j > low && arr[j] > pivot) j--;
    if (i < j) swap(arr, i, j);
  }

  swap(arr, low, j);
  return j;
}

void quick_sort(int arr[], int low, int high) {
  if (low >= high) return;
  int pivot = partition(arr, low, high);
  quick_sort(arr, pivot + 1, high);
  quick_sort(arr, low, pivot - 1);
}

int main() {
  int size;
  printf("Enter array size: ");
  scanf("%d", &size);

  int arr[size];
  printf("Enter array elements: ");
  for (int i = 0; i < size; i++) scanf("%d", &arr[i]);

  quick_sort(arr, 0, size - 1);

  printf("Sorted array is: ");
  for (int i = 0; i < size; i++) printf("%d ", arr[i]);
}