The Royal Coding
Binary Search Bubble Sort Build A Max Heap Build A Min Heap Graph Traversal Heap Sort Implementing A Basic Hash Table Implementing A Binary Search Tree Implementing A Queue Implementing A Stack Insertion Sort Length Of Linked List Linear Search Linked Lists Merge A Two Sorted Linked List Merge Sort Quick Sort Redix Sort Reverse A Linked List Selection Sort Ternary Search Suffix Automata Construction

Python/C/C++/JAVA

Advanced Practice Programs with Code and Concept

By D.S

Quick Sorting

Okay, so when it comes to sorting algorithms, Quick sort is a pretty popular one. It's efficient and works well with large sets of data. Now, the cool thing is that you can implement Quick sort in several programming languages including C, C++, Python, and Java. In C and C++, you would typically use arrays to store your data and then utilize pointers to quickly swap the values during the sorting process. In Python, you could make use of the list type which has some built-in functionality for sorting. Java is similar to C++ in that you'd utilize arrays and pointers to perform swaps but would need to encapsulate everything within a class structure. Overall, implementing Quick sort in any of these languages requires some knowledge of basic coding concepts but should be fairly straightforward once you get the hang of it!

(a.) C Program

#include <stdio.h>

      void swap(int* a, int* b) {
          int t = *a;
          *a = *b;
          *b = t;
      }
      
      int partition(int arr[], int low, int high) {
          int pivot = arr[high];
          int i = (low - 1);
      
          for (int j = low; j <= high - 1; j++) {
              if (arr[j] < pivot) {
                  i++;
                  swap(&arr[i], &arr[j]);
              }
          }
          swap(&arr[i + 1], &arr[high]);
          return (i + 1);
      }
      
      void quickSort(int arr[], int low, int high) {
          if (low < high) {
              int pi = partition(arr, low, high);
              quickSort(arr, low, pi - 1);
              quickSort(arr, pi + 1, high);
          }
      }
      
      void printArray(int arr[], int size) {
          for (int i = 0; i < size; i++)
              printf("%d ", arr[i]);
          printf("\n");
      }
      
      int main() {
          int arr[] = {10, 7, 8, 9, 1, 5};
          int n = sizeof(arr) / sizeof(arr[0]);
          printf("Original array: ");
          printArray(arr, n);
          quickSort(arr, 0, n - 1);
          printf("Sorted array: ");
          printArray(arr, n);
          return 0;
      }
Output:-
Original array:
10 7 8 9 1 5
Sorted array:
1 5 7 8 9 10

(b.) C++ Program

#include <iostream>
      using namespace std;
      
      void swap(int* a, int* b) {
          int t = *a;
          *a = *b;
          *b = t;
      }
      
      int partition(int arr[], int low, int high) {
          int pivot = arr[high];
          int i = (low - 1);
      
          for (int j = low; j <= high - 1; j++) {
              if (arr[j] < pivot) {
                  i++;
                  swap(&arr[i], &arr[j]);
              }
          }
          swap(&arr[i + 1], &arr[high]);
          return (i + 1);
      }
      
      void quickSort(int arr[], int low, int high) {
          if (low < high) {
              int pi = partition(arr, low, high);
              quickSort(arr, low, pi - 1);
              quickSort(arr, pi + 1, high);
          }
      }
      
      void printArray(int arr[], int size) {
          for (int i = 0; i < size; i++)
              cout << arr[i] << " ";
          cout << endl;
      }
      
      int main() {
          int arr[] = {10, 7, 8, 9, 1, 5};
          int n = sizeof(arr) / sizeof(arr[0]);
          cout << "Original array: " << endl;
          printArray(arr, n);
          quickSort(arr, 0, n - 1);
          cout << "Sorted array: " << endl;
          printArray(arr, n);
          return 0;
      }
Output:-
Original array:
10 7 8 9 1 5
Sorted array:
1 5 7 8 9 10

(c.) Python Program

def partition(arr, low, high):
    i = (low - 1)
    pivot = arr[high]

    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]

    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return (i + 1)

def quickSort(arr, low, high):
    if low < high:
        pi = partition(arr, low, high)
        quickSort(arr, low, pi - 1)
        quickSort(arr, pi + 1, high)

arr = [10, 7, 8, 9, 1, 5]
print("Original array: ")
print(arr)
n = len(arr)
quickSort(arr, 0, n - 1)
print("Sorted array: ")
print(arr)
Output:-
Original array:
10 7 8 9 1 5
Sorted array:
1 5 7 8 9 10

(d.) Java Program

public class Main {
      public static int partition(int arr[], int low, int high) {
          int pivot = arr[high];
          int i = (low - 1);
          for (int j = low; j < high; j++) {
              if (arr[j] <= pivot) {
                  i++;
                  int temp = arr[i];
                  arr[i] = arr[j];
                  arr[j] = temp;
              }
          }
          int temp = arr[i + 1];
          arr[i + 1] = arr[high];
          arr[high] = temp;
          return i + 1;
      }
  
      public static void quickSort(int arr[], int low, int high) {
          if (low < high) {
              int pi = partition(arr, low, high);
              quickSort(arr, low, pi - 1);
              quickSort(arr, pi + 1, high);
          }
      }
  
      public static void printArray(int arr[]) {
          int n = arr.length;
          for (int i = 0; i < n; ++i)
              System.out.print(arr[i] + " ");
          System.out.println();
      }
  
      public static void main(String args[]) {
          int arr[] = {10, 7, 8, 9, 1, 5};
          System.out.println("Original array:");
          printArray(arr);
          int n = arr.length;
          quickSort(arr, 0, n - 1);
          System.out.println("Sorted array:");
          printArray(arr);
      }
  }
Output:-
Original array:
10 7 8 9 1 5
Sorted array:
1 5 7 8 9 10

How did you feel about this post?

😍 🙂 😐 😕 😡

Was this helpful?

👍 👎