2.C Program to sort the given list using quick sort technique(Part B)

2.C Program to sort the given list using quick sort technique

ALGORITHM :

Step 1: Start

Step 2: Implement the quick_sort function that takes the list (my_list), start index (low), and end index (high) as parameters.

Step 3: If low is less than high:

        a. Choose a pivot element (my_list[high]) and partition the list around the pivot.

        b. Recursively call quick_sort for the elements before the pivot (my_list[low] to my_list[pivot - 1]).

        c. Recursively call quick_sort for the elements after the pivot (my_list[pivot + 1] to my_list[high]).

Step 4: Input the number of elements (n) and the list of elements (my_list).

Step 5: Call quick_sort(my_list, 0, n-1) to sort the list.

Step 6: Display the sorted list.

Step 7: End

SOURCE CODE :

#include <stdio.h>

// Function to swap two elements in the list

void swap(int arr[], int a, int b) {

    int temp = arr[a];

    arr[a] = arr[b];

    arr[b] = temp;

}

// Function to perform the partitioning step of Quick Sort

int partition(int arr[], int low, int high) {

    int pivot = arr[high]; // Choose the rightmost element as pivot

    int i = low - 1;

    for (int j = low; j < high; j++) {

        if (arr[j] <= pivot) {

            i++;

            swap(arr, i, j);

        }

    }

    swap(arr, i + 1, high);

    return (i + 1);

}

// Function to implement Quick Sort

void quickSort(int arr[], int low, int high) {

    if (low < high) {

        int pi = partition(arr, low, high); // Partitioning index

        // Recursive calls on the two partitions

        quickSort(arr, low, pi - 1);

        quickSort(arr, pi + 1, high);

    }

}

// Function to print the list

void printList(int arr[], int size) {

    printf("Sorted list: ");

    for (int i = 0; i < size; i++) {

        printf("%d ", arr[i]);

    }

    printf("\n");

}

int main() {

    int size;

    printf("Enter the size of the list: ");

    scanf("%d", &size);

    int arr[size];

    printf("Enter the elements of the list:\n");

    for (int i = 0; i < size; i++) {

        scanf("%d", &arr[i]);

    }

    printf("Original list: ");

    for (int i = 0; i < size; i++) {

        printf("%d ", arr[i]);

    }

    printf("\n");

    quickSort(arr, 0, size - 1);

    printList(arr, size);

    return 0;

}

OUTPUT :

Enter the size of the list: 7

Enter the elements of the list:

54 26 93 17 77 31 44

Original list: 54 26 93 17 77 31 44

Sorted list: 17 26 31 44 54 77 93